Областная олимпиада по математике, 2018 год, 9 класс

Несколько аэропортов связаны двусторонними беспересадочными авиарейсами так, что из каждого аэропорта выходит не более 2018 рейсов. Докажите, что можно разделить все рейсы между 11 авиакомпаниями компаниями так, что рейсами любой из компаний нельзя совершить круговое путешествие по нечетному числу аэропортов.

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

Лемма: Ребра полного графа на $2^n$ вершинах можно раскрасить в $n$ цветов так, чтобы граф с ребрами любого цвета был двудольным.

Доказательство: Лемма легко доказывается индукцией по $n.$

База: $n=1$ очевидно подходит.

Переход: Разобьем вершины на две группы по $2^{n–1}$ вершине, все ребра между группами покрасим в цвет $n$, граф из ребер этого цвета будет очевидно двудольным. Теперь для каждой из половинок покрасим ребра в цвета $1,2,\ldots, n–1$ (это можно по индукционному предположению). Графы этих цветов также будут двудольными, так как состоят из двух несвязанных двудольных частей каждый. $\quad\square$

Теперь перейдем к решению задачи. Легко покрасить вершины искомого графа $G$ степени не более $2018$ правильным образом в  $2^{11}$ цветов (даже в $2019$). Теперь, рассмотрим раскраску в $11$ цветов ребер полного графа на $2^{11}$ вершинах (вершины которого занумерованы цветами вершин графа $G$), в которой граф каждого цвета двудолен. Покрасим все ребра графа $G$ между вершинами цветов $i$ и $j$ также, как и ребро между вершинами $i$ и $j$ в раскраске полного графа. Очевидно, нечетных циклов в графе ребер любого цвета не будет.