Олимпиадная задача: кто выиграет в перестановке шариков в луночках? Теория чисел и алгоритмы
Задача
Есть длинный ряд луночек. В трёх из них лежит по шарику. Игроки по очереди делают ход: берут один из крайних шариков и перекладывают в свободную луночку между двумя другими. Тот, кто не может сделать ход, считается проигравшим. Кто – начинающий игру или ходящий вторым – победит при правильной игре при показанных на рисунках первоначальных расположениях шариков?
а) 
б) 
в) 
г) Разберите общий случай: между крайними шариками и средним имеется N и K пустых луночек.
Решение
г) Назовём положение шариков удачным, если какое-то из чисел N, K нечётно. Заметим, что:
1) любой ход из неудачного положения приводит к удачному;
2) при всяком удачном положении возможен ход, приводящий к неудачному положению.
Действительно, в неудачном положении числа N и K чётны. После перестановки шарика один из промежутков (скажем, длины K) исчезает, а второй разбивается на два, сумма длин которых равна N – 1 . Поскольку сумма длин нечётна, одно из слагаемых нечётно, то есть положение стало удачным.
В удачном положении из чисел N и K хотя бы одно нечётно (скажем, N). Возьмём шарик, не являющийся границей промежутка длины N и поставим его в лунку рядом с любым из имеющихся (такой ход возможен, так как N > 0). Мы получим неудачное положение: расстояния между шариками 0 и
N – 1.
Отсюда видно, что удачные положения выигрышные, а неудачные – проигрышные.
Ответ
а), в) Начинающий; б) второй; г) начинающий побеждает тогда и только тогда, когда хотя бы одно из чисел N, K нечётно.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь