Таблицы Брадиса

После этого хода остается параллелограмм,

После этого хода остается параллелограмм,

Элементы математики в задачах - Г. А. Мерзон

170                     Целые числа 2. Алгоритм Евклида

Пусть на каком-то ходу один из игроков (назовем его А) получил шоколадку в форме равнобедренной трапеции с меньшим основа­нием а и большим основанием Ъ (длина боковой стороны такой трапеции равна Ъ — а). Если А отломит треугольник, сторона которого меньше, чем Ъ — а, то другой игрок (назовем его Б) отломит треуголь­ник со стороной 1, и у игрока А не будет возможности сделать ход и он проиграет. Следовательно, в этой ситуации он должен отломать треугольник со стороной Ъ — а. После этого хода остается параллело­грамм, длины сторон которого равны а и Ъ — а.

Пусть игрок получил шоколадку в форме параллелограмма со сто­ронами а и Ъ, причем а < Ъ. Тогда по аналогичным соображениям он должен отломать треугольник со стороной а. После этого хода остается равнобедренная трапеция с основаниями Ъ — а и Ъ.

Таким образом, если в некоторый момент один из игроков получил шоколадку в форме параллелограмма со сторонами а и Ъ (а < Ъ), то через два хода он получит шоколадку в форме параллелограмма со сторонами а и Ъ — а. Если же один из игроков получил параллело­грамм с равными сторонами (т. е. ромб), то после его хода образуется треугольник.

Теперь приведем выигрышную стратегию для второго игрока при простом п: ему достаточно каждый раз отламывать кусок наибольше­го размера. Покажем, что эта стратегия приводит к выигрышу. Пусть первый игрок отломал треугольник со стороной к. После хода второго игрока образовался параллелограмм со сторонами к и п — к. Эти чис­ла взаимно просты, так как п — простое число. Далее, после каждого хода второго игрока будет получаться параллелограмм (пока в конце концов не получится ромб). Длины сторон этого параллелограмма взаимно просты. Значит, длины сторон ромба тоже взаимно просты. Но это означает, что получится ромб со стороной 1! Первый будет вынужден отломать от него треугольник со стороной 1, после чего второй выигрывает.