26. Игры

Простейшие игры, поиск выигрышной стратегии

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела 26. Игры:

Это старая версия каталога задач

Нажмите для перехода на новую версию

Решаем задачи
Задание 1 #12726

Два игрока играют в игру: в кучке лежит 5 спичек; Игроки по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Кто выиграет при правильной игре?

Показать решение

Для решения данной задачи начнем перебирать все варианты, затем построим дерево ходов. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3). Если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну. Если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну.

Построим дерево, чтобы убедиться в правильности наших рассуждений.

Действительно при правильной игре выигрывает первый игрок. Для этого ему нужно своим первым ходом убрать 1 спичку.

Ответ: Игрок 1
Задание 2 #12727

На столе лежат 25 спичек. Играют двое. Играющие по очереди могут взять от одной до четырех спичек. Выигрывает тот, кто берет последние(юю) спички(у). Для какого игрока существует выигрышная стратегия?

Показать решение

Победит тот игрок, которому достанутся последние 1-4 спички. Будем считать эти позиции выигрышными (в). Если же игроку достается 5 спичек, то любым своим ходом он обеспечивает победу сопернику, считаем такую позицию проигрышной (п):

Выигрышная стратегия существует для второго игрока. Для этого он должен дополнять ход первого до 5 спичек (если первый взял одну, второй берет четыре и т.п.). Тогда после первого хода второго игрока останется 20 спичек, затем 15,10,5 и 0 – первый проиграл.

Ответ: Второй игрок.
Задание 3 #12728

На столе лежат 25 спичек. Играют двое. Играющие по очереди могут взять 1,2 или 4 спички. Выигрывает тот, кто берет последние(юю) спички(у). Для какого игрока существует выигрышная стратегия?

Показать решение

Выигрышная стратегия существует для первого игрока. Для этого он должен ставить противника в проигрышную позицию, т.е. брать столько спичек, чтобы осталось кратное трем количество.

Ответ: Первый игрок.
Задание 4 #12729

Двое по очереди ломают шоколадку 5x8. За ход можно разломать любой кусок по прямой линии между дольками. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

Показать решение

Долек всегда будет \(5\cdot8=40\) штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 40. Значит, игра продолжалась ровно 39 ходов. Поэтому последний (39-й) ход был обязательно ходом первого (его ходы - первый, третий и все с нечетными номерами) — и первый выиграл. Можем сделать вывод, что первый всегда выигрывает.

Ответ: Первый игрок.
Задание 5 #12730

Имеется три кучки камней: в первой - 10, во второй - 15, в третьей - 20. За ход можно разбить любую кучку на две меньшие. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Показать решение

Количество возможных ходов для раскладывания кучек: \(45 - 3 = 42\). Поэтому, как бы ни ходил первый игрок, при его ходе всегда будет четное число кучек. При ходе же второго игрока количество кучек будет всегда нечетно. Значит, победит первый игрок, так как по окончании игры всегда остается ровно 45 кучек по одному камню в каждой.

Ответ: Первый игрок.
Задание 6 #12731

Двое по очереди кладут пятаки на круглый стол так, чтобы они не накладывались друг на друга и не выступали за край стола. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Показать решение

Нам нужно найти такую последовательность ходов, которая позволила бы, глядя на ходы соперника, делать ходы, которые привели бы к победе. Стол круглый, поэтому первый ход — положить пятак в центр доски. Далее ходим по симметрии, относительно центра стола. Следовательно, первый игрок выиграет.

Ответ: Первый игрок.
Задание 7 #12732

Имеются две кучки конфет: в одной — 20, в другой — 21. За ход нужно съесть все конфеты в одной из кучек, а вторую разделить на две необязательно равные кучки. Проигрывает тот, кто не может сделать ход. Кто выиграет?

Показать решение

Простейшая выигрышная позиция для того игрока, кто ее создал: это 1 и 1. Понятно, что в этом случае побеждает тот, кто ходит вторым, так как у первого игрока нет хода.

Очевидно, что позиция 2 и 1 выигрышная для первого и проигрышная для второго.

Если 3 и 1, тогда второй вновь с победой, как несложно убедиться простой проверкой, так как есть ровно два хода.

Когда в кучках 3 и 2, победа у первого (убираем 3, делим 2).

Если же 3 и 3, тогда победа вновь возвращается ко второму, что можно показать простым перебором.

Замечаем закономерность: если в каждой из кучек по нечетному числу конфет, тогда позиция выигрышная для второго.

Если же хотя бы в одной из кучек четное число конфет, то такая позиция выигрышная для первого.

Несложно понять, что когда в обеих кучках по нечетному числу конфет, то за один ход нельзя получить такую же позицию, так как при разделении любого нечетного числа на два слагаемых одно из них будет четным. Однако если хотя бы в одной из кучек четное (ненулевое) число конфет, то ее несложно разбить на два нечетных слагаемых. Таким образом мы можем разбить все позиции на выигрышные и проигрышные с учетом того, сколько конфет в кучках. И задача выигрывающего делать ход на выигрышные позиции.

После этого уже понятно, кто выиграет в данной по условию игре и как ему этого добиться.

Делим все возможные ходы на «выигрышные» и «проигрышные». Если после разбиения получились две кучки с нечетным числом конфет, тогда назовем такую позицию «выигрышной», а все остальные — «проигрышные».

Стратегия победителя заключается в том, что он делает ход на «выигрышные» поля. Так как первый может сделать ход на «выигрышное» поле, а хода с одного «выигрышного» поля на другое нет, и с любого «проигрышного» поля за один ход можно попасть на «выигрышное», то побеждает начинающий. Своим первым ходом он может съест кучку из 21 конфеты, а кучу с 20 конфетами разделить на две, в которых нечетное количество конфет в обеих кучках (например, 19 и 1). Заметим, что последняя позиция, когда две кучки, по одной конфете в каждой, выигрышная, т. е. последний ход сделает первый.

Ответ: Первый игрок.

1

Рулетка
Вы можете получить скидку в рулетке!