ГДЗ по информатике, 11 класс, Босова, номер p161.5

План решения.

Данная игра относится к классу игр с полной информацией и конечным числом ходов. Чтобы определить наличие выигрышной стратегии, необходимо проанализировать позиции игры с конца (метод обратной индукции) или найти инвариант — свойство, которое сохраняется при оптимальной игре одного из игроков. В таких играх ключевым является деление общего количества предметов на сумму минимального и максимального хода (1+2=3).

Вычисление и анализ.

Рассмотрим правила: за один ход можно взять 1 или 2 спички. Выигрывает тот, кто забирает последнюю спичку (то есть оставляет противнику 0).

• Если на столе лежит 1 или 2 спички, текущий игрок может забрать все и выиграть. Это выигрышные позиции для того, чей ход.
• Если на столе лежит 3 спички, то независимо от того, возьмет игрок 1 или 2 спички, он оставит противнику 2 или 1 спичку соответственно. Противник заберет остаток и выиграет. Значит, позиция с 3 спичками — проигрышная для текущего игрока.
• Обобщим это наблюдение. Позиция является проигрышной для текущего игрока, если количество спичек кратно 3. Если же количество спичек не кратно 3, игрок может сделать так, чтобы после его хода осталось кратное 3 количество спичек.

Проверим начальную позицию: 107 спичек. 107÷3=35(остаток 2) Так как остаток равен 2, число 107 не делится на 3 нацело. Это означает, что первый игрок находится в выигрышной позиции. Его стратегия: на первом ходе взять ровно столько спичек, сколько составляет остаток от деления на 3, то есть 2 спички. После этого на столе останется 105 спичек (105 делится на 3). Далее, каким бы количеством спичек (1 или 2) ни взял второй игрок, первый игрок должен дополнить взятую партию до 3 (если второй взял 1, первый берет 2; если второй взял 2, первый берет 1). Таким образом, после каждого хода первого игрока на столе будет оставаться число спичек, кратное 3, пока не останется 0.

Проверка и вывод.

Убедимся в корректности стратегии. Первый игрок забирает 2 спички, оставляя 105. Второй игрок делает ход k∈{1,2}. Первый игрок забирает 3-k спичек. Суммарно за раунд убирается 3 спички. Так как 105 кратно 3, процесс завершится тем, что первый игрок заберет последние спички. Следовательно, выигрышная стратегия существует у первого игрока.