«Ферзя — в угол», «цзяньшицзы» и числа ФибоначчиМатулис А. Ю., Савукинас А. Ю. «Ферзя — в угол», «цзяньшицзы» и числа Фибоначчи // Квант. — 1984. — № 7. — С. 18—21, 29.
Текст статьиМатулис А. Ю., Савукинас А. Ю. «Ферзя — в угол», «цзяньшицзы» и числа Фибоначчи // Квант. — 1984. — № 7. — С. 18—21, 29.
Мы хотим познакомить вас с ещё одним, довольно неожиданным, применением
чисел Фибоначчи, о которых рассказано в статье И. М. Яглома на с. 15—18
этого номера журнала.
Мы увидим, что числа Фибоначчи помогают построить теорию древней
китайской игры «цзяньшицзы» и связанной с ней игры «ферзя — в угол». Этим
играм уже были посвящены статьи И. М. Яглома («Квант», 1971, № 2,
с. 4) и А. Орлова («Квант», 1977, № 3,
с. 41).
Здесь мы наметим несколько иной подход к решению той же задачи.
«Цзяньшицзы» и «ферзя — в угол»
Условия старинной игры «цзяньшицзы» (выбирание камней) таковы. Имеются
две кучки камней (или каких-нибудь других предметов, например спичек). Двое
играющих поочерёдно выбирают камни из этих кучек, причём за один ход можно
либо взять любое число камней из одной (какой угодно) кучки, либо поровну из обеих кучек сразу. Выигрывает тот, кто возьмёт последний камень.
Нам требуется найти правила беспроигрышной игры.
Пусть в одной кучке $a$ камней, во второй $b$ камней. Поставим в соответствие паре чисел $(a;b)$ клетку (бесконечной!) шахматной доски,
изображённой на рисунке 1 и поместим в клетку $(a;b)$ ферзя.
Рис. 1
Легко видеть, что каждому ходу в игре «цзяньшицзы» соответствует
некоторый ход ферзя: если игрок берёт $k$ камней из первой кучки, то ферзь
смещается на $k$ клеток влево; если игрок берёт $l$ камней из второй кучки —
ферзь смещается на $l$ клеток вниз; если же он берёт по $m$ камней из каждой
кучки, ферзь смещается на $m$ клеток по диагонали влево и вниз.
Итак, вместо игры «цзяньшицзы», можно рассматривать игру «ферзя — в угол»
с такими правилами: на бесконечной шахматной доске стоит ферзь. Два игрока
по очереди перемещают ферзя так, чтобы он приближался к угловому полю
$(0;0)$, т. е. за один ход разрешается смещать ферзя на любое число клеток
либо влево, либо вниз, либо по диагонали влево и вниз. Выигрывает тот, кто приведёт ферзя на поле $(0;0)$.
На рисунке 1 изображён ход игры, начинающейся в клетке $(12;14)$, где красные стрелки указывают ходы первого игрока, а синие — второго; выиграл
здесь первый игрок.
Понятно, что любой партии игры в «цзяньшицзы» соответствует некоторая
партия игры «ферзя — в угол», а партии игры «ферзя — в угол» — партия
«цзяньшицзы». Поэтому в дальнейшем мы будем говорить только об игре «ферзя —
в угол».
Проигрышные поля
На рисунке 2 изображена бесконечная шахматная доска, на которой некоторые
поля помечены знаком «$-$». Эти поля мы будем называть также проигрышными.
Нетрудно видеть, что если один из играющих будет каждым своим ходом
ставить ферзя на отмеченное поле, то он выиграет.
Рис. 2
В самом деле, ни из какого отмеченного поля нельзя перейти ходом ферзя на отмеченное поле. Напротив, из любого неотмеченного поля можно одним ходом
перейти на отмеченное. Поэтому, поставив ферзя на отмеченное поле, вы вынуждаете вашего противника сойти с отмеченного поля. Следующим ходом вы можете снова шагнуть на отмеченное поле (более близкое к полю $(0;0)$
и т. д. В конце концов вы шагнёте на отмеченное поле $(0;0)$ и выиграете.
Можно указать правило, по которому последовательно получаются отмеченные
поля. Сначала отмечается поле $(0;0)$. На это поле можно пойти с любого поля
вертикали $a=0$, горизонтали $b=0$ и диагонали $a=b$. Ближайшие
нерассмотренные поля — это поля $(1;2)$ и $(2;1)$. На одно из этих полей
можно пойти из любых полей вертикалей $a=1$, $a=2$, горизонталей $b=1$ и $b=2$ и диагоналей $b-a=1$, $a-b=1$. С самих же полей $(1;2)$ и $(2;1)$
можно пойти только на неотмеченные поля. Значит, эти два поля мы должны
отметить знаком «$-$». За этими полями следуют поля $(3;5)$ и $(5;3)$,
которые мы тоже должны отметить, и т. д.
Поскольку симметричные относительно главной диагонали поля $(a;b)$ и $(b;a)$ в этой игре совершенно равноправны (это особенно понятно при формулировке игры на языке кучек камней: ведь $(a;b)$ и $(b;a)$ — это,
разумеется, одно и то же положение, когда в одной кучке имеется $a$, а в другой $b$ камней), мы в дальнейшем будем изучать отмеченные поля, лежащие в верхней половине доски, т. е. поля, для которых $b\ge a$.
Положение первых из таких полей приведено в таблице; здесь $n$ — номер
проигрышного поля.
$$
\begin{gather*}
\small\textbf{Проигрышные поля}~\bm{(a_n;b_n)}\\
\begin{array}{|c|ccccccccccccc|}\hline
\vphantom{\dfrac00}n&0&1&2&3&4&5&6&7&8&9&10&11&12\\\hline
\vphantom{\dfrac00}a_n&0&1&3&4&6&8&9&11&12&14&16&17&19\\\hline
\vphantom{\dfrac00}b_n&0&2&5&7&10&13&15&18&20&23&26&28&31\\\hline
\end{array}
\end{gather*}
$$
Из описанного выше способа построения проигрышных полей следует, что на каждой вертикали, на каждой горизонтали и на каждой диагонали $b-a=n$
($n\in\mathbb{Z}$) имеется единственное отмеченное поле. При этом отмеченные
поля нижней половины доски симметричны отмеченным полям $(a_n;b_n)$. Это поля $(b_n;a_n)$.
Свойства чисел $\bm{(a_n;b_n)}$
Из таблицы видно, что наши числа $(a_n,b_n)$ обладают следующими
свойствами.
1. Каждое натуральное число входит в проигрышные пары один и только
один раз: либо в качестве $a_n$, либо в качестве $b_n$.
Это означает, что при любом натуральном $N$ либо на $N$-й горизонтали,
либо на $N$-й вертикали есть такое поле, причём эти два случая взаимно
исключают друг друга.
Учитывая теперь отмеченные поля нижней половины доски, получаемые заменой
$a\to b$, а $b\to a$, мы можем утверждать, что каждая вертикаль и каждая
горизонталь содержит одно и только одно отмеченное поле.
2. Для любого натурального $n$ имеется единственная проигрышная пара
$(a_n,b_n)$ такая, что выполняется равенство $b_n-a_n=n$.
Заметим, что на доске разность $b-a$ указывает расстояние от поля $(a;b)$
до диагонали доски, измеренное по вертикали или по горизонтали. Число $n$ мы будем считать совпадающим с номером соответствующей диагонали доски.
Свойства 1 и 2 обеспечивают то, что с каждого неотмеченного поля можно
одним ходом перейти на отмеченное, а всякий ход с отмеченного поля приводит
на неотмеченное, — т. е. обстоятельства, которые обеспечивают выигрыш
игроку, каждым своим ходом ставящему ферзя на отмеченное поле. (Если
начальное положение ферзя — отмеченное, то начинающий при правильной игре
второго игрока проигрывает, поэтому ему остаётся либо рассчитывать на ошибку
противника — весьма правдоподобную, если тот не владеет правилами
беспроигрышной игры, либо сразу капитулировать.)
В самом деле, с отмеченного поля все ходы ведут на неотмеченные поля.
Если же поле $(a;b)$ неотмеченное и $b-a=n\gt0$, то при $a\gt a_n$ (и,
значит, $b\gt b_n$) можно сразу перейти на поле $(a_n;b_n)$ ходом по диагонали. Если же $a\lt a_n$ (и $b\lt b_n$), то либо $a=a_k$, либо $b=b_k$.
В первом случае $k\lt n$ (ибо $a_k=a\lt a_n$) и $b_k-a=b_k-a_k=k\lt n=b-a$,
и поэтому $b\gt b_k$; из этого следует, что ферзя можно ходом по вертикали
перевести в точку $(a_k;b_k)$. Если же $a=b_l$ и тем более $l\lt n$, то $b\gt a=b_l\gt a_l$, и ферзя можно одним ходом перевести в отмеченное поле
$(b_l;a_l)$ нижней половины доски.
Точно так же проверяется, что из каждого неотмеченного поля нижней
половины доски ферзя можно одним ходом поставить на отмеченное поле.
Опишем ещё одно рекуррентное правило построения последовательности
$(a_n;b_n)$.
Пусть $a_0=0$, $b_0=0$. Пара $(a_n;b_n)$ определяется так: $a_n$ —
наименьшее из натуральных чисел, отсутствующих среди чисел $a_0$, $b_0$,
$a_1$, $b_1$, $a_2$, $b_2$, $\ldots$, $a_{n-1}$, $b_{n-1}$, а $b_n=a_n+n$.
Упражнение 1. Докажите, что последовательность
$(a_n;b_n)$ совпадает с построенной ранее последовательностью проигрышных
пар.
Описанные нами способы нахождения отмеченных пар довольно трудно
применять в конкретных ситуациях. Как, например, узнать, будет ли отмеченной
пара чисел $(a;b)$, если $a$ и $b$ очень велики (скажем, если $a$ и $b$
порядка миллиона)?
Частоты чисел $\bm{a_n}$ и $\bm{b_n}$ в ряду натуральных чисел
Заранее предупреждаем читателей, что в этом разделе мы ничего не будем
доказывать, а лишь ограничимся некоторыми интуитивными соображениями,
которые позволят нам угадать формулы для $a_n$ и $b_n$.
Пусть $N$ — натуральное число, $A_N$ — количество чисел $a_n$, не превосходящих $N$, а $B_N$ — количество не превосходящих $N$ чисел $b_n$.
Тогда отношения $p_N=\dfrac{A_N}N$, $q_N=\dfrac{B_N}N$ указывают долю
(«частоту») чисел $a_n$, соответственно $b_n$, среди всех натуральных чисел
от 1 до $N$. Ясно, что $p_N+q_N=1$.
Выпишем ряд первых чисел $p_N$ и $q_N$:
$$
\begin{alignat*}{2}
p_1&=1/1=1,&\quad q_1&=0/1=0;\\
p_2&=1/2=0{,}5,&q_2&=1/2=0{,}5;\\
p_3&=2/3\approx0{,}6667,&q_3&=1/3\approx0{,}3333;\\
p_4&=3/4=0{,}75,&q_4&=1/4=0{,}25;\\
p_5&=3/5=0{,}6,&q_5&=2/5=0{,}4;\\
p_6&=4/6\approx0{,}6667,&q_6&=2/6\approx0{,}3333;\\
p_7&=4/7\approx0{,}5714,&q_7&=3/7\approx0{,}4286;\\
p_8&=5/8=0{,}625,&q_8&=3/8=0{,}375;\\
p_9&=6/9\approx0{,}6667,&q_9&=3/9\approx0{,}3333;\\
p_{10}&=6/10=0{,}6,&q_{10}&=4/10=0{,}4;\\
p_{11}&=7/11\approx0{,}6364,&q_{11}&=4/11\approx0{,}3636.
\end{alignat*}
$$
Мы видим, что числа $p_N$ не слишком сильно отличаются друг от друга и «группируются» около величины, близкой к 0,3—0,4. Можно рассчитывать, что с ростом $N$ величины $p_N$ и $q_N$ стремятся к некоторым пределам, т. е. что существуют $\lim\limits_{N\to\infty}p_N=p$ и $\lim\limits_{N\to\infty}q_n=q$, причём числа $p$ и $q$ выражают частоту
(«плотность»), с какой встречаются в натуральном ряду числа $a_n$ и $b_n$
соответственно.
Если частота чисел $a_n$ в натуральном ряду равна $p$, то эти числа
составляют «$p$-ю долю» всех натуральных чисел, т. е. одно число $a$
в среднем приходится на $\dfrac1p=u$ натуральных чисел. При равномерном
распределении чисел $a_n$ разность между соседними числами $a_{i+1}$ и $a_i$
этой последовательности должна была бы составить $u$, т. е. числа $a_n$
должны образовывать арифметическую прогрессию $a_1=u$, $a_2=2u$, $\ldots$,
$a_n=nu$, $\ldots$ с разностью $u=\dfrac1p$.
Разумеется, в точности эти равенства выполняться не могут, так как числа
нашей прогрессии — не целые: однако если допустить, что распределение чисел
$a_n$ «довольно равномерно», то можно надеяться, что $a_i\approx iu$, $i=1$, 2, 3, $\ldots$, $n$, $\ldots$ Здесь знак $\approx$ означает лишь, что правая
часть не слишком сильно отличается от левой. Точно так же рассуждая, получим
для чисел $b_n$ приближённое равенство $b_i\approx iv$, $i=1$, 2, $\ldots$,
$n$, $\ldots$, где $v=\dfrac1q$.
Поскольку $p+q=1$, числа $u=\dfrac1p$ и $v=\dfrac1q$ удовлетворяют
условию
$$
\dfrac1u+\dfrac1v=1.
$$
По свойству 2, $b_n-a_n=n$. Поэтому в силу нашего допущения $b_n\approx nv$,
$a_n\approx nu$. Получим $nv-nu\approx n$, т. е. $v-u\approx 1$.
Поэтому естественно искать числа $u$ и $v$, исходя из системы
$\dfrac1u+\dfrac1v=1$, $v-u=1$, $u\gt0$, $v\gt0$. Решая эту систему,
получим
$$
u=\dfrac{1+\sqrt5}2,\quad v=\dfrac{3+\sqrt5}2.
$$
Из равенств $a_i\approx iu$ и $b_i\approx iv$ следует, что $b_i\approx\dfrac vua_i=ua_i$ (легко проверить, что $v=u^2$). Линия $b=ua$ и симметричная ей линия $b=\dfrac1ua$ в нижней половине доски изображены
пунктиром на рисунке 2, а принадлежащие этим линиям точки $a_i=ui$ и $b_i=vi$ отмечены кружочками. Эти точки, естественно, не совпадают с левыми
нижними углами проигрышных клеток доски. Однако все кружки на рисунке
принадлежат отмеченным клеткам. Естественно предположить, что $a_i=[ui]$, а $b_i=[vi]$, где квадратные скобки обозначают целую часть числа.
Основная теорема
Теперь мы можем забыть все соображения, которые привели нас к выписанным
выражениям для проигрышных полей $(a_n;b_n)$, и сразу сформулировать
следующую основную теорему.
Теорема 1. Пусть $u=\dfrac{1+\sqrt5}2$,
$v=u^2=u+1=\dfrac{3+\sqrt5}2$. Поле $(a;b)$, где $b\gt a$, в том и только в том случае является проигрышным, если существует натуральное число $n$
такое, что $a=[nu]$, $b=[nv]$. Если такого натурального $n$ не существует,
то позиция является выигрышной.
Доказательство. Рассмотрим последовательность точек
$$
(a_1;b_1),~(a_2;b_2),~\ldots,~(a_n;b_n),~\ldots,
$$
где $a_n=[nu]$, $b_n=[nv]$, и докажем, что для этой последовательности
выполнены свойства 1 и 2. Начнём со свойства 1.
Сначала убедимся в том, что все числа $a_1$, $b_1$, $a_2$, $b_2$,
$\ldots$ различны. Числа $a_i=[iu]$ различны, так как $u\gt1$. По той же причине ($v\gt1$) различны числа $b_j=[jv]$. Предположим, что какие-то два из чисел $a_i$ и $b_j$ совпадают. Это значит, что $[iu]=[jv]=k$. Поэтому
$iu=k+\delta_1$, где $0\lt\delta_1\lt1$, $jv=k+\delta_2$, где $0\lt\delta_2\lt1$. Разделив первое равенство на $u$, второе на $v$, а затем
сложив полученные равенства, приходим к равенству
$$
i+j=\dfrac ku+\dfrac kv+\dfrac{\delta_1}u+\dfrac{\delta_2}v=
k+\dfrac{\delta_1}u+\dfrac{\delta_2},
$$
из которого следует, что $$
0\lt i+j-k=\dfrac{\delta_1}u+\dfrac{\delta_2}\lt\dfrac1u+\dfrac1v=1,
$$
что невозможно, так как число $i+j-k$ — целое.
Теперь докажем, что каждое натуральное число встречается в последовательности $a_1$, $b_1$, $a_2$, $b_2$, $\ldots$, $a_n$, $b_n$,
$\ldots$
Пусть $N$ — произвольное натуральное число. Существует ровно
$\left[\dfrac Nu\right]$ чисел $a_i=[iu]$, меньших $N$. $\Big($Это числа с номерами $i=1$, 2, $\ldots$, $\left[\dfrac Nu\right].\Big)$ И ровно
$\left[\dfrac Nv\right]$ чисел $b_j=[jv]$, меньших $N$ $\Big($числа с номерами $j=1$, 2, $\ldots$, $\left[\dfrac Nv\right]\Big)$. Всего
чисел $a_i$ и $b_j$, меньших $N$, существует $\left[\dfrac
Nu\right]+\left[\dfrac Nv\right]$, а так как $\dfrac Nu$ и $\dfrac Nv$ — не целые числа,
$$
\dfrac Nu-1+\dfrac Nv-1\lt\left[\dfrac Nu\right]+\left[\dfrac Nv\right]\lt
\dfrac Nu+\dfrac Nv,
$$
т. е.
$$
N-2\lt\left[\dfrac Nu\right]+\left[\dfrac Nv\right]\lt N.
$$
Таким образом, $\left[\dfrac Nu\right]+\left[\dfrac Nv\right]=N-1$. Но это означает, что чисел вида $a_i$ и $b_j$, меньших $N$, имеется в точности
столько, сколько всего натуральных чисел, меньших $N$. Поскольку все числа
$a_i$ и $b_j$ различны, свойство 1 последовательности $(a_1;b_1)$,
$(a_2;b_2)$, $\ldots$, $(a_n,b_n)$, $\ldots$ доказано.
Свойство 2 доказывается без труда:
$$
b_n-a_n=[vn]-[un]=[(u+1)n]-[vn]-[un]=[nu]+n-[un]=n.
$$
Тем самым основная теорема полностью доказана.
Появляются числа Фибоначчи
Согласно основной теореме, для определения проигрышной пары с номером $n$
надо умножить $n$ на иррациональное число, заданное в виде бесконечной
десятичной дроби. Возможно, что такое умножение вам не понравится, особенно
если вы не имеете счётной машины. Как для определения проигрышных пар $(a_n;b_n)$ обойтись только действиями над натуральными числами?
Для этой цели может послужить такое свойство проигрышных пар:
3. Если $(a_n;b_n)$ — проигрышная napa, то пары $(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\le b_{n+1}-b_n\le3$ и $1\le
a_{n+1}-a_n\le2$.
Из результатов упражнения 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_i\lt 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_n+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.
После сделанных нами замечаний мы можем сформулировать следующую теорему,
дающую ещё одно описание всех отмеченных пар.
Теорема 2. Пусть $(a_n;b_n)$ — отмеченная пара. Если представить
натуральное число $n-1$ в виде суммы нeповторяющихся чисел Фибоначчи:
$$
n-1=f_{k_1}+f_{k_2}+\ldots+f_{k_i},
$$
то $$
a_n-1=f_{k_1+1}+f_{k_2+1}+\ldots+f_{k_i+1}
$$
или, иначе говоря, если $n-1$ есть сумма некоторых попарно различных чисел
Фибоначчи, то $a_n-1$ есть такая же сумма чисел Фибоначчи с номерами на единицу большими.
