Задача о ханойской Башне⁠⁠

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

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

Чтобы решить этот вопрос, нам следует чуть-чуть усложнить нашу задачу, а точнее обобщить ее, посмотрим, что будет в случае n дисков. Обозначим за T(n) - минимальное число перекладываний, необходимых для перемещения n дисков с одного колышка на другой. Очевидно, что T(1)=1, а T(2)=3.

Давайте найдем T(3), для этого надо перенести два верхних диска на средний колышек, затем перенести третий диск и на него перенести два других. Получаем 2*T(2)+1=7 перекладываний. Это легко обобщить на случай n дисков: сначала надо перенести n-1 меньших дисков на средний колышек, затем перенести большой диск и на него перенести n-1 меньших. Таким образом n дисков можно перенести за 2*T(n-1)+1 перекладываний. Но мы не доказали, что необходимо 2*T(n-1)+1 перекладываний

Действительно, нет ли более короткого пути? Оказывается нет. На некотором этапе мы переносим самый большой диск. Когда мы его переносим n-1 меньших дисков должны находиться на одном колышке, а для того чтобы собрать их вместе, потребуется по меньшей мере T(n-1) перекладываний. После перемещения самого большого диска в последний раз (его могут перемещать и больше одного раза) мы обязаны переместить n-1 меньших дисков обратно. Это требует T(n-1) перекладываний. Следовательно T(n) не меньше, чем 2*T(n-1)+1

Хорошо, мы получили равенство T(n)=2T(n-1)+1, кроме того мы знаем, что T(1)=1, совокупность таких равенств называется рекуррентностью. В данном случае легко угадать решение методом пристального взгляда: T(1)=1, T(2)=3, T(3)=7, T(4)=15, T(5)=31, T(6)=63. T(n)=2^n - 1? Это равенство легко проверить с помощью метода математической индукции.