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

Арсак Жак

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

Если число a₁a₂…a_p (представленное как последовательность цифр) кратно 3, то и a₁ + а₂ + … + a_p кратно 3. Сумма кубов цифр равна

a₁³ + а₂³ + … + a_p³.

Нужно

показать, что это число также кратно 3. Действуйте по индукции по числу слагаемых. Предположим, что для p = n– 1 членов

a₁³ + а₂³ + … + a_p³ = (a₁ + … + a_p)³ по модулю 3; тогда равенство

(a₁ + … + a_p + a_n)³ = (a₁ + … + a_p)³ + 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' соответственно: