Пятьсот двадцать головоломок

Magazine (14, 1964) указывают 64 способа, которыми можно выразить 64 с помощью четырех четверок.

Кнут в журнале Mathematics Magazine (37, 1964, pp. 308— 310) показал, как представить 64, используя только одну четверку и три рода символов: знак квадратного корня, знак факториала и скобки. Чтобы выразить таким образом число 64, требуется 57 знаков квадратного корня, 9 знаков факториала и 18 скобок. С помощью вычислительной машины удалось выяснить, что все положительные целые числа, не превосходящие 208, можно выразить аналогичным образом. Кнут высказывает предположение, что этот метод применим ко всем целым положительным числам.

Дьюдени частично прав в своем утверждении относительно 113. Насколько мне известно, никто не сумел представить это число без использования весьма нестандартных символов или чрезвычайно сложных процедур, вроде той, которую предложил Кнут. — М. Г.]

109. Какие символы считать допустимыми — дело вкуса, но я бы лично предпочел обойтись без всяких log.

Вот несколько решений:

110. Если мы умножим 497 на 2, то получим 994. Если же мы сложим эти два числа, то получим 499. Цифры в обоих случаях одни и те же. Аналогичный результат справедлив для 263 и 2. Мы получим соответственно 526 и 265.

[Г. Линдгрен указывает, что, вводя девятки после первой цифры, можно получить два ответа при любом желаемом числе цифр: 4997 + 2 = 4999; 499 ? 2 = 9994; 2963 + 2 = 2965; 2963 ? 2 = 5926; аналогично для 49 997+(или ?)2; 29 963+(или ?)2 и т. д. — М. Г.]

111. Квадрат числа 836, равный 698 896, содержит четное число цифр, причем его можно читать как обычным способом слева направо, так и справа налево. Среди всех квадратов, содержащих данное четное число цифр, палиндромический квадрат наименьший.

112. Если число нулей, заключенных между двумя единицами, равно любому числу, кратному 3, плюс 2, то два сомножителя всегда можно выписать немедленно с помощью следующего любопытного правила: 1001 = 11 ? 91; 1 000 001 = 101 ? 9901; 1 000 000 001 = 1001 ? 999 001; 1 000 000 000 001 = 10 001 ? 99 990 001. В последнем случае мы получаем требуемый ответ, а 10 001 = 73 ? 137. Кратность вхождения 3 в 11 равна 3 (11 = 3 ? 3 + 2). Следовательно, в каждый сомножитель мы вставляем по три нуля и добавляем лишнюю девятку.

Если бы наше число, как я предположил, содержало 101 нуль, то наибольшее число, на которое можно умножить 3, чтобы произведение не превосходило 101, равнялось бы 33 и сомножители содержали бы 33 нуля и 34 девятки и имели бы вид, указанный выше. Если бы количество нулей в нашем числе было четным, то вы смогли бы найти два сомножителя следующим образом: 1001 = 11 ? 91; 100 001 = 11 ? 9091; 10 000 001 = 11 ? 909 091 и т.д.

113. Число 1 234 567 890 разлагается на множители следующим образом: 2 ? 3 ? 3 ? 5 ? 3607 ? 3803. Если 3607 мы умножим на 10, а 3803 на 9, то получим два составных множителя: 36 070 и 34 227, дающих в произведении 1 234 567 890 и обладающих наименьшей разностью.

114. Для того чтобы число делилось на 11, нужно, чтобы либо четыре чередующиеся цифры в сумме давали 17, а остальные пять — 28, либо, наоборот, четыре цифры давали в сумме 28, а пять — 17. Так, в приведенном примере (482 539 761) цифры 4, 2, 3, 7, 1 дают в сумме 17, а 8, 5, 9, 6 дают 28. Далее, четыре цифры могут в сумме дать 17 девятью различными способами, а пять цифр могут дать 17 двумя способами. Всего получается 11 способов. В каждом из этих 11 случаев четыре цифры можно переставить 24, а пять цифр — 120 способами, что дает 2880 вариантов. Всего благоприятных исходов получается 2880 ? 11 = 31680. Поскольку девять цифр можно переставить 362 880 способами, то мы получаем 115 против 11 за то, что наугад взятое число не будет делиться на 11[34].

115. Запишем под нашим числом справа налево числа 1, 10, 11, как показано ниже:

4	9	1	2	9	3	0	8	2	1	3
10	1	11	10	1	11	10	1	11	10	1

Умножим теперь числа 1 и 10, стоящие внизу, на числа, записанные над ними, и сложим полученные произведения; затем проделаем то же самое с числами 11 и вычтем из первой суммы вторую. В результате получим: 13 + 08 + 29 + 49 = 99; 11 ? (2 + 3 + 1) = 66. Разность равна 33 и совпадает как раз с остатком от деления нашего числа на 37.

Вот ключ к решению задачи. Если мы поделим 1, 10, 100, 1000 и т. д. на 37, то будем последовательно получать остатки: 1, 10, 26 и снова 1, 10, 26 и т. д. Удобнее вычесть 37 из 26 и сказать, что остаток равен минус 11. Если вы примените данный метод к числу 49 629 708 213, то получите, что первая сумма равна 99, а вторая сумма равна 165. Разность равна минус 66. Прибавьте 37 и вы получите минус 29. Но, поскольку ответ отрицательный, прибавьте еще раз 37, и вы получите верный ответ, равный 8. Теперь вы можете применить аналогичный метод и к другим простым делителям. В случае 7 и 13 это сделать легко. В первом из них вы пишите 1, 3, 2 (1, 3, 2), 1, 3, 2 и т. д. справа налево, причем числа в скобках берете со знаком минус. Во втором случае надо записать 1 (3. 4, 1), 3, 4, 1 (3, 4, 1) и т. д.

116. Обозначим наше число через ABCABCABC. Если суммы цифр, обозначенных буквами A, B и C, равны соответственно:

А	В	С
18	19	8
15	15	15
12	11	22
19	8	18
22	12	11
8	18	19
11	22	12

то в первых трех случаях 11A - 10B = C, в следующих двух 11A - 10B - C = 111(3 ? 37). И наконец, в последних двух случаях 10B + C - 11A = 111. Если имеет место один из этих случаев, то независимо от конкретного значения соответствующих цифр наше число делится на 37. Вот пример первого случая:

А	В	С	А	В	С	A	В	С
9	8	4	7	6	3	2	5