Программирование игр и головоломок

a_n³ + 3 (…)

доказывает наше утверждение для n слагаемых.

Возьмите число с k цифрами. Сумма кубов его цифр ограничена величиной k*9³. Но исходное число не может быть меньше, чем 10^{k ?1}. Следовательно, достаточно, чтобы 10^k?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.

Единственное, что до сих пор еще не сказано — это способ определять, становится» ли последовательность периодической. Метод Полларда был основан на первой стратегии. Мы выясняем, существует ли a_i с a_2i = a_i. Но вычисление f(x) = x² ? 1 по модулю n — дорогое вычисление. Брепт улучшил этот метод, предложив использовать вторую стратегию.

Головоломка 17.

Эта программа основана на следующих результатах:

если b нечетно, n четно, то n делится на b тогда и только тогда, когда n/2 делится на b;

нечетное n делится на b тогда и только тогда, когда n ? b делится на b. Но n ? b четно.

Для n = 2⁷⁷ ? 3 и b = 7 вы получаете:

Число n нечетно. Рассматриваем n ? b = 2⁷⁷ ? 10. Оно делится на 2: получаем 2⁷⁶ ? 5.

Это число нечетно: (2⁷⁶ ? 5) ? 7 = 2⁷⁶ ? 12.

Делим на 4: 2⁷⁴ — 3.

Получаем ту же самую задачу, в которой показатель уменьшен на 3. Так как 77 = 3*25 + 2, то мы таким образом доходим до 2² — 3 = 1, которое не делится на 3. Вряд ли вас слишком утомит доказательство того, что 2ⁿ ? 3 никогда не делится на 7…

Головоломка 18.

Я не в состоянии рассказать вам, как я получил эту программу, это — очень долгая история, связанная с разложением целых чисел на множители. Может быть, когда-нибудь я ее и опубликую. Следовательно, будем разбираться в том, что нам дано — в тексте программы.

Начнем с нечетного n. В соответствии с инициализацией программы n = 4p ? 1, где p четно. В противном случае уже последует ответ «НЕТ». Следовательно, рассмотрите нечетное n, являющееся полным квадратом и, следовательно, квадратом нечетного числа 2k + 1;

(2k + 1)² = 4k² + 4k + 1 = 4k (k + 1) + 1.

Так как k (k + 1) — произведение двух последовательных целых чисел, и из двух последовательных целых чисел всегда есть хотя бы одно четное число, получаем простой, но интересный результат: любой квадрат нечетного числа сравним с 1 по модулю 8. Таким-образом, при n отличном от 1 по модулю 8 инициализирующая часть программы выводит, что n не является точным квадратом.

Посмотрим теперь, что происходит внутри цикла. Делим p на 2, и если результат четен, мы удовлетворяемся тем, что умножаем a на 2. При этом действии произведение a*p остается постоянным. Поэтому кажется вероятным, что в цикле существует инвариантная величина, запись которой содержит a*p в предположении, что p четно.

Если после деления p на 2 результат оказывается нечетным, то мы вычитаем из этого результата a/2 + b. Обозначим новые значения a, b, p через а', b', p' соответственно:

а' = 2*а, p' = p/2 ? а/2 ? b, b' = a + b.

Для этих значений получаем:

a'*p' = a*p ? a² ? 2a*b = а*р ? (а + b)² + b² = а*р ? b'² + b².

Это, наконец, дает

а'*p' + b'² = а*р + b².

Инвариантной величиной цикла оказывается, таким образом, сумма ар + b², причем p остается четным. Это обеспечивается тем, что в случаях, когда p/2 нечетно, мы вычитаем нечетные b из нечетного p/2. Что касается b, то он нечетен потому, что он начинается со значения 1 и к нему прибавляются только четные значения а.

В начале а = 4, p (целая часть дроби (n ? 1)/4) четно, b = 1, так что ар + b² = n.

Наконец, a, начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.

Тогда при переходе от a, b, p к a', b', p' либо

b' = b, а' = 2*а, так что если b < а, то и b' < а';