Иногда утверждение может и не содержать параметра в явном виде и требуется сообразительность, чтобы его туда ввести (примеры 26 и 27).
Пример 26. Дано конечное множество прямых на плоскости. Доказать, что части, на которые плоскость разбита этими прямыми, можно раскрасить двумя красками, причём раскрасить правильно, т. е. так, чтобы никакие две части, имеющие общую границу, не были бы одинакового цвета.
Именно так, правильно, раскрашиваются географические карты, отражающие политическое или административное устройство какой-либо территории; поэтому всякое разбиение плоскости на части тоже будем называть картой. В подлежащем доказательству утверждении никакое натуральное число не упоминается, но сейчас мы такое число введём. С этой целью слегка переформулируем наше утверждение, включив в него параметр n: всякую карту, образованную n прямыми, можно правильно раскрасить в два цвета. Вот теперь уже можно применять метод математической индукции.
Базис справедлив: ведь при 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).
Принцип наименьшего числа может быть использован для построения нового варианта «стандартного рассуждения», призванного обосновать истинность универсальной формулировки. Вспомним, что мы обосновывали её, делая последовательные переходы от A(1) к A(2), от A(2) к A(3) и т. д. Теперь же будем рассуждать от противного. Покажем, как строится рассуждение, на примере 26. Предположим, что бывают карты указанного вида, которые нельзя правильно раскрасить. Назовём число n «плохим», если существует карта, образованная n прямыми, которую нельзя правильно раскрасить. По предположению «плохие» числа существуют; следовательно, множество всех таких чисел не пусто. Применяя к нему принцип наименьшего числа, получаем, что существует наименьшее «плохое» число a. В силу базиса индукции а ≠ 1. Значит, a = k + 1, где k – натуральное число. Так как a – наименьшее из «плохих» чисел, то k не является плохим; следовательно, всякую карту, образованную k прямыми, можно правильно раскрасить. Но тогда в силу индукционного шага можно правильно раскрасить и всякую карту, образованную a = k + 1 прямыми. Полученное противоречие убеждает нас, что исходное предположение о существовании карт, не допускающих правильной раскраски, не соответствует действительности. Таким образом, мы получили доказательство того, что всякую карту, образованную прямыми, можно раскрасить правильно.
Метод индукции в самом общем смысле состоит в переходе от частных формулировок к формулировке универсальной. Различают полную и неполную индукцию. Метод математической индукции позволяет, применяя некоторое логическое рассуждение к произвольному натуральному числу, убедиться, что A истинно для этого произвольного числа, а значит, убедиться что A(n) истинно для всех n. В этом смысле данный метод является методом полной индукции; слово «полная» означает, что мы лишь тогда считаем себя вправе объявить об истинности универсальной формулировки, когда мы убедились в её истинности для каждого отдельного значения n – во всей полноте этих значений, без исключения. Метод неполной индукции состоит в переходе к универсальной формулировке после проверки частных формулировок для отдельных, но не всех значений n.
Примеры неполной индукции встречаются на каждом шагу. Скажем, если не все, то многие уверены, что Бенджамин Франклин был президентом Соединённых Штатов. «Президент Франклин» – такое можно услышать и от кассира в банке, и с экрана телевизора, причём от персонажей, которых трудно заподозрить в глубоком знании американской политической истории. А откуда же возникла подобная уверенность? Дело в том, что портрет Франклина мы видим на 100-долларовой банкноте, а едва ли не каждый знает: на лицевой стороне долларовых банкнот помещены заключённые в овал портреты американских президентов. И действительно, на однодолларовой купюре изображён первый президент Джордж Вашингтон, на двухдолларовой – третий президент Томас Джефферсон, на пятидолларовой – шестнадцатый президент Авраам Линкольн, на двадцатидолларовой – седьмой президент Эндрю Джексон, на пятидесятидолларовой – восемнадцатый президент Улисс Грант. Однако попытка установить порядковый номер президентства Франклина встречает непреодолимые затруднения. Дело в том, что Франклин не был президентом США. (Как не был президентом США и Александр Гамильтон, чей портрет украшает десятидолларовую купюру.)
