Урок 18
§11.2. Знакомство с теорией игр

11.2. Знакомство с теорией игр (Пример 2)

Пример 2. А эта задача из открытого банка заданий ЕГЭ по информатике (fipi.ru).

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.

За один ход игрок может выполнить одно из следующих действий:

• добавить в кучу один камень (+ 1);
• добавить в кучу два камня (+ 2);
• увеличить количество камней в куче в 3 раза (х 3).

Например, имея кучу из 5 камней, за один ход можно получить кучу из 6, 7 или 15 камней.

У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 46 или больше камней. Будем считать, что в начальный момент в куче S камней, 1 ≤ S ≤ 45.

Выясним, при каких значениях числа S Петя может выиграть первым ходом.

Если S = 45, то, добавив в кучу один камень (+ 1), два камня (+ 2) или утроив количество камней в ней (х 3), Петя становится победителем.

Если S = 44, то стать победителем можно, если добавить в кучу два камня (+ 2) или утроить количество камней в ней (х 3).

Если S = 43, то Петя становится победителем, утроив количество камней в куче (х 3). Также можно действовать для любого S ≥ 16 (16 х 3 = 48, 15 х 3 = 45).

Итак, Петя может выиграть, если S = 16, ..., 45 — это его выигрышные позиции. Для выигрыша Пете достаточно увеличить количество камней в 3 раза.

При меньших значениях S за один ход нельзя получить кучу, в которой будет 46 или более камней.

Если же в куче будет 15 камней, то после любого хода Пети своим первым ходом может выиграть Ваня. Действительно, при S = 15 после первого хода Пети («Ход П») в куче будет 16, 17 или 45 камней.

Любой из этих случаев является выигрышным для делающего ход Вани («Ход В»), которому для победы достаточно увеличить количество камней в 3 раза (рис. 3.19).

Рис. 3.19. Позиция 15 — выигрышная для Вани

Теперь попробуем определить значения S, при которых у Пети будет выигрышная стратегия, причём Петя не сможет выиграть первым ходом, но сможет выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.

Мы выяснили, что S = 15 — проигрышная позиция для любого игрока. Если Петя своим первым ходом сможет перевести в неё Ваню, то что бы ни делал последний, сам он выиграть не сможет, но переведёт в выигрышную позицию своего соперника. 15 камней Петя может получить при S = 14 (+ 1), S = 13 (+ 2) или S = 5 (х 3). Других вариантов для S нет (рис. 3.20).

Рис. 3.20. Позиции 5, 13, 14 — выигрышные для Пети

Представим всю информацию на числовой линейке:

Cкачать материалы урока