«Ферзя — в угол», «цзяньшицзы» и числа Фибоначчи

18

«Ферзя — в угол», «Цзяньшиццы» и числа Фибоначчи

А. Ю. МАТУЛИС, А. Ю. САВУКИНАС

Мы хотим познакомить вас с еще одним, довольно неожиданным, применением чисел Фибоначчи, о которых рассказано в статье И. М. Яглома на с. 15—18 этого номера журнала.

Мы увидим, что числа Фибоначчи помогают построить теории древней китайской игры «Цзяньшиццы» и связанной с ней игры «Ферзя — в угол». Этот игра уже был посвящены статью И. М. Яглома («Квант», 1971, № 2, с. 4) и А. Орлова («Квант», 1977, № 3, с. 41).

Здесь мы наметим несколько иной подход к решению той же задачи.

«Цзяньшиццы» и «Ферзя — в угол»

Условия старинной игры «Цзяньшиццы» (выбранные камней) таковы. Имеются две кучки камней (или каких-нибудь других предметов, например спичек). Двое играющих почередно выбирают камни из этих кучек, причем за один ход можно либо взять либо число камней из одной (какой уголно) кучки, либо поровну из обенных кучек сразу. Выигравает тот, кто возьмет последний камень.

Нам требуется найти правильное беспроигрывной игры.

Пусть в одной кучке a камней, во второй b камней. Поставим в соответствии пале чисел (a, b) клетку (бесконечной!) шахматной доски, изображенной на рисунке 1 и поместим в клетку (a, b) ферзя.

Легко видеть, что каждому ходу в игре «Цзяньшиццы» соответствует некоторый ход ферзя: если играк берет k камней из первого кучки, то ферзь смешается на k клеток влево; если играк берет l камней из второй кучки — ферзь смешается на l клеток вниз; если же он берет по m камней из каждой кучки, ферзь смешается на m клеток по диагонали влево и вниз.

Итак, вместе игры «Цзяньшиццы», можно рассматривать игру «Ферзя — в угол» с таким правилом: на бесконечной шахматной доске стоит ферзь. Два играка по очереди перемещают ферзя так, чтобы он приближался к угловому полю (0, 0), то есть за один ход разрешается смешать ферзя на любое число клеток либо влево, либо вниз, либо по диагонали влево и вниз. Выигравает тот, кто приведет ферзя на поле (0, 0).

На рисунке 1 изображен ход игры, начинающийся в клетке (12, 14), где красные стрелки указывают ходы первого играка, а сине — второго; выиграл здесь первый играк.

Понятно, что любой партии игры в «Цзяньшиццы» соответствует некоторой партии игры «Ферзя — в угол», а партии игры «Ферзя — в угол» — партия «Цзяньшиццы». Поэтому в дальнейшем мы будем говорить только об игре «Ферзя — в угол».

Проигрывные поля

На рисунке 2 изображена бесконечная шахматная доска, на которой неокторые поля помещены знаком «—». Эти поля мы будем называть также проигрывными. Нетрудно видеть, что если один из церающих будет каждым своим ходом ставить ферзя на отмещенное поле, то он выиграет.

