Леонард Эйлер атындағы олимпиада,2014-2015 оқу жылы, қорытынды кезеңнің 2-ші туры

Графиния елінде $n$ $(n \geq 2)$ қала бар. Кейбір қалалар тұра (қонбай ұшып өтетін) авиажолымен қосылған (әр авиажолмен рейстер екі бағытта да орындалады). Кез келген қаладан ұшақпен кез келген басқа қалаға жетуге болады (басқа қала арқылы жету де мүмкін), бірақ, кез келген авиажолды жапса, ол шарт бұзылады. Сонымен қатар әр қаладан $d$-дан көп емес авиажол шығады. Графиния қаласының барлық қалаларын, әр авиажол әр түрлі топтағы екі қаланы қосатындай және кез келген екі топ үшін сол екі топты қосатын авиажол саны бірден аспайтындай, саны $\dfrac{n}{2} + d$ санынан аспайтын топ санына бөлуге болатынын дәлелдеңіз. ( Д. Карпов )

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

Комментарии от администратора Комментарии от администратора №1.     Рассмотрим граф, где вершины — города, а рёбра — авиалинии. По условию он является деревом, вершины которого, как известно, можно занумеровать двумя цифрами так, чтобы любые две смежные вершины были отмечены разными цифрами. Сделаем это и покрасим в чёрный цвет вершины, отмеченные той цифрой, которой отмечено не меньше половины всех вершин. Остальные вершины покрасим в разные цвета, для этого хватит $n/2$ цветов. Докажем индукцией по количеству вершин, что черные вершины любого дерева, у которого степени всех вершин не превосходят $d$, можно перекрасить в $d$ цветов так, чтобы две вершины, имеющие общую соседнюю, были разноцветными. Так как $n \geq 2$, у дерева есть не чёрная вершина $x$. Пусть $y_1, \dots, y_k$ — соседи вершины $x$, они черные и $k \leq d$. Тогда при удалении вершины $x$ получается $k$ деревьев, каждое из которых меньше исходного и может быть покрашено по предположению индукции. Так как покраски этих деревьев независимы, можно покрасить их так, чтобы все вершины $y_1, \dots, y_k$ имели разные цвета, что нам и нужно. Вернемся к задаче и покрасим черные вершины нашего дерева, как сказано выше. Предположим, что пары соседних вершин $a_1b_1$ и $a_2b_2$ имеют одинаковые наборы цветов. Тогда не чёрные вершины $a_1$ и $a_2$ в этих парах совпадают. Но все соседи вершины $a_1$ разноцветны, противоречие.