Принцип крайнего, индукция и другие методы в комбигео

Докажем утверждение индукцией по числу квадратов.

База индукции. Для одного квадрата утверждение очевидно.

Предположение индукции. Пусть для любого набора из квадратов существует требуемая раскраска.

Шаг индукции. Рассмотрим квадрат. Выберем крайний квадрат следующим образом:

• Выберем квадраты с максимальной абсциссой правой стороны.
• Если таких несколько, среди них выберем квадрат с минимальной ординатой нижней стороны.

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

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

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

Таким образом, получена корректная раскраска всех квадратов.