В самом деле, ни из какого отмещенного поля нельзя перейти ходом ферзя на отмещенное поле. Например, из любого неотмещенного поля можно один ход перейти на отмещенное поле. Поэтому, поставив ферзя на отмещенное поле, вы вынуждаете вашого противника соисти с отмещенного поля. Следующим ходом вы можете снова шагнуть на отмещенное поле (более близкое к полю (0, 0) и так далее. В конце концов вы шагните на отмещенное поле (0, 0) и выиграете.

Можно указать правила, по которым последовательно получаются отмещенные поля. Сначала отмещается поле (0, 0). На это поле можноойти с любого поля вертикали a=0, горизонтали b=0 и диагонали a=b. Ближайшие нерассмотренные поля — это поля (1, 2) и (2, 1). На одно из этих полей можноойти из любых полей вертикали a=1, a=2, горизонтали

21

Основная теорема

Тепер мы можем забыть все сообразения, которые приведены нас к выписанным выражениям для проигрывших полей ($a_n, b_n$), и сразу сформировать следующую основную теорему.

Теорема 1. Пусть $u = \frac{1+\sqrt{5}}{2}$, $v = u^2 = u + 1 = \frac{3+\sqrt{5}}{2}$. Поле $(a, b)$, где $b > a$, в том и только в том случае является проигрывным, если существует натуральное число $n$ такое, что $a = [nu], b = [nv]$. Если такого натурального $n$ не существует, то позиция является выигрывной.

Доказательство. Рассмотрим последовательность точек

$$(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n), \dots,$$

где $a_n = [nu], b_n = [nv]$, и доказем, что для этой последовательности выполнены свойства 1 и 2 (см. с. 19). Начнем со свойства 1.

Сначала убедимся в том, что все числа $a_1, b_1, a_2, b_2, \dots$ различны. Числа $a_i = [iu]$ различны, так как $u > 1$. По той же причине ($v > 1$) различны числа $b_j = [jv]$. Предположим, что какие-то два из чисел $a_j$ и $b_j$ совпадают. Это значит, что $[iu] = [jv] = k$. Поэтому $iu = k + \delta$, где $0 < \delta_1 < 1$, $jv = k + \delta_2$, где $0 < \delta_2 < 1$. Разделив первое равенство на $u$, второе на $v$, а затем сложив полученные равенства, приходим к равенству

$$i + j = \frac{k}{u} + \frac{k}{v} + \frac{\delta_1}{u} + \frac{\delta_2}{v} = k + \frac{\delta_1}{u} + \frac{\delta_2}{v},$$

из которого следует, что

$$0 < i + j - k = \frac{\delta_1}{u} + \frac{\delta_2}{v} < \frac{1}{u} + \frac{1}{v} = 1,$$

что невозможно, так как число $i + j - k$ — целое.

Тепер доказем, что каждое натуральное число встречает в последовательности $a_1, b_1, a_2, b_2, \dots, a_n, b_n, \dots$.

Пусть $N$ произвольное натуральное число.

Существуетровно $\left[ \frac{N}{u} \right]$ чисел $a_i = [iu]$, меньше $N$. (Это числа с номерами $i = 1, 2, \dots, \left[ \frac{N}{u} \right]$.) Ировно $\left[ \frac{N}{v} \right]$ чисел $b_j = [jv]$, меньше $N$. (числа с номерами $j = 1, 2, \dots, \left[ \frac{N}{v} \right]$.) Всего чисел $a_i$ и $b_j$, меньше $N$, существуют $\left[ \frac{N}{u} \right] + \left[ \frac{N}{v} \right]$, а так как $\frac{N}{u}$ и $\frac{N}{v}$ — не целые числа, $\frac{N}{u} - 1 + \frac{N}{v} < \left[ \frac{N}{u} \right] + \left[ \frac{N}{v} \right] < \frac{N}{u} + \frac{N}{v}$, то есть

$$N - 2 < \left[ \frac{N}{u} \right] + \left[ \frac{N}{v} \right] < N.$$

Таким образом, $\left[ \frac{N}{u} \right] + \left[ \frac{N}{v} \right] = N - 1$. Но это означает, что чисел вида $a_i$ и $b_j$, меньше $N$, имеется в точности столько, сколько всего натуральных чисел, меньше $N$. Поскольку все числа $a_i$ и $b_j$ различны, свойство 1 последовательности $(a_1 b_1), (a_2 b_2), \dots, (a_n b_n)$, … доказано.

Свойство 2 доказывает без труда:

$$b_n - a_n = [vn] - [un] = [(u + 1)n] - [vn] - [un] = [nu] + n - [un] = n.$$

Тем самым основная теорема полностью доказана.

Появляется числа Фибоначчи

Согласно основной теореме, для определения проигрывной пары с номером $n$ надо умножить $n$ на irrationalное число, заданное в виде бесконечной десятичной дроби. Возможно, что такое умножение вам не понятно, особенно если вы не имеете счетной машины. Как для определения проигрывных пар $(a_n, b_n)$ обычно только действиями над натуральными числами?

Для этой цели может послужить такое свойство проигрывных пар:

3. Если $(a_n, b_n)$ — произвольная пара, то пары $(b_n - 1, a_n + b_n - 1)$ и $(b_n + 1, a_n + b_n + 2)$ — тоже произвольные.

При этом, исходя из начального поля $(0, 0)$ или первого поля $(1, 2)$, мы можем построить, пользоваться свойством 3, все проигрывные пары.

Наметим доказательство свойства 3.

Упражнение 2. Доказите, что для проигрывных пар $(a_n, b_n)$ и $(a_{n+1}, b_{n+1}): 2 \leq b_{n+1} - b_n \leq 3$, и $1 \leq a_{n+1} - a_n \leq 2$.

Из результатов упражнения 2 следует, что числа $b_n - 1$ и $b_n + 1$ не являются большими числами проигрывных пар. По свойству 1 существуют такие $k$ и $l$, что $a_k = b_n - 1$, $a_l = b_n + 1$. Посмотрим, чему равны $k$ и $l$.

По свойству 2, номер любой пары равенности между большим и меньшим из чисел этой пары.

С другой стороны, из свойства 1 следует, что номер любой отменной пары $(a_k, b_k)$ равенности ее меньше числа $a_k$ и количество всех неулевых $b_l < a_k$. При $a_l = b_n - 1$ количество чисел $b_l$, меньше числа $a_l$, равно $n - 1$. Это значит, что $k = b_n - 1 - (n - 1) = a_n$. Поэтому пара $(b_n - 1, b + a_n - 1)$ — отмеченная.

Упражнение 3. Доказите, что пара $(b_n + 1, a_n + b_n + 2)$ является отменной для всякой отменной пары $(a_n, b_n)$.

Упражнение 4. Доказите, что любая отменная пара $(a_n, b_n)$ может быть получена из пары $(0, 0)$ или пары $(1, 2)$ с помощью последовательного применения нескольких операций, описываемых свойством 3.

(Окончание см. на с. 29)