ВсОШ 2026, 10 класс, задача 4
Даны натуральные числа и , причём и . Изначально в ряд выложены пластилиновых шариков, каждый шарик имеет массу . Петя и Вася играют в игру, делая ходов по очереди, начинает Петя. За ход игрок должен выбрать два соседних шарика и слепить их в один шарик (который остается в том же месте в ряду). Победа присуждается Пете, если в какой-либо момент игры в ряду появлялся шарик массы . Иначе победа присуждается Васе. Кто из игроков имеет выигрышную стратегию?
Ответ: Петя побеждает при ; иначе побеждает Вася.
Решение. Переформулируем задачу следующим образом. Пусть изначально на числовой прямой покрашены красным точки , а шарики из условия соответствуют единичным отрезкам . За свой ход игрок перекрашивает одну из красных точек, отличных от точек и , в синий цвет. Петя и Вася по очереди делают ходы (Петя — ходов, Вася — ход), пока в конце не останутся лишь две красные точки и . Петя выигрывает, если в какой-то момент игры найдутся красные точки и такие, что все целые точки между ними синие.
Пусть . Предъявим стратегию за Петю. Первым ходом пусть он покрасит синим точку . Выделим пар красных точек
а красные точки разобьем на пары произвольно. Если Вася перекрашивает в синий цвет некоторую точку, то Петя на следующем ходе перекрашивает вторую точку из той же пары. В результате после ходов Пети все выделенные пары точек одноцветные, причем количество выделенных пар красных точек не изменяется или уменьшается на . В какой-то момент после хода Пети будет ровно одна выделенная пара красных точек. В этот момент среди точек только и красные, значит все целые точки между ними синие, и Петя выигрывает.
Пусть . Предъявим стратегию за Петю. Первым ходом пусть он покрасит синим точку . Остальные красные точки, за исключением и , разобьем на пары:
Если Вася перекрашивает в синий цвет некоторую точку, то Петя на следующем ходе перекрашивает вторую точку из той же пары. В результате перед последним ходом Васи останется ровно одна указанная пара красных точек, а точки во всех остальных парах будут синими. Если это пара вида , то Петя уже побеждает. Пусть это пара . Перекрашивая последним ходом , Вася проигрывает из-за пары красных точек . Аналогично, перекрашивая последним ходом , он проигрывает из-за пары .
Пусть . Предъявим стратегию за Васю. Рассмотрим последовательность точек
Пусть Вася на своем ходе перекрашивает самую первую на текущий момент красную точку в этой последовательности. Так как , ходов у Васи хватит, чтобы все точки из в итоге стали синими. После этого пусть Вася играет как угодно.
Покажем, что такая стратегия работает. Предположим противное: в какой-то момент точки и красные для некоторого , а все целых точек из интервала синие. Не может быть , так как точка стала на первом же ходу Васи синей, и к этому моменту среди точек было не более одной синей. Пусть . Поскольку еще красная, Вася пока только перекрашивал точки множества , то есть сделал к рассматриваемому моменту не более ходов, при этом лишь один раз он перекрашивал точку из интервала , а именно точку . Тогда к этому моменту Петя сделал не более хода. Значит, среди целых точек интервала синими стали не более точки. Но
тем самым в осталась хотя бы одна красная точка — противоречие.