Жак Арсак - Программирование игр и головоломок

Потребуем, чтобы 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.

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

a 1 3+ а 2 3+ … + a p 3.

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

a 1 3+ а 2 3+ … + a p 3= ( a 1+ … + a p ) 3по модулю 3; тогда равенство

( a 1+ … + a p + a n ) 3= ( a 1+ … + a p ) 3+ a n 3+ 3 (…)

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

Возьмите число с k цифрами. Сумма кубов его цифр ограничена величиной k *9 3. Но исходное число не может быть меньше, чем 10 k−1. Следовательно, достаточно, чтобы 10 k−1было больше, чем k *729, что очевидным образом выполняется при k = 5. Но эта оценка слишком пессимистична.

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

Число, полученное при обращении порядка цифр, равно

1000 d + 100 c + 10 b + a ,

и разность этих двух чисел равна

999 ( a − d ) + 90 ( b − c ).

Числа a , b , c , d были расположены в невозрастающем порядке, и они не все равны между собой, так что a строго больше d и a − d не равно нулю. Все остальное просто.

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

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

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

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

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

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

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

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

Это число нечетно: (2 76− 5) − 7 = 2 76− 12.

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

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

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

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

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

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

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

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