Глава 6. Индукция и Ферма

Теперь, зная базисные факты арифметики остатков, мы готовы вернуться к изучению простых чисел. Основной результат этой главы — очень полезная теорема, впервые доказанная Ферма. Она непосредственно следует из более сильной теоремы теории групп, которую мы изучим в главе 9. Здесь же мы, следуя указаниям Ферма, даем ее прямое доказательство методом математической индукции. С описания такого метода доказательства мы и начнем.

§ 6.1. Ханой! Ханой!

Думали ли Вы когда-нибудь над головоломкой под названием «Ханойские башни»? Она состоит из трех деревянных стержней, закрепленных на деревянной основе и некоторого числа деревянных дисков (из шести в моем комплекте). В центре каждого диска есть отверстие для нанизывания на стержень. Обозначим стрежни Диаметры дисков различны; в начале игры все они располагаются на стержне А в порядке убывания размеров: самый большой внизу, а самый маленький — наверху башни.

Цель задачи: переместить всю башню со стержня А на стержень С, используя В как перевалочный пункт, подчиняясь при этом следующим правилам:

(1) за один ход можно переместить только один диск;

(2) больший диск нельзя класть поверх меньшего.

Обратите внимание! По первому правилу с любого стержня за один ход можно снять и переместить только верхний диск. Поэтому, если убрать из головоломки перевалочный стержень В, задача станет неразрешимой.

Стоит попытаться решить головоломку самостоятельно, чтобы освоиться с ней. Практически это можно сделать довольно быстро. Но вопрос, который мы хотим поставить, выходит за рамки стандартной игры: можем ли мы найти формулу минимального числа ходов, требуемых для перемещения всей башни из дисков со стержня А на стержень С? Естественно, мы предполагаем, что диски перемещаются согласно правилам. Поставленный вопрос имеет важнейшее значение для тех, кто готов поверить следующему рассказу.

Под высоким куполом одного индийского храма находятся три шпиля, густо усеянные алмазами, как пчела бархатным ворсом. В момент сотворения мира Бог поместил на один из них 64 диска чистого золота: наибольший — внизу, а остальные — сверху, так, что получилась башня. Он дал задание главному жрецу храма переставить диски согласно правилам, сформулированным выше. Когда вся башня из 64 дисков будет полностью перенесена на один из оставшихся шпилей, Бог вернется и положит конец миру. Итак, чтобы узнать, когда наступит конец света, Вам достаточно решить задачу о минимальном числе перемещений 64 дисков.

Оставив в стороне схоластические аспекты проблемы, вернемся к ее «деревянной» постановке, с которой мы начали. Если в игре только один диск, его достаточно просто перенести со стержня А на стержень С. При этом мы не нарушаем никаких правил, и головоломка решена. В этом случае достаточно

одного перемещения. Теперь предположим, что у нас есть два диска. Сначала мы перенесем меньший диск на стержень В; затем больший диск можно переставить на стержень С; и наконец, меньший — на С, так что он окажется сверху большого диска. Итак, для решения головоломки с двумя дисками достаточно трех ходов. Если у Вас есть такая головоломка, то неплохо было бы подсчитать количество перемещений, которое Вы сделаете, переставляя башню из четырех, а потом из пяти дисков.

Теперь поразмышляем над общим случаем головоломки из дисков. Рассуждение станет легче для восприятия, если мы опишем его в виде диалога между учеником и учителем.

Учитель: Предположим, что диски пронумерованы сверху вниз числами так что наименьший диск имеет номер 1 (и находится вверху), а наибольший — (он внизу стержня). Что нужно сделать, чтобы можно было передвинуть диск ?

Ученик: Чего?

Учитель: Мы хотим передвинуть диск но все остальные диски стоят на нем. Что же нам делать?

Ученик: Переставить все диски, которые стоят на самом большом?

Учитель: Это так, нам следует перенести дисков, которые лежат на Но нельзя забывать, что мы хотим переложить все диски на стержень С, а диск при этом должен оказаться в самом низу стержня. Куда же нам деть остальные ?

Ученик: На стержень В?

Учитель: На стержень В. Однако возникают проблемы.

Ученик: Они всегда есть.

Учитель: Правила! По первому из них мы можем менять

положение только одного из дисков; а по второму — диски должны быть нанизаны на стержень В в порядке убывания их размеров. Как нам передвинуть меньших диска с А на В?

Ученик: Нам следует передвигать только один диск за один ход, не нарушая правил.

Учитель: А более точно?

Ученик: Было бы здорово, я полагаю, чтобы задача с дисками была уже решена. Тогда можно было бы передвинуть башню из дисков со стержня А на В.

Учитель: А что будет служить перевалочным пунктом?

Ученик: Может, это С?

Учитель: Точно. Подведем итог. Нам нужно переставить диск на С. Но мы можем это сделать только после перемещения на стержень дисков, которые находятся над ним. Сделаем это, играя с меньшими дисками, используя С в качестве перевалочного пункта. Таким образом весь набор из дисков будет передвинут со стержня А на В. Осуществив это, мы свободно перенесем диск на С.

