M683. О расположении разноцветных кружков

Условие

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

Доказательство

Доказательство возможности требуемой раскраски проведем индукцией по числу кружков $n$. При $n\leq 4$ утверждение очевидно. Предположим, что оно справедливо для любого расположения $k$ кружков. Пусть на столе лежит $k+1$ кружков. Зафиксируем на плоскости произвольную точку $M$ и рассмотрим кружок, центр $O$ которого находится на наибольшем расстоянии от $M$ (если таких кружков несколько, возьмем любой из них). Нетрудно убедиться, что выбранного кружка касается не более двух других (центры всех кружков лежат в круге $\left ( M, \left | OM \right | \right )$ — рис. 1). Отбросим кружок с центром $O$ и раскрасим нужным образом в четыре цвета оставшиеся $k$ кружков (по предположению индукции это можно сделать). Вернем теперь кружок с центром $O$ на место. Поскольку он касается не более трех из уже покрашенных кружков, его можно раскрасить в тот цвет, который не был использован при раскраске касающихся его соседей.

Утверждение доказано.

На рисунке 2 изображены 11 кружков, для нужной раскраски которых трех цветов недостаточно. Действительно, предположив, что эти кружки можно раскрасить тремя цветами, получим, что кружки $A, B, C, D, E$ должны быть окрашены одинаково. Но это невозможно, поскольку кружки $A$ и $E$ касаются.