Question

Помогите решить даю 25 баллов Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может а) добавить в одну из куч (по своему выбору) два камня или б) увеличить количество камней в куче в два раза. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в обеих кучах всего будет 75 камней или больше.Задание 1. Для каждой из начальных позиций (10, 32), (11, 31) укажите, кто из игроков имеет выигрышную стратегию. Задание 2. Для каждой из начальных позиций (10, 31), (11,30), (12,30) укажите, кто из игроков имеет выигрышную стратегию. Задание 3. Для начальной позиции (10,29) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной выигрышной стратегии.​

Answer 1

Ответ:

Задание 1

Петя может выиграть при .

.

Задание 2

Возможное значение : . В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию . После хода Вани может возникнуть одна из четырёх позиций: , , , . В каждой из этих позиций Петя может выиграть одним ходом, утроив количество камней во второй куче.

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

Задание 3

Возможное значение : . После первого хода Пети возможны позиции: , , , . В позициях и Ваня может выиграть первым ходом, утроив количество камней во второй куче. Из позиций и Ваня может получить позицию . Эта позиция разобрана в п. . Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.

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

Answer 2

Давайте рассмотрим задачу поочередно.

Задание 1:

Начальные позиции:

1. (10, 32) 2. (11, 31)

Решение:

- В начальной позиции (10, 32), Петя может увеличить в первой куче количество камней до 20. Тогда Ваня не сможет предотвратить поражение, и Петя выигрывает.

- В начальной позиции (11, 31), Петя может увеличить во второй куче количество камней до 62, и он также выигрывает.

Итак, в обеих начальных позициях Петя имеет выигрышную стратегию.

Задание 2:

Начальные позиции:

1. (10, 31) 2. (11, 30) 3. (12, 30)

Решение:

- В начальной позиции (10, 31), Петя может добавить два камня в первую кучу, создав (12, 29), и тем самым выигрывает.

- В начальной позиции (11, 30), Петя также может добавить два камня во вторую кучу, создав (11, 32), и выигрывает.

- В начальной позиции (12, 30), Петя может увеличить количество камней в первой куче до 24, создав (24, 30), и выигрывает.

Итак, во всех трех начальных позициях Петя имеет выигрышную стратегию.

Задание 3:

Начальная позиция:

(10, 29)

Решение:

- В начальной позиции (10, 29), Петя может добавить два камня в первую кучу, создав (12, 29). Независимо от того, что делает Ваня, Петя всегда может поддерживать позицию (четное, нечетное) и выигрывать.

Таким образом, Петя имеет выигрышную стратегию в начальной позиции (10, 29).

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