Ученик: Как же мы потом передвинем оставшиеся диски на С так, чтобы они правильно легли поверх диска Мне кажется, что нам нужно опять поиграть в диски, чтобы передвинуть их с В на С?

Учитель: Такая игра может занять много времени, но это именно тот путь, который приводит к победе. Заметим, что нам пришлось решить головоломку с дисками дважды. В первый раз мы переместили башню, состоящую из дисков с А на В (используя С в качестве перевалочного). Это нам освободило диск, и мы переместили его на С. Наконец, мы еще раз сыграли в игру с дисками, перемещая их со стержня В на С (используя А как перевалочный). В результате все дисков оказались нанизанными на стержень С, и ни одно правило не было нарушено.

Ученик:

Учитель: Это еще не конец!

Ученик: Не конец? О, Боже!

Учитель: Мы хотели найти наименьшее число ходов, необходимое для решения головоломки, разве нет?

Ученик: Полагаю, все еще хотим.

Учитель: Чтобы облегчить дальнейшие рассуждения, обозначим через минимальное число ходов, требуемых для решения головоломки с дисками. Как мы увидели, для ее решения нам сначала нужно передвинуть дисков, лежащих над Сколько ходов нам потребуется для этого?

Ученик: Чтобы переместить их на стержень В, нам нужно решить головоломку с дисками, не так ли? И нам, я полагаю, потребуется по крайней мере ходов.

Учитель: Поскольку мы перенесли меньших дисков на стержень В, стержень С остался пустым. Поэтому теперь можно передвинуть последний диск на С. Много ли нам нужно ходов для этого?

Ученик: Один?

Учитель: Естественно; и сколько теперь всего затрачено ходов от начала игры?

Ученик: Уф, ?

Учитель: Что дальше?

Ученик: Нам еще нужно перетащить меньших дисков с В, где они сейчас находятся, на С, накрыв ими диск

Учитель: Так, а сколько передвижений потребуется для достижения этой цели?

Ученик: Не меньше, чем разумеется, потому что это минимальное число ходов в головоломке с дисками.

Учитель: Итак, мы видим, что с момента начала игры всего нам предстоит сделать ходов. Более того, если мы внимательно посмотрим на проведенные рассуждения, мы убедимся, что нет никакой возможности полностью решить головоломку за меньшее число ходов. Так что такое

Ученик: Минимальное число ходов, требуемое для решения головоломки по перемещению дисков со стержня А на С.

Учитель: Да, но как нам вычислить предполагая, что мы уже знаем

Ученик:

Учитель: Отлично! Теперь подсчитаем минимальное число ходов, необходимых для решения задачи с шестью дисками.

Конечный результат диалога — формула

Заметим, что эта формула не говорит нам чему равно Для вычисления мы должны сначала найти Значит, вычисляется многократным применением формулы. Например, для вычисления нам сначала необходимо найти Поскольку, как мы уже усвоили, то

Действуя так же, мы имеем

Следовательно, для решения моей головоломки, состоящей из 6 дисков, мне нужно по крайней мере 63 хода. А как насчет головоломки в индийском храме? Для ответа на этот вопрос нужно вычислить довольно страшная задача.

Равенство называется рекуррентной формулой. Другими словами, чтобы найти нужно применить ее несколько раз, на каждом этапе используя в качестве исходных данкых результат предыдущего вычисления. Вы можете спросить, как доказать эту формулу? Ответ: приведенный диалог и является ее доказательством. Допускаю, что оно изложено в такой форме, которая может показаться чересчур экзотичной, чтобы называться математическим доказательством. Но этот недостаток легко лечится; все что нужно сделать — это выбрать основные моменты из диалога и переписать их на привычном математическом жаргоне.

Тот факт, что мы получили только рекуррентную формулу, не остановит наших попыток найти конечное выражение для т.е. такое, из которого получается простой подстановкой значения переменной Если Вы обратили внимание на значения вычисленные выше, то можете догадаться о вероятном виде искомой формулы. Но раз конечная формула будет угадана, перед нами встает новая проблема: мы должны будем доказать, что она работает при всех значениях переменной Заметим, что проверяя гипотетическую формулу для какой-то таблицы чисел, можно убедиться лишь в том, что она верна именно для чисел таблицы, но не более. Для доказательства формулы мы вводим метод математической индукции.

Быть может, Вы думаете: «Зачем беспокоиться о поиске другой формулы? Что плохого в рекуррентной?» Резонные вопросы. В конце концов, для определения при фиксированном нам всего-то и нужно, что вычислить с ее помощью Да компьютер сделает это очень быстро! Чего же еще желать? Как раз здесь пути математики и вычислительной математики расходятся.

Несколько преувеличивая, мы могли бы сказать, что вычислительная математика предназначена для грубого, силового подхода к работе: делать настолько эффективно, насколько

получается; а математика, наоборот, нацелена на поиск пути достижения результата с минимальными вычислениями. Конечно, это, в действительности, две стороны одной медали. В реальном мире проблемы решаются органическим синтезом математики и вычислительной математики. Так что эти науки чаще сотрудничают, чем конкурируют.