Республиканская олимпиада по математике, 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$ цветам. Первый игрок выигрывает.