1. Возвратные задачи

В ЭТОЙ ГЛАВЕ В КАЧЕСТВЕ ПРИМЕРА рассматриваются три задачи, по которым можно будет судить о том, что нас ожидает в дальнейшем. Эти задачи имеют две общие черты: к ним неоднократно обращались математики и решение каждой из них основано на идее возвратности (или рекуррентности), согласно которой решение всей задачи зависит от решений той же самой задачи меньших размеров.

1.1 ЗАДАЧА О ХАНОЙСКОЙ БАШНЕ

Рассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков:

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

Люка [209] связывал свою игрушку с мифической легендой о значительно большей башне Брамы, которая, как утверждается, состоит из 64 дисков чистого золота, а колышки представляют собой три алмазных шпиля. При сотворении мира Всевышний поместил диски на первый шпиль и повелел, чтобы жрецы переместили

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

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

Наилучший способ разрешить вопрос, подобный нашему, — несколько обобщить его. Башня Брамы состоит из 64 дисков, а ханойская башня — из 8; посмотрим, что будет в случае дисков.

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

Следующий шаг в решении задачи — выбор подходящего обозначения: обозначай и властвуй. Будем говорить, что есть минимальное число перекладываний, необходимых для перемещения дисков с одного колышка на другой по правилам Люка. Тогда очевидно, равно 1, а равно 3.

Можно получить дополнительную информацию, причем совершенно бесплатно, если рассмотреть самый крайний случай: ясно, что поскольку для перемещения башни из дисков вообще не требуется ни одного перекладывания! Блестящие математики не стыдились впадать в крайности, потому что если хорошенько разобраться в частных случаях (даже в совсем тривиальных), легче постичь общие закономерности.

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

В этой формуле фигурирует знак вместо поскольку наше построение показывает только, что достаточно перекладываний; мы не доказали, что необходимо перекладываний

Быть может, какой-нибудь мудрец отыщет лучший метод.

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

Эти два неравенства вместе с тривиальным решением при дают

(Заметим, что уже известные нам значения согласуются с этими формулами. Особое внимание к крайним случаям не только способствовало выводу общей формулы, но и обеспечило удобным способом проверки, что мы не совершили глупой ошибки. Такие проверки будут особенно ценными, когда мы отважимся на более рискованные Маневры в последующих главах.)

Совокупность равенств типа (1.1) называется рекуррентностью (говорят также о возвратном соотношении или рекурсивной зависимости). Она задается начальным значением и зависимостью общего члена от предыдущих. Иногда мы будем называть рекуррентностью только выражение для общего члена, хотя формально для полного задания рекуррентности необходимо еще начальное значение.

Рекуррентность позволяет вычислять для любого какое мы пожелаем. Но в действительности никто не захочет пользоваться для вычисления рекуррентностью, когда велико — это займет слишком много времени. Рекуррентность дает только косвенную, локальную информацию. Решение рекуррентного соотношения — вот что доставило бы нам чувство глубокого удовлетворения. То есть мы хотели бы получить в простой, компактной, «замкнутой форме» что позволило бы вычислить быстро даже при большом Располагая решением в замкнутой форме, мы могли бы понять, что на самом деле представляет собой

Итак, как же решить рекуррентное соотношение? Один из способов состоит в угадывании правильного решения с последующим доказательством, что наша догадка верна. А наша самая

большая надежда на угадывание решения — (снова) крайние случаи. Поэтому мы последовательно вычисляем . Это определенно выглядит так, как если бы

По крайней мере эта формула «работает» при

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

Рекуррентность идеально подходит для математической индукции. Например, в нашем случае (1.2) легко следует из (1.1): база индукции тривиальна, поскольку а индуктивный переход выполняется для если предположить справедливость (1.2), когда заменяется на :

Следовательно, (1.2) справедливо с равным успехом при любом Отлично! С поиском выражения для благополучно покончено.

Однако с задачей браминов дело обстоит иначе — они по-прежнему покорно перекладывают диски и им придется еще изрядно потрудиться, поскольку при требуется (примерно 18 с восемнадцатью нулями) перекладываний. Даже работая с фантастической скоростью одно перекладывание в микросекунду, они затратят свыше 5000 веков для перемещения башни Брамы. Сама же головоломка Люка несколько практичнее — она требует перекладываний, которые при известной сноровке можно выполнить приблизительно за четыре минуты.

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

1 Рассмотрение крайних случаев. Это позволяет вникнуть в задачу и помогает на стадиях 2 и 3.

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

3 Нахождение и доказательство замкнутой формы для нашего математического выражения. В случае ханойской башни это решение рекуррентности (1.2).

Именно третьей стадии мы будем уделять внимание на протяжении всей книги. Порой будем перескакивать сразу через стадии 1 и 2, поскольку математическое выражение будет задано в качестве исходного. Но даже тогда мы будем сталкиваться с подзадачами, необходимость решения которых заставит нас проходить все три стадии.

Наш анализ задачи о ханойской башне привел к правильному ответу, но он требовал индуктивного скачка — мы полагались на счастливую догадку об ответе. Одна из основных целей этой книги состоит в том, чтобы объяснить, как читатель может решать рекуррентности, не являясь ясновидцем. Например, рекуррентность (1.1) может быть упрощена прибавлением 1 к обеим частям соотношений:

Теперь, если положить то получим

Не надо быть гением, чтобы обнаружить, что решение этой рекурсии есть просто следовательно, Даже компьютер смог бы обнаружить это.