ВСОШ 2026, региональный этап, 9 класс, задача 3
( баллов) Петя и Вася играют в игру. В начале игры на столе лежат куч, состоящих из , , , , , , спичек соответственно. Ребята ходят по очереди, начинает Петя. Каждый из мальчиков своим ходом может взять любое ненулевое количество спичек из кучи с наибольшим количеством спичек (ровно из одной из таких куч, если их несколько). Выигрывает тот, кто заберёт последнюю спичку. Кто из мальчиков может играть так, чтобы гарантированно выиграть?
Ответ
Ответ. Петя.
Решение 1. Опишем стратегию, позволяющую Пете гарантированно забрать последнюю спичку. Для этого он на каждом ходу будет делать так, чтобы количество куч, содержащих максимальное количество спичек, было чётным (такие позиции будем называть правильными).
Докажем, что (1) перед каждым ходом Пети позиция будет неправильной и (2) он всегда сможет сделать ход, добившись правильной позиции. На первом ходу Пете достаточно взять спичку (из кучи с спичками), добившись правильной позиции.
Далее, если перед ходом Васи позиция правильная, то после его хода хотя бы одна из наибольших куч останется нетронутой, то есть наибольшее число спичек в куче не изменится. При этом их количество уменьшится ровно на , то есть позиция перед ходом Пети станет неправильной.
Пусть теперь перед ходом Пети позиция неправильная, причём в ней ровно кучек, содержащих максимальное количество спичек (число нечётно). Если , то Петя, например, забирает полностью одну из максимальных кучек, и позиция становится правильной (в ней максимальная кучка).
Если же , то пусть — число спичек в следующей за максимальной по величине непустой кучке, и пусть кучек, содержащих спичек, ровно (если других непустых кучек нет, то ). Если число чётно, то Петя просто заберёт наибольшую кучку (в частности, если других кучек нет, то Петя заберёт последнюю спичку). Если же нечётно, то Петя забирает столько спичек, чтобы в кучке осталось спичек, и таких кучек станет ; во всех случаях позиция снова станет правильной.
Итак, Петя всегда сможет поддерживать описанные свойства — в частности, Вася никогда не сможет забрать последнюю спичку (в правильной ситуации это невозможно). Так как число спичек уменьшается, это рано или поздно сделает Петя и выиграет.
Решение 2. Заметим, что игра закончится не более чем за ходов. Тогда у одного из мальчиков обязательно есть выигрышная стратегия. Предположим, что её нет у Пети; тогда она есть у Васи.
Пусть Петя первым ходом возьмёт спичку (из кучи с спичками), а в ответ Вася (по своей стратегии) возьмёт некоторое количество спичек из кучи с спичками. По нашему предположению, в получившейся позиции выигрывает Вася, то есть игрок, ходящий вторым.
Но этой же позиции мог добиться Петя, взяв на первом ходе спичку из кучи с спичками. Действуя по той же стратегии, он гарантированно выиграет. Полученное противоречие означает, что у Васи нет выигрышной стратегии, а значит, она есть у Пети.
Комментарий. Метод, описанный во втором решении, называется передачей хода.