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

Пример 27. Выпуклый многоугольник целиком покрыт другим выпуклым многоугольником. (Например, на рис. 3 многоугольник ABCDEFG целиком покрыт многоугольником IJKLMNO.) Доказать, что периметр внутреннего многоугольника не превосходит периметра многоугольника внешнего. Будем доказывать данное утверждение методом математической индукции. Чтобы применить этот метод, надлежит ввести параметр. Сообразительности здесь потребуется несколько больше, чем в примере 26. Назовём свободной всякую сторону внутреннего многоугольника, которая не лежит ни на какой стороне внешнего многоугольника. (Так, на рис. 3 свободными являются стороны AB, BC, CD, EF, GA, но не стороны DE и FG.) В качестве параметра индукции возьмём количество свободных сторон, точнее говоря, количество свободных сторон плюс единица (поскольку свободных сторон может и не быть, а мы условились начинать натуральный ряд не с ноля, а с единицы). Сформулируем теперь более развёрнуто утверждение, которое собираемся доказывать индукцией по этому параметру: каково бы ни было натуральное число n, для всяких двух вложенных друг в друга выпуклых многоугольников, у которых число свободных сторон равно n – 1 или меньше, периметр внутреннего многоугольника не превосходит периметра внешнего многоугольника. В базисе индукции значение параметра равно единице, а это значит, что свободных сторон нет вовсе. Тогда утверждение очевидно: ведь в этом случае каждая сторона внутреннего многоугольника является частью какой-либо стороны внешнего многоугольника. Предположим теперь, что утверждение верно для всех случаев, когда в паре вложенных многоугольников имеется k свободных сторон. Докажем его для всех случаев, когда в паре вложенных многоугольников имеется k + 1 свободных сторон. Итак, пусть R есть внутренний многоугольник, Т – внешний и количество свободных сторон есть k + 1. Нам нужно доказать, что p(R) ≤ p(T), где p(R) и р(Т) – периметры многоугольников R и T. Берём одну из свободных сторон и продолжаем её в обоих направлениях (на рис. 3 в качестве такой свободной стороны выбрана сторона AB). Полученная прямая разрезает Т на два многоугольника – также выпуклых, как это показано в замечании, непосредственно предшествующем примеру 20. Точки пересечения со сторонами многоугольника T обозначим буквами X и Y. Поскольку внутренний многоугольник выпукл, он, как это доказано в примере 20, целиком лежит по одну сторону от прямой XY. Следовательно, он целиком располагается внутри одного из тех двух многоугольников, на которые эта прямая разбивает T. Обозначим буквой S тот из многоугольников разбиения, который содержит R, так что R вложен в S, а S вложен в T. На рис. 3 таковым промежуточным S является многоугольник XYKLMNO (а другим из двух многоугольников, на которые разбивается T, будет многоугольник XYJI). Обозначим через p (S) периметр многоугольника S. На рис. 3 видно, что p (S) ≤ p (T), поскольку отрезок, стягивающий концы ломаной (на рис. 3 – отрезок XY), короче самой этой ломаной (на рис. 3 – ломаной XIJY). Если теперь рассмотреть пару вложенных многоугольников R и S, то можно заметить, что в этой паре количество свободных сторон меньше количества свободных сторон в паре R и T. Действительно, свободной перестала быть та сторона (на рис. 3 – сторона AB) многоугольника R, с которой мы начали построение. Поэтому по предположению индукции p(R) ≤ p (S). Соединив это неравенство с установленным ранее неравенством p(S) ≤ p(T), приходим окончательно к требуемому неравенству p(R) ≤ p(T).