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