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

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