Изменения

Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для самого маленького диска всегда есть две свободные позиции, потому что он самый маленький, его можно положить сверху на любой диск. Если диск не самый маленький, то для него может быть не более одной свободной позиции. Допустим, что для него свободные две позиции. Это означает, что на двух других стержнях расположены диски размером больше, чем рассматриваемый. А так как рассматриваемый диск не самый маленький, то где-то расположен наименьший. Либо он расположен на рассматриваемом диске, тогда мы не можем переместить рассматриваемый, либо на каком-то другом, но тогда у нашего диска остаётся не более одной свободной позиции. Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если <tex>n</tex> нечётно, то последовательность перемещений наименьшего диска имеет вид <tex>r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow r_{1} \rightarrow r_{3} \rightarrow r_{2} \rightarrow \ldots .</tex>(где <tex>r_{1}</tex> — стартовый стержень, <tex>r_{3}</tex> — финальный стержень, <tex>r_{2}</tex> — оставшийся стержень), а если <tex>n</tex> чётно, то <tex>r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow r_{1} \rightarrow r_{2} \rightarrow r_{3} \rightarrow \ldots.</tex>

==См. Также==