Рекомендация. Лучше это задание оформлять таблицей, для большего удобства проверяющих, а также во избежание помарок.
Пример задания.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи
камней. Игроки ходят по очереди, первый ход делает Петя. Назовём позицией игры указание количества камней в обеих кучах. Например, позиция (15,20) означает, что в первой куче 15 камней, а во второй — 20. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Например, имея количество камней в кучах (15,20), за один ход можно получить положение (16,20), (30,20), (15,21) и (15,30). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в обеих кучах (сумма) становится не менее 65. Победителем считается игрок, сделавший последний ход, то есть первым получивший положение, в котором сумма камней в кучах будет 65 или больше камней.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (4,31), (5,30), (7,29) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. Для исходных позиций (4,30) и (6,29) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Обоснуйте ответ.
2. Для исходных позиций (4,29), (6,28) и (5,29) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Обоснуйте ответ.
3. Для исходной позиции (5,28) укажите, кто из игроков выигрывает. Сколько ходов необходимо для выигрыша? Опишите выигрышную стратегию. Приведите дерево игры. Обоснуйте ответ. На рёбрах дерева указывайте, кто делает ход, в узлах — позицию игры.
Решение:
Зеленым выделен выигрыш Васи, желты - Пети
1. Построим таблицу:
Зеленым выделены ячейки, приводящие к победе. Так как речь идет о безошибочной игре и каждый игрок стремиться к победе, то можно сделать вывод, что выигрывает при любом ходе Пети Вася за свой первый ход. Из таблицы видно, что как бы не сходил Петя у Васи есть возможность выиграть, а так как игра безошибочная то Вася сходит именно так, чтобы победить. В задании указано, что необходимо описать выигрышную стратегию, поэтому изменим таблицу и сразу опишем её, давая правильно построенный ответ:
Дерево игры, оформленное в виде таблицы:
Таблица содержит все возможные варианты хода Пети, из неё видно, что при любом ходе Пети у Васи имеется ход, приводящий его в победе. Таким образом, Вася выиграет на своём первом ходе, вне зависимости от хода Пети.
Примечание. Для себя вы можете и должны построить первую, полную таблицу, однако в чистовик вы переносите её в измененном виде, то есть, таблицу 2
2. Таблица:
Итак, из таблицы видно, что при безошибочной игре выигрывает Петя за свой второй ход, однако не все варианты первого хода ему выигрышны. Поэтому изменим таблицу и получим такой ответ:
Дерево игры, оформленное в виде таблицы:
Таблица содержит все возможные варианты хода Васи, при выигрышной стратегии Пети. Из неё видно, что при любом ходе первом Васи у Пети имеется такой второй ход, который приведет его в победе. Таким образом, Петя выиграет на своём втором ходе.
3. Рассмотрим таблицу:
Итак, при безошибочной игре выигрывает Вася своим первым или вторым ходом. Оформленный ответ:
Дерево игры, оформленное в виде таблицы:
Таблица содержит все возможные варианты хода Пети, при выигрышной стратегии Васи. Из неё видно, что Вася выигрывает своим первым или вторым ходом при любом ходе Пети. Таким образом, Вася выиграет на своём первом или втором ходе.