1. Простое деление

Иногда простой вопрос из элементарной арифметики может поставить всех в тупик. Например, я хочу разделить четыре числа, а именно 701, 1 059, 1 417 и 2312 на максимально возможное число так, чтобы остаток от деления на него всех четырех чисел был одинаковым. Как же это можно сделать? Конечно, с помощью запутанного метода проб и ошибок можно получить верный ответ, но существует и более простой способ. Какой?

2. Девять шкатулок

Следующая головоломка показывает, как важно порой знать границы интервала, которому принадлежит число. Это может пригодиться достаточно часто. Например, до сих пор неизвестно, сколькими способами шахматный конь может обойти всю доску, пройдя по каждой клетке ровно один раз. Но мы знаем, что это число меньше, чем количество сочетаний из 168 по 63, и больше, чем 31 054 144 (это количество путей определенного типа). Можно взять и более знакомый пример. Если спросить кого-нибудь, сколько монет у него в кармане, он затруднится с ответом. Но задав ему еще несколько вопросов, мы можем получить ответ вида: «Да, я думаю, что у меня больше трех монет, и точно уверен, что их меньше 25 ». Итак, зная, что некое число в моей головоломке находится в промежутке между 2 и 12, читатель сможет дать верный ответ. Без этой информации число ответов было бы бесконечным, и выбрать из них единственно правильный было бы невозможно.

Эту головоломку мне рассказал мой друг дон Мануэль Родригес, эксцентричный скупец из Новой Кастилии. В новогоднюю ночь 1879 года он показал мне девять шкатулок. Он сообщил, что в каждой шкатулке находится квадратное число золотых дублонов, и разница между числом дублонов в шкатулках А и В такая же, как и между В и С. Та же разница между количеством монет в шкатулках D и Е, Е и F, G и Н, Н и I. Затем он попросил меня определить, сколько же монет в каждой шкатулке.

Сначала я решил, что это невозможно и что число ответов бесконечно велико, но, поразмыслив, понял, что это не так. Ни одна из шкатулок не была пустой. Вес шкатулок А, В и С увеличивался в соответствии с алфавитным порядком, то же самое верно для D, Е, F и для G, Н, I. Однако шкатулки D или Е не обязательно должны быть тяжелее С, а шкатулки G или Н не обязательно тяжелее F. Также было очевидно, что шкатулка А может содержать не более дюжины монет. Зная это, я смог найти верный ответ.

Короче говоря, нам нужно найти девять чисел (представляющих из себя квадрат чисел), таких что каждая тройка чисел (А, В, С; D, Е, F и G, Н, I) образовывала бы арифметическую прогрессию. Разница между числами в каждой группе должна быть одинакова. Кроме того, А меньше 12. Сколько же дублонов лежало в каждой из девяти шкатулок?

3. Задача банкира

У одного банкира был азартный клиент, который всегда был готов ввязаться в спор. Желая излечить его от этой дурной привычки, банкир предложил поспорить, что клиент не сможет разделить содержимое ящика, в котором находились только монеты, на равные части.

Банкир положил одну или более монет в ящик (столько, сколько ему захотелось), затем клиент добавил одну или более монет, но не больше 40. При этом ни банкир, ни клиент не знали, сколько же монет положил другой. Наконец, клиент должен был положить в ящик столько монет, сколько пожелает банкир. Определите, сколько монет должен положить в ящик банкир и сколько монет должен положить в ящик клиент по просьбе банкира, чтобы банкир имел наибольшие шансы выиграть.

4. Задача султана

Один султан решил отправить в сражение армию, которая могла бы построиться в два квадрата двенадцатью различными способами. Какое наименьшее число солдат может быть в такой армии?

Чтобы сделать задачу понятнее, поясню, что если бы в армии было 130 солдат, то они смогли бы построиться в два квадрата только двумя способами: по 81 и 49 либо по 121 и 9. Разумеется, в любом построении должны участвовать все солдаты армии.

Решения

1. Вычтем каждое число из всех остальных, и получим 358 (дважды: 1059 - 701 = 358 и 1417 - 1059 = 358), 716(1417--701 =716), 1611 (2312-701 =1611),

1 253 (2312 - 1059 = 1253) и 895 (2312 --1417 = 895). Итак, 358 равно 2 х 179, поэтому единственный возможный общий делитель, для которого остаток от деления в любом случае будет равен нулю, — это 179. Методом проб и ошибок получим, что 179 удовлетворяет условиям задачи. Поэтому именно 179 — искомое число, и для всех чисел, указанных в задаче, остаток от деления на него будет равен 164.

2. Ниже приведен ответ, удовлетворяющий всем условиям задачи:

А = 4
В = 3364
С = 6724
D = 2116
Е = 5476
F = 8836
G = 9409
Н = 12769
I = 16129

