Республиканская олимпиада по математике, 2026 год, 10 класс

Двое игроков играют в следующую игру. Имеется пустой граф на $S$ вершинах и $k$ карандашей различных цветов. Первый игрок называет цвет, после чего второй игрок проводит какое-нибудь ребро, не проведённое ранее, карандашом названного цвета. Затем первый игрок снова называет цвет, второй проводит ребро и т. д. Если в некоторый момент игры образуется цикл из рёбер одного цвета, то игра заканчивается, и выигрывает второй игрок. Если же все рёбра будут проведены и не образуется ни одного одноцветного цикла, то выигрывает первый игрок. Для фиксированного $S > 2$ найдите наибольшее $k$, при котором второй игрок может гарантировать себе победу. ( Абдрахманов А. )

Комментарий/решение

Наибольшее $k = \lfloor \frac{S}{2} \rfloor$.

* При $k \le \lfloor \frac{S}{2} \rfloor$ второй игрок выигрывает. Он разбивает вершины на $m = \lfloor \frac{S}{2} \rfloor$ непересекающихся пар. Каждому из $k$ цветов он сопоставляет свою уникальную пару вершин. Когда первый игрок называет цвет, второй проводит ребро этого цвета между вершинами из его пары. Каждый цвет образует лишь отдельные отрезки (паросочетания). В графе не возникает ни одного одноцветного цикла. Первый проигрывает, когда ходы заканчиваются.

* При $k > \lfloor \frac{S}{2} \rfloor$ первый игрок выигрывает. Он называет каждый ход новый цвет. Всего цветов больше, чем пар вершин на доске, поэтому второй игрок вынужден строить рёбра разных цветов. По принципу Дирихле, рёбер одного цвета не хватит для замыкания цикла, пока первый распределяет ходы по всем $k$ цветам. Первый игрок выигрывает.