Связность и связные подграфы (клики)

Подсказка 1

Попробуем доказать, что первый победит при правильной стратегии, обоснованием такому предположению послужат первые рассуждения, которые последует далее. Постараемся построить победную стратегию. Чему может быть равно число ребер в результирующем графе?

Подсказка 2

Ровно n-1 ребро. С одной стороны, именно столько ребер содержится в остовном дереве, которое можно выделить в любом связном графе n вершин. С другой стороны, любой ход, после которого в графе их из синих ребер образуется цикл, можно было пропустить, поскольку ребро, которое было поставлено в этот ход, никак не влияет на связность текущего и любого графа, который может образоваться при следующих ходах. Чему равно количество ходов в игре? Какое следствие из этого можно сделать для нашей стратегии?

Подсказка 3

Количество ходов первого игрока равно n-1. Ясно, что нам необходимо следить за отдельными компонентами связности текущего графа (изначально их количество равно n, в конце — n-1 и изменяется на 1 с каждым ходом). Кажется, что если две компоненты связности содержат достаточное количество вершин, то второй не успеет покрасить все ребра между ними даже за всю игру. Сколько вершин должно быть в каждой из компонент связности, чтобы победа первого была предопределена?

Подсказка 4

Несложно показать, что если первый успеет разбить вершины на компоненты связности размера не меньше 101 — он победил. Как это наблюдение помогает нам построить победную стратегию?

Подсказка 5

Стратегия первого на ход такова: выбирать компоненту X размера меньше 101 (выбирать компоненты связности большего размера не имеет смысл по доказанному выше утверждению) из которой наружу идёт больше всего синих ребер и соединять её с любой другой. Будем говорить, что синие рёбра идущие из X в этот момент упомянуты. Наконец, наша цель дважды оценить количество суммарных упоминаний всех ребер за игру с двух сторон, что повлечет за собой противоречие. Как можно оценить сверху количество упоминаний произвольного фиксированного синего ребра?

Подсказка 6

Несложно показать, что каждое синее ребро упомянуто не больше 200 раз. Осталось предположить, что стратегия, предъявленная нами, не работает. Это было возможно на некотором ходе только в том случае, если на этом ходе появилась компонента связности, количество вершин в которой не превосходит 100, которая отделена от всех остальных вершин исходного графа (сейчас из неё ведет не меньше n−1 синих ребер). Рассмотрите какой вид имела данная компонента связности во все прошлые ходы и сделайте отсюда оценку снизу на количество упоминаний.

Подсказка 7

Количество упоминаний каждого синего ребра не превосходит 200, а их количество не превосходит 100*(n-2) --- количество ходов второго, умноженного на 100, то есть суммарное число упоминаний не превосходит 2*10⁴(n-2). C другой стороны, из рассуждений предыдущей подсказки, не меньше, чем ((n-1)/100-1)+((n-1)/100-2)+..., докажите, что неравенство, которое при это этом образуется невозможно при заданных значениях n