Даны две кучки спичек. Вначале в одной кучке $m$ спичек, в другой — $n$ спичек, $m \gt n$. Двое игроков по очереди берут из кучки спички. За один ход игрок берёт из одной кучки любое (отличное от нуля) число спичек, кратное числу спичек в другой кучке. Выигрывает игрок, взявший последнюю спичку в одной из кучек.
Докажите, что если $m \gt 2n$, то игрок, делающий первый ход, может обеспечить себе выигрыш.
При каких $\alpha$ верно следующее утверждение: если $m \gt \alpha n$, то игрок, делающий первый ход, может обеспечить себе выигрыш?
А. Слинько
Всесоюзная математическая олимпиада школьников (XII, 1978 год, 9 класс)
Текущую ситуацию в игре будем описывать парой натуральных чисел $(i,j)$, где $i$ — число спичек в первой кучке, а $j$ — во второй.
а) В случае, когда $m\ge2n$, несложно доказать существование выигрышной стратегии для начинающего, не указывая её конкретно. Из ситуации $(m,n)$ мы можем сделать $\left[\dfrac mn\right]$ различных ходов:
$$
(m,n)\to(m-n,n),~(m-2n,n),~{\ldots},~(m-(q-1)n,n),~(m-qn, n),
$$
где $q=\left[\dfrac mn\right]$, т. е. $0\le m-qn\lt n$. Если ситуция $(m-qn, n)$ — проигрышная, то выигрышный ход: $(m,n)\to(m-qn,n)$. Если же ситуация $(m-qn,n)$ выигрышная, то предыдущая $(m-(q-1)n, n)$ — проигрышная, поскольку из неё можно пойти только в $(m-qn,n)$. (Заметим, что при $m\ge2n$ обязательно $q\ge2$, так что $q-1\ge1$.) В этом случае выигрышный ход: $(m,n)\to(m-(q-1)n,n)$.
б) Заметим, что «выигрышность» ситуации зависит только от отношения $\dfrac mn$, где $m$ и $n$ — первоначальные количества спичек в обеих кучках (поскольку при переходе с одной позиции на другую наибольший общий делитель чисел $m$ и $n$ сохраняется).
Отбросим теперь условие $m\gt n$. Тогда наша задача сводится к такой: рассортировать все рациональные числа на два класса: выигрышные числа $\alpha=\dfrac mn$ и проигрышные числа.
Очевидно, что ситуации $(m,n)$ и $(n,m)$ — одновременно выигрышные или одновременно проигрышные. Поэтому, если отношение $\dfrac mn$ отмечать на числовой оси, то точки $\alpha$ и $\dfrac1\alpha$ будут равноправными: из того, что точка $\alpha$ — выигрышная, следует, что и $\dfrac1\alpha$ — выигрышная, и наоборот.Заметим, что ход $(m,n)\to(m-kn,n)$ соответствует вычитанию из $\alpha=\dfrac mn$ целого числа $k$.
Ясно, что все целые числа $\alpha$ (а, следовательно, и обратные целым) будут выигрышными: в ситуации, когда $\dfrac mn$ — целое число, начинающий выигрывает за один ход, забирая все спички из большей кучки. Нетрудно сообразить, что в любой арифметической прогрессии с меньшим единицы (положительным) начальным членом и разностью 1 имеется ровно одна проигрышная точка. Из пункта а) следует, что все проигрышные числа меньше 2; поэтому проигрышные точки могут находиться только внутри интервала $\left(\dfrac12;2\right)$.
Докажем теперь, что все отличные от единицы рациональные точки некоторого отрезка $I\subset\left(\dfrac{1}{2};2\right)$ единичной длины являются проигрышными, и попробуем, найдя этот отрезок, указать выигрышную стратегию для начинающего. Легко понять, что отрезок $I$ должен быть замкнут относительно операции обращения: именно, если $\alpha\in I$, то и $\dfrac1\alpha\in I$. Пусть $\gamma\gt1$ — правый конец этого единичного отрезка. Тогда $\gamma-1$ — его левый конец и должно быть $\gamma-1=\dfrac1\gamma$. Отсюда находим, что $\gamma=\dfrac{\sqrt5+1}2$ (это число известно под названием «золотого сечения»). Рассмотрим ситуацию $(i,j)$ такую, что $\dfrac ij=\alpha\in(\gamma-1;\gamma)$ (рис. 6), причём $\dfrac ij\ne1$. Допустим, что $i\gt j$; тогда $\alpha\in(\gamma-1;\gamma)$. В этой ситуации у играющего имеется единственный ход $(i,j)\to(i-j,j)$, для которого
$$
\alpha'=\dfrac{i-j}j=\dfrac ij-1=\alpha-1\lt\gamma-1,
$$
т. е. этот ход приводит к ситуации с отношением $\alpha'$ вне интервала $(\gamma-1;\gamma)$. Кроме того, на этом ходе игра не кончается.
Рис. 6Рис. 7Рис. 8Рис. 9
Пусть теперь $\dfrac mn=\alpha\not\in(\gamma-1;\gamma)$ и $\dfrac mn\not\in\mathbb{Z}$ (случай, когда отношение $\dfrac mn$ — целое, описан выше); положим, для определённости, $m\gt n$. Найдётся такое $k\in\mathbb{Z}$, что $\dfrac mn-k\in(\gamma-1;\gamma)$, так что после хода $(m,n)\to(m-kn,n)$ мы получим ситуацию с отношением, находящимся в интервале $(\gamma-1;\gamma)$ и не равным единице (поскольку $\dfrac mn\not\in\mathbb{Z})$.
Отсюда получаем выигрушную стратегию для начинающего игрока. Если $\dfrac mn\in\mathbb{Z}$, то он выигрывает первым ходом. Если $\dfrac mn\not\in\mathbb{Z}$ и $\dfrac mn\not\in(\gamma-1;\gamma)$, то каждым своим очередным ходом он добивается того, чтобы отношение $\dfrac{m_k}{n_k}$ попадало в интервал $(\gamma-1;\gamma)$, после чего его противник может сделать единственный ход, приводящий снова к ситуации с отношением вне указанного интервала. Понятно, что в конце концов начинающий выигрывает. На рисунке 7 красные точки соответствуют выигрышным ситуациям $(m,n)$, чёрные — проигрышным.
Таким образом, утверждение пункта б) задачи верно при всех $\alpha\gt\gamma$ $\left(\gamma=\dfrac{\sqrt5+1}2\right)$.
Примечание редакции. При решении этой задачи, как это часто бывает не только в элементарной математике, но и в серьёзных математических исследованиях, нам очень помог «угаданный» ответ: в некоторый момент мы предположили, что все рациональные не целые точки некоторого интервала единичной длины — проигрышные, и после этого быстро довели исследование до конца. Но в этой задаче можно обойтись и без такого дополнительного шага: число $\gamma$ возникает в ней естественным образом из следующих рассуждений. Как уже было замечено, все проигрышные точки принадлежат интервалу $\left(\dfrac12;2\right)$. Легко сообразить также, что если точка $x\in(1;2)$ — проигрышная (выигрышная), то точка $x-1$ — выигрышная (проигрышная). Поэтому все точки интервала $\left(1;\dfrac32\right)$ — проигрышные, и нам остаётся исследовать точки интервала $\left(\dfrac32;2\right)$. Предположим, что точка $x\in\left(\dfrac32;2\right)$ — проигрышная. Тогда точки $x-1$ и $\dfrac1{x-1}$ — выигрышные, причём $\dfrac1{x-1}$ меньше 2 (но больше 1). Поэтому $\dfrac1{x-1}-1=\dfrac{2-x}{x-1}$ — проигрышная точка. Итак, если точка $x\in\left(\dfrac32;2\right)$ — проигрышная, то и точка $\dfrac{2-x}{x-1}$ — тоже проигрышная. Нарисуем график функции $\dfrac{x-1}{2-x}$ (рис. 8). На рисунке 8 показано, как по точке $x$ найти точку $\dfrac{x-1}{2-x}$. При преобразовании $x\to\dfrac{x-1}{2-x}$ есть неподвижная точка — корень уравнения $x^2-x-1=0$, принадлежащий интервалу $\left(\dfrac32;2\right)$ (это и есть число $\gamma$). Легко доказать, что если точка находится правее точки $\gamma$, то итерации (повторения) нашего преобразования рано или поздно выведут её за точку 2. (Одна из возможных схем доказательства приведена на рисунке 9: тангенс угла наклона чёрной прямой, проходящей через неподвижную точку $(\gamma;\gamma^2-\gamma-1)$, равен 2, а касательная к кривой $\dfrac{x-1}{2-x}$ идёт круче — убедитесь в этом.)
Поэтому все точки из интервала $(\gamma;2)$ — выигрышные и, следовательно, все точки из интервалов $(\gamma;\infty)$ и $\left(0;\dfrac1\gamma\right)$ — выигрышные. Аналогично, если предположить, что некоторая точка из интервала $\left(\dfrac32;\gamma\right)$ — выигрышная, то eё итерациями мы получим точку из интервала $\left(1;\dfrac32\right)$, откуда следует, что все точки из интервала $(1;\gamma)$ — проигрышные. Конечно, такое решение более громоздко. Однако зато оно и более поучительно!
