ВсОШ 2019, 10 класс, задача 2
Паша и Вова играют в следующую игру, делая ходы по очереди. Начинает Паша. Изначально перед мальчиками лежит большой кусок пластилина. За один ход Паша может разрезать любой из имеющихся кусков пластилина на три части (не обязательно равные). Вова своим ходом выбирает два куска и слепляет их вместе. Паша побеждает, если в некоторый момент среди имеющихся кусков пластилина окажется кусков одинаковой массы. Может ли Вова помешать Паше победить?
(Р. Ефремов, Д. Белов)
Ответ.
Нет, не может.
Первое решение.
Приведём алгоритм, позволяющий Паше победить. Пусть масса исходного куска равна кг. Паша каждым ходом будет отрезать от самого большого из имеющихся кусков два куска массой по г. Докажем, что не позже, чем через ходов Паша победит. Предположим, что это не так. Рассмотрим последовательных ходов Паши. Всего за эти ходов появятся кусков массой г. Если бы каждым своим ответным ходом Вова слеплял два куска массой по г, то в итоге получилось бы кусков массой г, и Паша бы победил. Значит, по крайней мере один раз Вова не слепит между собой два куска массой г. Поэтому спустя ходов Паши и ходов Вовы количество кусков массой г увеличится хотя бы на . Разобьём ходов Паши на сотни последовательных. По доказанному выше, после каждой сотни последовательных ходов Паши и ответных ходов Вовы количество кусков массы г увеличивается хотя бы на . Таким образом, через таких сотен последовательных ходов количество кусков массой г увеличится хотя бы на . Поэтому Паша так или иначе победит.
Второе решение.
Опять же положим массу исходного куска равной кг. Приведём другой алгоритм действий Паши. Пока это возможно, он будет добиваться выполнения следующего условия: (∗) массы всех кусков на столе составляют целое число граммов. Заметим, что Вова своим ходом не может нарушить (∗). Если перед ходом Паши на столе есть кусок массой хотя бы г, он может отрезать от него два куска по г, сохраняя (∗). Значит, если Паша не может сделать ход, каждый кусок весит либо г, либо г (такой момент обязательно наступит, так как количество кусков перед ходом Паши растёт). Но тогда он уже выиграл: в противном случае общая масса всех кусков (в граммах) меньше , что не так.