J + E = 10,
I + D + 1 = E,
H + C = 10 + D,
G + 1 = С,
F = 9.
Закончите вы с помощью программы.
Головоломка 11.
Обозначим через ai цифры исходного числа, bi — цифры результата, ki — цифры «в уме»:
3ai + ki = bi + 10ki+1.
Сумма всех ai равна 45, как и сумма всех bi. Обозначим через K сумму всех ki:
3*45 + K = 45 + 10*K дает К = 10.
Мы знаем, что дает «в уме» каждая цифра:
1 дает 0, 2 дает 0, 3 дает 0 или 1 в зависимости от того, что хранится «в уме» над 3.
4 дает 1, 5 дает 1, 6 дает 1, потому что не может случиться 3*6 + 2, что давало бы «в уме» 2, но цифру единиц 0;
7, 8 и 9 дают 2.
Для того, чтобы сумма величин «в уме» была равна 10, нужно, чтобы 3 давало 1 «в уме». Так как 3*3 + 1 (с цифрой единиц, равной 0) случиться не может, то нужно, чтобы «в уме» над 3 было 2. Следовательно, 3 стоит слева от 7, 8 или 9. В частности, 3 не может стоять на правом конце.
Остальное просто, если вы будете следовать методу, указанному в разделе «Условия». Вот таблица:
Потребуем, чтобы 9 было справа; следовательно, вычеркнем 9 из этой таблицы, оставив его только в столбце, соответствующей тому, что «в уме» 0. Цифра 3 требует 2 «в уме», чтобы дать 1. Вычеркнем остальные 3 в таблице. Цифра 9 не может быть получена иначе как с помощью 6 и 1 «в уме». Другие 6 вычеркиваем. Цифра 8 получается из 2 при 2 «в уме». Нужно взять 3 числа в первом столбце, так что нужно еще одно не равное ни 2, ни 3. Их нужно 4 в среднем столбце, так что нужно еще 3 числа, ре равных 6, которые нужно взять среди цифр 7, 4, 1, 8, 5. Два последних числа должны быть взяты из столбца с нулем «в уме». Когда эти числа среди всех возможных будут выбраны, останется расположить их в соответствии с тем, что должно быть для них «в уме». Эту программу сделать легко.
Головоломка 12.
Если число a1a2…ap (представленное как последовательность цифр) кратно 3, то и a1 + а2 + … + ap кратно 3. Сумма кубов цифр равна
a13 + а23 + … + ap3.
Нужно показать, что это число также кратно 3. Действуйте по индукции по числу слагаемых. Предположим, что для p = n − 1 членов
a13 + а23 + … + ap3 = (a1 + … + ap)3 по модулю 3; тогда равенство
(a1 + … + ap + an)3 = (a1 + … + ap)3 + an3 + 3 (…)
доказывает наше утверждение для n слагаемых.
Возьмите число с k цифрами. Сумма кубов его цифр ограничена величиной k*93. Но исходное число не может быть меньше, чем 10k−1. Следовательно, достаточно, чтобы 10k−1 было больше, чем k*729, что очевидным образом выполняется при k = 5. Но эта оценка слишком пессимистична.
Головоломка 14.
Число, полученное при обращении порядка цифр, равно
1000d + 100c + 10b + a,
и разность этих двух чисел равна
999 (a − d) + 90 (b − c).
Числа a, b, c, d были расположены в невозрастающем порядке, и они не все равны между собой, так что a строго больше d и a − d не равно нулю. Все остальное просто.
Головоломка 16.
Единственное, что до сих пор еще не сказано — это способ определять, становится» ли последовательность периодической. Метод Полларда был основан на первой стратегии. Мы выясняем, существует ли ai с a2i = ai. Но вычисление f(x) = x2 − 1 по модулю n — дорогое вычисление. Брепт улучшил этот метод, предложив использовать вторую стратегию.
Головоломка 17.
Эта программа основана на следующих результатах:
если b нечетно, n четно, то n делится на b тогда и только тогда, когда n/2 делится на b;