Полуинвариант

Рассмотрим граф Каждому городу страны сопоставим вершину данного графа. Соединим ребрами те и только те вершины, которые соответствуют городам, расстояние между которыми не превосходит км. Будем красить вершину в цвет флага над ратушей соответствующего города.

Пусть — количество ребер с концами разного цвета после дня Покажем, что для любого верно, что Действительно, без ограничений общности, пусть в соответствующий день вершина графа поменяла свой цвет с синего на красный, но тогда смежных с ней вершин красного цвета больше, чем тех же вершин синего цвета, но тогда количество ребер с концами разного цвета уменьшилось по крайней мере на

Таким образом, не позже чем, через дней данный процесс закончится.