Каждое из этих чисел является квадратом для следующих чисел (в алфавитном порядке): 2,58,82,46,74,94,97,113 и 127. Во всех случаях разность между А и В, В и С, D и Е и так далее равна 3360.

3. Чтобы монеты нельзя было разделить на равные столбики (одну монету нельзя считать столбиком), нужно, чтобы их число было простым. Если банкир получит простое число, он победит. Сейчас

я покажу, как это можно сделать простым способом вне зависимости оттого, сколько монет положит в ящик клиент, то есть чтобы банкир всегда выигрывал.

Сначала банкир должен положить 40 монет, затем, вне зависимости от того, сколько добавит клиент, попросить его добавить в ящик квадрат от того числа монет, которое он только что положил, уменьшенного на единицу. Так, банкир положит 40 монет, клиент добавит, например, 6, затем 25 (5 в квадрате). В результате в ящике будет лежать 71 монета — простое число. Попробуем еще раз. Банкир кладет 40 монет, клиент добавляет 12, затем 121 (11 в квадрате), в результате в ящике будет лежать 173 монеты — снова простое число.

Ключ к решению задачи — следующий любопытный факт: если прибавить к любому числу, не превышающему 39, его квадрат и увеличить сумму на 41, то результат будет простым числом. Первым это обнаружил великий математик Эйлер.
Можно предложить другое решение: банкир должен попросить клиента добавить столько монет, чтобы в результате в ящике оказалось определенное число монет. Но это не просто делает задачу абсурдной, но и нарушает правило о том, что ни один из игроков не должен знать, сколько монет положил другой.

4. Наименьшие простые числа, которые можно представить в виде 4n + 1, — это 5, 13, 17, 29 и 37; наименьшие, которые можно представить в виде 4n - 1, — это 3,7,11,19 и 23. Таким образом, простые числа из первой группы всегда можно представить в виде суммы двух квадратов единственным способом. Так, 5 = 4 + + 1; 13 = 9+ 4; 17 = 16+1; 29 = 25+ 4; 37 = 36 + 1. Но простые числа из второй группы никак нельзя представить в виде суммы двух квадратов. Чтобы число можно было представить в виде суммы двух квадратов разными способами, необходимо, чтобы это число имело определенное количество простых сомножителей из первой группы. Так, 5 или 13 — единственные числа, которые можно представить одним способом. Однако 65 (5x13) можно представить двумя способами; 1105 (5 х 13 х 17) —четырьмя; 32405(5 х 13 х 17 х 29) — восемью способами. Таким образом, для каждого нового множителя, который мы добавим, число способов удваивается. Обратите внимание, что я говорю «новый множитель», поскольку повторное умножение на один и тот же множитель подчиняется другому закону. Мы не можем выразить 25 (5 х х 5) двумя способами, только одним. Однако 125(5x5x5) можно представить двумя способами, равно как и 625 (5 х 5 х 5 х 5). Но если мы добавим еще один множитель 5, то сможем представить результат в виде суммы двух квадратов тремя разными способами.

Если простое число из второй группы будет множителем искомого числа, то это число не сможет быть суммой двух квадратов. Так, 15 (3 х 5) не подходит, 135 (3 х 3 х 3 х 5) — тоже. Но если 3 встретится среди сомножителей четное число раз, то всё изменится: эти тройки сами образуют квадрат и мы получим решение, но только одно. Так, 45 (3 х 3 х 5 или 9 х 5) = 36 + 9. Аналогично может использоваться множитель 2 либо 2 в любой степени, например, 4,8,16,32. Однако его использование будет влиять на число решений, за исключением случаев, подобных 50, когда квадрат удваивается и мы получаем два ответа: 49 + 1 и 25 + 25.

Как только мы разложим число на простые множители, мы сразу же сможем определить, можно ли разложить это число на два квадрата. Если это возможно, то найти все возможные варианты разложения очень просто, и это легко можно сделать в уме. Я упомянул число 130. Нетрудно видеть, что оно равно 2x5x13. Так как 65 можно представить двумя способами (64+1 и 49 + 16), то 130 также можно представить двумя способами, так как множитель 2 не влияет на ответ.

Наименьшее число, которое можно представить в виде суммы двух квадратов двенадцатью разными способами, равно 160 225. Именно столько солдат содержит наименьшая по размерам армия, удовлетворяющая условиям задачи.

Это число равно произведению 5x5x13x17x29. Каждый из множителей этого произведения принадлежит к требуемой группе. Если бы все множители были различны, то число способов равнялось бы шестнадцати, но так как один из множителей повторяется, то способов всего двенадцать. Двенадцать пар — это 400 и 15, 399 и 32, 393 и 76, 392 и 81, 384 и 113, 375 и 140, 360 и 175, 356 и 183, 337 и 216, 329 и 228, 311 и 252, 265 и 300. Если мы возведем в квадрат числа из каждой пары, после чего сложим их, то для каждой пары эта сумма будет равна 160225.