Жак Арсак - Программирование игр и головоломок
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;
нечетное n делится на b тогда и только тогда, когда n − b делится на b. Но n − b четно.
Для n = 277 − 3 и b = 7 вы получаете:
Число n нечетно. Рассматриваем n − b = 277 − 10. Оно делится на 2: получаем 276 − 5.
Это число нечетно: (276 − 5) − 7 = 276 − 12.
Делим на 4: 274 — 3.
Получаем ту же самую задачу, в которой показатель уменьшен на 3. Так как 77 = 3*25 + 2, то мы таким образом доходим до 22 — 3 = 1, которое не делится на 3. Вряд ли вас слишком утомит доказательство того, что 2n − 3 никогда не делится на 7…
Головоломка 18.
Я не в состоянии рассказать вам, как я получил эту программу, это — очень долгая история, связанная с разложением целых чисел на множители. Может быть, когда-нибудь я ее и опубликую. Следовательно, будем разбираться в том, что нам дано — в тексте программы.
Начнем с нечетного n. В соответствии с инициализацией программы n = 4p − 1, где p четно. В противном случае уже последует ответ «НЕТ». Следовательно, рассмотрите нечетное n, являющееся полным квадратом и, следовательно, квадратом нечетного числа 2k + 1;
(2k + 1)2 = 4k2 + 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 − a2 − 2a*b = а*р − (а + b)2 + b2 = а*р − b'2 + b2.
Это, наконец, дает
а'*p' + b'2 = а*р + b2.
Инвариантной величиной цикла оказывается, таким образом, сумма ар + b2, причем p остается четным. Это обеспечивается тем, что в случаях, когда p/2 нечетно, мы вычитаем нечетные b из нечетного p/2. Что касается b, то он нечетен потому, что он начинается со значения 1 и к нему прибавляются только четные значения а.
В начале а = 4, p (целая часть дроби (n − 1)/4) четно, b = 1, так что ар + b2 = n.
Наконец, a, начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.
Тогда при переходе от a, b, p к a', b', p' либо
b' = b, а' = 2*а, так что если b < а, то и b' < а';
либо
b' = а + b, а' = 2*а, что также сохраняет справедливость отношения а' < b'.
Следовательно, вот ситуация, которую цикл оставляет инвариантной:
n = а*p + b2;
а — степень двойки,
p четно,
b нечетно, b < а.
Кроме того, мы знаем, что при выходе из цикла p < а.
Если p равно нулю, то n = b2. Тогда мы видим, что n — квадрат числа b, которое выводится, и все закончено.
Но n может оказаться полным квадратом и тогда, когда p не нуль. Попробуем рассмотреть все возможные случаи. Положим n = r2 (r нечетно). Соотношение
r2 = ар + b дает
r2 − b2 = ар.
