Разделы 
Дополнительно
Задача по математике - 3776
2019-06-16 
Даны две кучки спичек. В начале в одной кучке $m$ спичек, в другой - $n$ спичек, $m > n$. Двое игроков по очереди берут из кучки спички. За один ход игрок берет из одной кучки любое (отличное от нуля) число спичек, кратное числу спичек в другой кучке. Выигрывает игрок, взявший последнюю спичку в одной из кучек.
а) Докажите, что если $m > 2n$, то игрок, делающий первый ход, может обеспечить себе выигрыш.
б) При каких $\alpha$ верно следующее утверждение: если $m > \alpha n$, то игрок, делающий первый ход, может обеспечить себе выигрыш?
Решение:
а) Пусть $m \geq 2n$. Покажем, что 1-й игрок может сделать в позиции $(m, n)$ такой ход, что полученная позиция станет (для 2-го игрока) проигрышной. Если позиция $(m - n, m)$ - проигрышная, то искомый ход: $(m,n) \rightarrow (m - n, m)$. Если же эта позиция выигрышная, то в ней существует ход, превращающий ее в проигрышную. Поскольку $m - n \geq n$, этот ход имеет вид $(m - n, n) \rightarrow (m - kn, n)$, где $k$ - некоторое натуральное число. Но тогда искомый выигрышный ход 1-го игрока: $(m, n) \rightarrow (m - kn, n)$.
Любопытно, что здесь удается доказать, что позиция $(m, n)$ при $m \geq 2n$ выигрышная, не предъявляя в явном виде выигрывающей стратегии.
б) Каждой позиции $(m, n)$, где $m \geq n$, поставим в соответствие точку $x = \frac{m}{n} \geq 1$ на числовой оси. При каждом ходе точка $x$ смещается на некоторое целое число к влево; если она попадает в отрезок $0 < x < 1$, то заменяется на обратную: $x \rightarrow \frac{1}{x}$ попадание в 0 - проигрыш. Отметим на оси отрезок $\left [ \frac{1}{ \beta}; \beta \right ]$; длины 1; $\beta - \frac{1}{ \beta} = 1$ при $\beta = \frac{1 + \sqrt{5}}{2}$. Точки $x = \frac{m}{n}$, лежащие внутри этого отрезка, соответствуют проигрышным позициям, правее него - выигрышным; в самом деле, из такой точки можно очередным (выигрывающим!) ходом попасть в этот отрезок; если $1 < x < \beta$, то очередной ход выводит из отрезка, а если $x = 1$, то ведет к проигрышу. Поскольку наибольшее число спичек в коробках уменьшается, через несколько ходов игра обязательно закончится.
Ответ: при $\alpha \geq \frac{1 + \sqrt{5}}{2}$.
Даны две кучки спичек. В начале в одной кучке $m$ спичек, в другой - $n$ спичек, $m > n$. Двое игроков по очереди берут из кучки спички. За один ход игрок берет из одной кучки любое (отличное от нуля) число спичек, кратное числу спичек в другой кучке. Выигрывает игрок, взявший последнюю спичку в одной из кучек.
а) Докажите, что если $m > 2n$, то игрок, делающий первый ход, может обеспечить себе выигрыш.
б) При каких $\alpha$ верно следующее утверждение: если $m > \alpha n$, то игрок, делающий первый ход, может обеспечить себе выигрыш?
Решение:
а) Пусть $m \geq 2n$. Покажем, что 1-й игрок может сделать в позиции $(m, n)$ такой ход, что полученная позиция станет (для 2-го игрока) проигрышной. Если позиция $(m - n, m)$ - проигрышная, то искомый ход: $(m,n) \rightarrow (m - n, m)$. Если же эта позиция выигрышная, то в ней существует ход, превращающий ее в проигрышную. Поскольку $m - n \geq n$, этот ход имеет вид $(m - n, n) \rightarrow (m - kn, n)$, где $k$ - некоторое натуральное число. Но тогда искомый выигрышный ход 1-го игрока: $(m, n) \rightarrow (m - kn, n)$.
Любопытно, что здесь удается доказать, что позиция $(m, n)$ при $m \geq 2n$ выигрышная, не предъявляя в явном виде выигрывающей стратегии.
б) Каждой позиции $(m, n)$, где $m \geq n$, поставим в соответствие точку $x = \frac{m}{n} \geq 1$ на числовой оси. При каждом ходе точка $x$ смещается на некоторое целое число к влево; если она попадает в отрезок $0 < x < 1$, то заменяется на обратную: $x \rightarrow \frac{1}{x}$ попадание в 0 - проигрыш. Отметим на оси отрезок $\left [ \frac{1}{ \beta}; \beta \right ]$; длины 1; $\beta - \frac{1}{ \beta} = 1$ при $\beta = \frac{1 + \sqrt{5}}{2}$. Точки $x = \frac{m}{n}$, лежащие внутри этого отрезка, соответствуют проигрышным позициям, правее него - выигрышным; в самом деле, из такой точки можно очередным (выигрывающим!) ходом попасть в этот отрезок; если $1 < x < \beta$, то очередной ход выводит из отрезка, а если $x = 1$, то ведет к проигрышу. Поскольку наибольшее число спичек в коробках уменьшается, через несколько ходов игра обязательно закончится.
Ответ: при $\alpha \geq \frac{1 + \sqrt{5}}{2}$.
