Алёна и Ваня играют у новогодней ёлки, на которой висит 1234
шарика. Ребята ходят по очереди, первой ходит Алёна. Каждый игрок по очереди протягивает между двумя ещё не соединёнными шариками гирлянду. Игрок, после хода которого какая-то часть гирлянды замкнётся, проигрывает. Кто из ребят всегда может выигрывать независимо от того, как играет товарищ?
Ответы
Ответ:
(см. объяснение)
Пошаговое объяснение:
При рассуждениях будем считать, что оба игрока играют оптимально. Заметим, что если у нас имеется некоторая гирлянда, то нам нельзя соединять никакой из ее шариков с другими шариками из этой гирлянды, так как иначе получим цикл, то есть проигрыш. Тогда будем рассматривать кусок гирлянды, как объект, к которому можно только присоединять шарики, еще не состоящие в нем (или же присоединять другие объекты: другие куски гирлянды, которые также могу образовываться в процессе игры). Соответственно в результате такого присоединения получаем новый объект такого же типа, к которому вновь могут быть применены те же самые правила (присоединение шарика или другого объекта). Как мы присоединяем объект к объекту (то есть каким шариком к какому) нас не волнует. Но тогда объект фактически эквивалентен одному шарику, так как с ним можно делать только те же самые операции. Соответственно при оптимальной игре обоих игроков итогом будет один объект, все шарики которого будут его составляющими. Эта позиция очевидно проигрышная. Осталось только понять, кто из игроков в нее попадет. Как только что было сказано выше, позиция из одного шарика/объекта проигрышная. Из двух, напротив, выигрышная, так как ведет в проигрышную. Соответственно из трех проигрышная, поскольку ведет только в выигрышные позиции и так далее. Наблюдается чередование, откуда понятно, что для игры, в которой 1234 шарика победителем будет первый игрок (позиция выигрышная), то есть Алёна.
Задание выполнено!