Областная олимпиада по математике, 2018 год, 10 класс
Комментарий/решение:
Лемма: Ребра полного графа на 2n вершинах можно раскрасить в 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 в раскраске полного графа. Очевидно, нечетных циклов в графе ребер любого цвета не будет.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.