Задача М683‍‍

Доказательство возможности требуемой раскраски проведём индукцией по числу кружков $n$‍.‍

При $n\lt4$‍‍ утверждение очевидно. Предположим, что оно справедливо для любого расположения $k$‍‍ кружков. Пусть на столе лежит $k+1$‍‍ кружков. Зафиксируем на плоскости произвольную точку $M$‍‍ и рассмотрим кружок, центр $O$‍‍ которого находится на наибольшем расстоянии от $M$‍‍ (если таких кружков несколько, возьмём любой из них). Нетрудно убедиться, что выбранного кружка касается не более трёх других (центры всех кружков лежат в круге $(M,|OM|)$‍‍ — рис. 1).

Отбросим кружок с центром $O$‍‍ и раскрасим нужным образом в четыре цвета оставшиеся $k$‍‍ кружков (по предположению индукции это можно сделать). Вернём теперь кружок с центром $O$‍‍ на место. Поскольку он касается не более трёх из уже покрашенных кружков, его можно раскрасить в цвет, который не был использован при раскраске касающих его соседей.

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

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