Петр и Виталий нарисовали на песке сорок палочек и решили сыграть в игру. Они стирают палочки по очереди. Разрешается за один ход стереть 2, 3 или 4 палочки. Проигрывает тот, кто не сможет сделать ход. Первым ходит Петр. У кого из мальчиков есть беспроигрышная стратегия?

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

Разбор задачи:

Игра начинается с 40 палочек. Каждый из игроков по очереди стирает 2, 3 или 4 палочки за ход. Задача — определить, кто из игроков имеет беспроигрышную стратегию, если Петр начинает первым.

Метод решения:

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

• Выигрышная позиция — это такая ситуация, из которой игрок, который ходит, может всегда привести игру к победе, независимо от того, как будет действовать соперник.

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

Строим таблицу:

Начнём с того, что при 0 палочках игрок не может сделать ход и проигрывает. Следовательно, позиция с 0 палочками — это проигрышная позиция.

Дальше, начиная с 1 палочки, 2, 3 и 4 палочек, можно рассматривать следующие варианты:

• Если на текущем ходе можно перейти к проигрышной позиции соперника, то текущая позиция будет выигрышной.

• Если на текущем ходе все возможные ходы ведут в выигрышные позиции соперника, то текущая позиция будет проигрышной.

Разбор ходов:

1. При 1 палочке игрок не может сделать ход, значит, это проигрышная позиция.

2. При 2 палочках можно стереть 2 палочки и оставить 0, что является проигрышной позицией для соперника. Значит, 2 палочки — выигрышная позиция.

3. При 3 палочках можно стереть 3 палочки и оставить 0, это проигрышная позиция для соперника, значит, 3 палочки — выигрышная позиция.

4. При 4 палочках можно стереть 4 палочки и оставить 0, это проигрышная позиция для соперника, значит, 4 палочки — выигрышная позиция.

5. При 5 палочках можно стереть 2, 3 или 4 палочки, но ни один ход не приведёт к проигрышной позиции для соперника (например, стерев 2, останется 3 палочки, которые — выигрышная позиция для соперника). Следовательно, 5 палочек — проигрышная позиция.

И так далее, постепенно перебирая все количества палочек от 0 до 40. Если внимательно посчитать и проследить, получится, что все позиции, где количество палочек составляет число, которое не делится на 5 (то есть, не находится в диапазоне 5, 10, 15 и т.д.), будут выигрышными для текущего игрока, а все другие — проигрышными.

Кто имеет беспроигрышную стратегию?

Если мы рассматриваем 40 палочек, то 40 — это выигрышная позиция для Петра, потому что из неё он может перевести игру в такие позиции, где Виталий будет в проигрышной ситуации. Стратегия Петра будет заключаться в том, чтобы всегда оставлять Виталию число палочек, которое делится на 5 (например, 35, 30, 25 и так далее). Виталию не останется выбора, и он не сможет избежать проигрыша, если Петр будет действовать оптимально.

Ответ:

У Петра есть беспроигрышная стратегия, так как он может всегда переводить игру в проигрышные позиции для Виталия.