1.1. Задача о ханойской башне
Рассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск, и не помещая больший диск на меньший.
Будем решать эту задачу в общем виде, т.е. посмотрим, что будет в случае n дисков.
Будем говорить, что Tn есть минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой по правилам Люка.
Рассмотрим крайние случаи: Т0=0, T1=1, T2=3, T3=7. Эксперимент с тремя дисками дает ключ к общему правилу перемещения n дисков: сначала мы перемещаем (n?1) меньших дисков на любой из колышков (что требует Тn-1 перекладываний), затем перекладываем самый большой диск (одно перекладывание ) и, наконец, помещаем (n?1) меньших дисков обратно на самый большой диск (еще Тn-1 перекладываний). Таким образом, n дисков (при n>0) можно переместить самое большое за 2Tn-1+1 перекладываний (т.е. достаточно перекладываний): Tn ? 2Tn-1+1.
Сейчас покажем, что необходимо 2Tn-1+1 перекладываний. На некотором этапе мы обязаны переместить самый большой диск. Когда мы это делаем, (n?1) меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере Тn-1 перекладываний. Самый большой диск можно перекладывать и более одного раза. Но после перемещения самого большого диска в последний раз мы обязаны поместить (n?1) меньших дисков (которые опять должны находиться на одном колышке) обратно на наибольший диск, что также требует Тn-1 перекладываний. Следовательно, Tn ? 2Tn-1+1.
Эти два неравенства вместе с тривиальным решением при n=0 дают рекуррентное соотношение:
Т0=0
Tn = 2Tn-1+1 при n>0
При достаточно большом n для вычисления Тn потребуется слишком много времени, поэтому получим Тn в простой, компактной, «замкнутой форме», что позволит вычислить Тn быстро.
Первый способ решения (угадывание правильного решения с последующим доказательством, что наша догадка верна).
Вычислим: Т3=2•3+1=7; Т4=2•7+1; Т5=2•15+1; Т6=2•31+1=63. Теперь можно сделать предположение, что
Тn =2n ? 1 при n?0. (2)
Докажем методом математической индукции по числу n:
1) База: n=0, Т0=20-1=1-1=0 (верно);
2) Индуктивный переход: пусть доказано для всех чисел t ? (n-1). Докажем для t=n: Тn= 2Tn-1+1 2(2n-1?1)+1 = 2•2n-1?2+1 = 2n ? 1
Из пунктов 1 и 2 следует: при n?0 Тn = 2n ? 1
Второй способ решения.
К обеим частям соотношения (1) прибавим 1:
Т0+1 = 1,
Тn+1 = 2Tn-1+2 при n>0.
Обозначим Un = Tn+1, тогда получим
U0 = 1
Un = 2Un-1 при n>0.
Решением этой рекурсии есть Un=2n; следовательно Тn = 2n?1.