ВсОШ 2024, 10, 11 классы, задача 3
( баллов) По кругу стоят белых точек. Аня и Боря красят по очереди по одной ещё не покрашенной точке в красный или синий цвет, начинает Аня. Аня хочет, чтобы в итоге оказалось как можно больше пар разноцветных соседних точек, а Боря — чтобы оказалось как можно меньше таких пар. Какое наибольшее число пар разноцветных соседних точек Аня может гарантировать себе независимо от игры Бори?
(П. Кожевников)
Ответ
Ответ. .
Решение. Нужно показать, что Аня всегда может добиться, чтобы разноцветных пар было не меньше , а Боря сможет помешать ей добиться, чтобы таких пар было больше .
Первый способ. Стратегия Ани. Первым ходом Аня красит в любой цвет любую точку, а дальше каждым ходом выбирает пару из непокрашенной точки и стоящей рядом с ней покрашенной (такая, очевидно, найдётся), и красит непокрашенную точку в цвет, отличный от цвета покрашенной. При этом образуется новая пара соседних разноцветных точек.
Стратегия Бори. Каждым ходом Боря выбирает пару из непокрашенной точки и стоящей рядом с ней покрашенной, и красит непокрашенную точку в цвет, совпадающий с цветом покрашенной. При этом образуется новая пара соседних одноцветных точек.
Обоснование правильности стратегий. Всего в круге имеется пар соседних точек, и каждый игрок делает за игру по ходов. Сделав свои ходы, Боря добьётся того, что из этих пар хотя бы будут одноцветными, а Аня — что хотя бы из них будут разноцветными. Однако заметим, что количество разноцветных пар всегда чётно. Действительно, после окончания игры пройдём полный круг, начиная с какой-то отмеченной точки (пусть для определённости с красной). Группы из идущих подряд красных и синих точек при этом будут чередоваться: К—С—К—С——К, и значит, встретим пар разноцветных соседей вида К—С столько же, сколько пар вида С—К. Поэтому если пар разноцветных соседних точек не меньше , то их хотя бы .
Второй способ. Разобьём все отмеченные точки на пар соседей: , , , .
Стратегия Бори. Если своим ходом Аня красит точку в паре , то Боря ответным ходом красит вторую точку в паре в тот же цвет. Ясно, что при такой игре Бори в конце игры каждая пара будет покрашена в один цвет. Значит, из пар соседних точек не менее будут одноцветными. Поэтому разноцветных пар будет не больше, чем .
Стратегия Ани. Аня будет добиваться того, чтобы в каждой паре с нечётным номером она покрасила одну из точек красным, а в каждой паре с чётным номером — синим. Если у Ани это получится, то покрашенные ею точек разобьют окружность на дуг с разноцветными концами. На каждой из этих дуг, очевидно, найдётся хотя бы одна пара разноцветных соседних отмеченных точек (в частности, если на дуге нет отмеченных Борей точек, такую пару образуют концы дуги).
Покажем, как Аня может реализовать этот план. Первым ходом она красит одну из точек в какой-то паре соответствующим цветом. Далее, если Боря отвечает ходом в ту же пару, то Аня красит одну из точек в любой ещё не покрашенной паре, иначе она красит вторую точку в паре, в которой только что покрасил точку Боря. В результате после каждого хода Ани будет ровно одна пара , в которой одна точка покрашена Аней, а другая не покрашена, а в каждой из остальных пар будет либо две покрашенных точки, ровно одна из которых покрашена Аней, либо ни одной покрашенной точки. Значит, в конце игры Аней будет покрашено ровно по одной точке в каждой паре , что ей и требовалось.
Только ответ.
- Предъявлена верная стратегия за Борю, гарантирующая, что число разноцветных пар не больше .
1') Обосновано, что эта Борина стратегия работает.
- Предъявлена верная стратегия за Аню, гарантирующая, что число разноцветных пар не меньше .
2') Обосновано, что эта Анина стратегия работает (если при верной Аниной стратегии обосновано лишь, что она может обеспечить себе пар, то считается, что обоснование отсутствует, и эти баллы не ставятся).
Баллы за указанные продвижения суммируются. Если предъявленная стратегия за одного из игроков не работает хотя бы в одном частном случае развития игры, такая стратегия признается не работающей и оценивается в ноль баллов.