Апология математики (сборник статей)

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

Именно так, правильно, раскрашиваются географические карты, отражающие политическое или административное устройство какой-либо территории; поэтому всякое разбиение плоскости на части тоже будем называть картой. В подлежащем доказательству утверждении никакое натуральное число не упоминается, но сейчас мы такое число введём. С этой целью слегка переформулируем наше утверждение, включив в него параметр n: всякую карту, образованную n прямыми, можно правильно раскрасить в два цвета. Вот теперь уже можно применять метод математической индукции.

Базис справедлив: ведь при n = 1 прямая ровно одна и достаточно просто раскрасить в разные цвета те две части, на которые она делит плоскость. Посылка индукционного шага состоит в предположении, что правильную раскраску можно всегда осуществить в случае k прямых. Заключение – в утверждении, что правильную раскраску всегда можно осуществить для k + 1 прямых. Переход от посылки к заключению, показанный на рис. 2, состоит в следующем. На карте, образованной k + 1 прямыми, выделим одну прямую – на рис. 2, а она показана жирной линией и помечена буквой p. Удалив эту прямую, получим карту, содержащую k прямых (рис. 2, б). Согласно индукционному предположению, полученная карта допускает правильную раскраску, которая показана на рис. 2, в. На раскрашенной карте восстанавливаем удалённую прямую (рис. 2, г), отчего правильность раскраски, разумеется, нарушается. Однако она сохранится в каждой из полуплоскостей, на которые выделенная прямая разбивает плоскость; нарушения будут иметь место лишь там, где граница между участками проходит по прямой p. Поэтому если в одной из названных полуплоскостей раскраску не менять, а в другой заменить каждый из двух цветов на противоположный, то вся карта с k + 1 прямой окажется правильно раскрашенной (рис. 2, д).