Презентация - Задачи с выигрышной стратегией

Задачи с выигрышной стратегией (игровые задачи)
Учитель математики МОУ «Будогощская СОШ» Кондратьева Наталья Владимировна

Игровые задачи
В игровых задачах необходимо грамотно сформулировать стратегию игры и доказать, что она действительно ведёт к выигрышу. Обычный вопрос в таких задачах: «Кто и как выиграет при правильной игре?»

Некоторые типы игровых задач:
Игры-шутки; Игры с симметрией; Игры, в которых стратегия дополнение до фиксированного числа.

Игры-шутки
Задачи – шутки – это такие игры, где для построения выигрышного алгоритма можно ничего и не знать, так как в них результат будет зависеть не от игры партнеров, а от начальных условий. Однако для этого в решении нужно заметить, что это задача-шутка, а не какая-то другая, в которой нужно искать выигрышную стратегию. На самом деле, нет никакой стратегии (а нас хотят обмануть, что она якобы есть!) Просто... как бы кто ни ходил, либо всегда выиграет первый игрок (тот, кто начинает игру), либо всегда второй.

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

Решение:
Долек всегда будет 3x4=12 штук, а шоколадка в начале была одна. Заметим, что на каждом ходу один кусок шоколадки всегда разламывается на 2, т.е. количество различных кусков шоколадки увеличивается на 1. В начале это кол-во было равно 1, а в конце, как мы заметили, 12. Значит, игра продолжалась ровно 11 ходов. Поэтому последний (11-й) ход был обязательно ходом первого (его ходы - первый, третий и все с нечетными номерами) - и первый выиграл. Вот такая получилась шутка - как ни ходи, первый всегда выигрывает.

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

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

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

Решение:
И это задача-шутка. Количество возможных ходов для раскладывания кучек: 25-3=22. Выиграет второй игрок, так как необходимо сделать чётное количество ходов.

Игры с симметрией
Очень простой, но мощный и красивый метод решения игровых задач - симметричная стратегия. Суть его - делать каждый раз ход, симметричный ходу противника. Доказательство правильности нашей стратегии будет пользоваться тем, что после каждого нашего хода позиция симметрична: раз так, то если противник сумел сделать свой ход, то и мы сможем сделать ход, симметричный ему.

Задача 4.
На столе лежат две кучки конфет, по 9 в каждой кучке. Два игрока по очереди берут со стола любое количество конфет из какой-либо одной кучки. Выигравшим считается тот, кто берёт со стола последние конфеты. Кто и как выиграет при правильной игре? Решение

Выиграет второй игрок, который, делая ход, берёт то же количество конфет, что и начинающий игру, но из другой кучки, т. е. проводит симметричный ход.

Задача 5.
На столе лежат две кучки спичек: в одной – 50, в другой 30 спичек. Два игрока по очереди берут со стола любое количество спичек из какой-либо одной кучки. Выигравшим считается тот, кто берёт со стола последние спички. Кто и как выиграет при правильной игре? Решение

Выиграет начинающий игру. Первым ходом ему следует взять 20 спичек из первой кучки, а дальше отвечать на ход второго игрока симметричным ходом.

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

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

Задача 6.
В ромашке 8 лепестков. Два игрока по очереди отрывают лепестки. Можно отрывать 1 или 2, проигрывает тот, кто не может сделать ход. Как вы думаете: кто выигрывает при «правильной игре» тот, кто начинает или тот, кто ходит вторым? Решение

Выигрывает первый игрок! Он отрывает 2 лепесточка.. И после каждого хода соперника дополняет общее количество, оторванных лепестков до трёх ( т.е. 8-2=6; 6 делится на 3)

Задача 7.
В ромашке 10 лепестков. Два игрока по очереди отрывают лепестки. Можно отрывать 1 или 2, проигрывает тот, кто не может сделать ход. Как вы думаете: кто выигрывает при «правильной игре» тот, кто начинает или тот, кто ходит вторым? Решение

Выигрывает первый игрок! Он отрывает 1 лепесток.. И после каждого хода соперника дополняет общее количество, оторванных лепестков до трёх ( т.е. 10-1=9; 9 делится на 3)

Задача 8.
В ромашке 14 лепестков. Два игрока по очереди отрывают лепестки. Можно отрывать 1 или 2, но только соседние лепестки. Проигрывает тот, кто не может сделать ход. Как вы думаете: кто выигрывает при «правильной игре» тот, кто начинает или тот, кто ходит вторым? Решение

Выигрывает первый игрок! Он отрывает 2 лепесточка.. И после каждого хода соперника дополняет общее количество, оторванных лепестков до трёх ( т.е. 14-2=12; 12 делится на 3)

Задача 9.
Ладья стоит на поле a1. Играют двое. За ход разрешается сдвинуть ладью на любое число клеток вправо или на любое число клеток вверх. Выигрывает тот, кто поставит ладью на поле h8. Кто из игроков обладает выигрышной стратегией? (применение ИД)

Задача 10.
Игра начинается с числа 0. За ход разрешается прибавить к имеющемуся числу любое натуральное число от 1 до 9. Выиграет тот, кто получит число 100. Кто и как выиграет при правильной игре?

Вопросы для повторения:
В каких играх и задачах можно использовать выигрышную стратегию? Какие существуют правила выигрышной стратегии? Всегда ли в задачах указано, кто ходит первым?