Мастер класс. «Ханойские башни»

Мастер класс.

Задача. Головоломка «Ханойские башни» состоит из трех стержней. На одном из стержней находится пирамидка (рис. 1), состоящая из нескольких колец разного диаметра, уменьшающихся снизу вверх

          .рис 1

Эту пирамидку нужно переместить на один из других стержней, перенося каждый раз только одно кольцо и не помещая большее кольцо на меньшее. Можно ли это сделать?

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

1. База индукции. При п = 1 все ясно, так как пирамидку из одного кольца очевидно можно переместить на любой стержень.

2. Шаг индукции. Предположим, что мы умеем перемещать любые пирамидки с числом колец п= к.
   Докажем, что тогда мы сможем переместить и пирамидку с п = к + 1.

Пирамидку из к колец, лежащих на самом большом    (к + 1)-м кольце, мы можем, согласно предположению, переместить на любой другой стержень. Сделаем это. Неподвижное (к + 1)-е кольцо не будет нам мешать провести алгоритм перемещения, так как оно самое большое. После перемещения кколец, переместим это самое большое (к + 1)-е кольцо на оставшийся стержень. И затем опять применим известный нам по индуктивному предположению алгоритм перемещения к колец, и переместим их на стержень с лежащим внизу   (к + 1)-м кольцом. Таким образом, если мы умеем перемещать пирамидки ск кольцами, то умеем перемещать пирамидки и с к + 1 кольцами. Следовательно, согласно принципу математической индукции, всегда можно переместить нужным образом пирамидку, состоящую из пколец, где п  1.