Простейшие игры, поиск выигрышной стратегии
Два игрока играют в игру: в кучке лежит 5 спичек; Игроки по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Кто выиграет при правильной игре?
Для решения данной задачи начнем перебирать все варианты, затем построим дерево ходов. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3). Если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну. Если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну.
Построим дерево, чтобы убедиться в правильности наших рассуждений.
Действительно при правильной игре выигрывает первый игрок. Для этого ему нужно своим первым ходом убрать 1 спичку.
На столе лежат 25 спичек. Играют двое. Играющие по очереди могут взять от одной до четырех спичек. Выигрывает тот, кто берет последние(юю) спички(у). Для какого игрока существует выигрышная стратегия?
Победит тот игрок, которому достанутся последние 1-4 спички. Будем считать эти позиции выигрышными (в). Если же игроку достается 5 спичек, то любым своим ходом он обеспечивает победу сопернику, считаем такую позицию проигрышной (п): 
Выигрышная стратегия существует для второго игрока. Для этого он должен дополнять ход первого до 5 спичек (если первый взял одну, второй берет четыре и т.п.). Тогда после первого хода второго игрока останется 20 спичек, затем 15,10,5 и 0 – первый проиграл.
На столе лежат 25 спичек. Играют двое. Играющие по очереди могут взять 1,2 или 4 спички. Выигрывает тот, кто берет последние(юю) спички(у). Для какого игрока существует выигрышная стратегия?
Выигрышная стратегия существует для первого игрока. Для этого он должен ставить противника в проигрышную позицию, т.е. брать столько спичек, чтобы осталось кратное трем количество. 
Двое по очереди ломают шоколадку 5x8. За ход можно разломать любой кусок по прямой линии между дольками. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?
Долек всегда будет \(5\cdot8=40\) штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов. Поэтому последний (39-й) ход был обязательно ходом первого (его ходы - первый, третий и все с нечетными номерами) — и первый выиграл. Можем сделать вывод, что первый всегда выигрывает.
Имеется три кучки камней: в первой - 10, во второй - 15, в третьей - 20. За ход можно разбить любую кучку на две меньшие. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Количество возможных ходов для раскладывания кучек: \(45 - 3 = 42\). Поэтому, как бы ни ходил первый игрок, при его ходе всегда будет четное число кучек. При ходе же второго игрока количество кучек будет всегда нечетно. Значит, победит первый игрок, так как по окончании игры всегда остается ровно 45 кучек по одному камню в каждой.
Двое по очереди кладут пятаки на круглый стол так, чтобы они не накладывались друг на друга и не выступали за край стола. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Нам нужно найти такую последовательность ходов, которая позволила бы, глядя на ходы соперника, делать ходы, которые привели бы к победе. Стол круглый, поэтому первый ход — положить пятак в центр доски. Далее ходим по симметрии, относительно центра стола. Следовательно, первый игрок выиграет.
Имеются две кучки конфет: в одной — 20, в другой — 21. За ход нужно съесть все конфеты в одной из кучек, а вторую разделить на две необязательно равные кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?
Простейшая выигрышная позиция для того игрока, кто ее создал: это 1 и 1. Понятно, что в этом случае побеждает тот, кто ходит вторым, так как у первого игрока нет хода.
Очевидно, что позиция 2 и 1 выигрышная для первого и проигрышная для второго.
Если 3 и 1, тогда второй вновь с победой, как несложно убедиться простой проверкой, так как есть ровно два хода.
Когда в кучках 3 и 2, победа у первого (убираем 3, делим 2).
Если же 3 и 3, тогда победа вновь возвращается ко второму, что можно показать простым перебором.
Замечаем закономерность: если в каждой из кучек по нечетному числу конфет, тогда позиция выигрышная для второго.
Если же хотя бы в одной из кучек четное число конфет, то такая позиция выигрышная для первого.
Несложно понять, что когда в обеих кучках по нечетному числу конфет, то за один ход нельзя получить такую же позицию, так как при разделении любого нечетного числа на два слагаемых одно из них будет четным. Однако если хотя бы в одной из кучек четное (ненулевое) число конфет, то ее несложно разбить на два нечетных слагаемых. Таким образом мы можем разбить все позиции на выигрышные и проигрышные с учетом того, сколько конфет в кучках. И задача выигрывающего делать ход на выигрышные позиции.
После этого уже понятно, кто выиграет в данной по условию игре и как ему этого добиться.
Делим все возможные ходы на «выигрышные» и «проигрышные». Если после разбиения получились две кучки с нечетным числом конфет, тогда назовем такую позицию «выигрышной», а все остальные — «проигрышные».
Стратегия победителя заключается в том, что он делает ход на «выигрышные» поля. Так как первый может сделать ход на «выигрышное» поле, а хода с одного «выигрышного» поля на другое нет, и с любого «проигрышного» поля за один ход можно попасть на «выигрышное», то побеждает начинающий. Своим первым ходом он может съест кучку из 21 конфеты, а кучу с 20 конфетами разделить на две, в которых нечетное количество конфет в обеих кучках (например, 19 и 1). Заметим, что последняя позиция, когда две кучки, по одной конфете в каждой, выигрышная, т. е. последний ход сделает первый.
