Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. Первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в два раза. Игра заканчивается, когда суммарное количество камней в кучах становится не менее 59. Побеждает игрок, сделавший последний ход. Выигрышная стратегия должна гарантировать победу независимо от ходов противника.
Для каждой указанной начальной позиции определите игрока, имеющего выигрышную стратегию, и опишите эту стратегию. Для позиции (5, 25) постройте дерево всех партий, возможных при реализации выигрышной стратегии; невозможные при этой стратегии партии в дерево включать нельзя.
Условие как в банке ФИПИ — открыть и сверить
| Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) бір камень либо увеличить количество камней в куче в екі раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы,
Игра завершается в тот момент, когда суммарное количество камней Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 59 или больше камней.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (4, 28), (5, 27), (7, 26) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.
Тапсырма 1. Для каждой из начальных позиций (4, 27), (6, 26) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Тапсырма 2. Для каждой из начальных позиций (4, 26), (5, 26), (6, 25) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию.
Тапсырма 3. Для начальной позиции (5, 25) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
| ||
| |
Это задание с развёрнутым решением: ответом считается шешімнің барысын жазу, жол емес. Шешімді қағазға жазып, салыстырыңыз с разбором — там каждый шаг с обоснованием.
Талдауды ашу1Мягкая — с чего смотретьдеңгей 1 из 3
Рассматривайте позиции как пары чисел и отмечайте позиции, из которых можно перейти в уже проигрышную позицию.
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Позиция является выигрышной, если из неё есть хотя бы один ход в проигрышную позицию; позиция является проигрышной, если все ходы ведут в выигрышные позиции.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
Последовательность ходов для позиции (5, 25) нужно строить только с учётом тех ходов Пети или Вани, которые входят в описанную выигрышную стратегию; остальные ветви дерева удаляются.