Условие
Несколько кругов одного радиуса положили на
стол так, что никакие два не перекрываются. Докажите, что
круги можно раскрасить в четыре цвета так, что любые
два касающихся круга будут разного цвета.
Решение
Доказательство проведем индукцией по числу кругов
n. При
n = 1 утверждение очевидно. Пусть
M — любая точка,
O —
наиболее удаленный от нее центр круга. Тогда круг с центром
O
касается не более трех других данных кругов. Выбросим его и раскрасим
остальные круги согласно предположению индукции. Этот круг можно
окрасить цветом, отличным от цветов касающихся его кругов.
Источники и прецеденты использования
