2014-06-08
Прямоугольная полоса размером $1 \times n (n \geq 4)$ составлена из единичных полей, занумерованных числами $1, 2, \cdots, n$. На полях с номерами $n – 2, n - 1, n$ стоит по одной фишке. Двое играют в следующую игру: каждый игрок своим ходом может перенести любую фишку на любое свободное поле с меньшим номером. Проигрывает тот, кто не может сделать очередного хода. Доказать, что начинающий может ходить так, чтобы наверняка выиграть.
Решение:
Разобьем все целые числа, начиная с двух, на непересекающиеся пары вида $(2k; 2k +1), k \in \mathbf{N}$. Тогда среди трех чисел $n, n-1, n-2$ два обязательно образуют пару. Начинающий должен первым ходом фишку, стоящую на поле с тем номером, который не попал в пару, переставить на поле с номером 1. После этого переставленная фишка двигаться уже не будет. Пусть другой игрок своим ходом переставил одну из фишек на некоторое поле $m$. Тогда первый игрок должен оставшуюся фишку поставить на папе $m – 1$ или $m + 1$ в зависимости от того, какое из этих чисел образует пару с номером $m$. Это всегда можно сделать, так как пары не пересекаются ни друг с другом, ни с числом 1. Действуя так же и далее, первый игрок не может проиграть. Поскольку игра обязательно закончится через конечное число ходов, то проиграет второй игрок.