Узагальнення задачі про Ханойську вежу

Abstract

Розглянуто варіацію класичної задачі про Ханойські вежі (див., напр., [1]). Нехай дано три кілки, на одному з них розташовано вежу з п дисків, причому під кожним диском, окрім найнижчого, розташовано диск більшого діаметра. Пронумеруємо диски і вважатимемо, що перший диск є найменшим, а п-тий — найбільшим. Диски з непарними порядковими номерами пофарбовано в один колір (червоний), з парними — в інший (синій). Мета гри — перемістити вежу на інший кілок із дотриманням таких правил: за один крок можна перемістити лише один диск, і тільки той, що розташований нагорі свого стека; кожен диск можна класти лише на диск більшого діаметра; кожен диск можна класти лише на диск іншого кольору. Теорема. Для задачі про двоколірну Ханойську вежу існує розв’язок, причому мінімальна кількість кроків дорівнює мінімальній кількості кроків класичної задачі 2п — 1, де п — кількість дисків.

The article examines a variation of the generalized tower of Hanoi problem (see [1]). We are given a tower of n disks, initially stacked in decreasing size on one of three pegs. Let us label the discs: disc 1 is the smallest disc, disc 2 the second smallest, and so on. Let the discs having odd numbers be red, and the discs having even numbers be blue. The objective is to transfer the entire tower to one of the other pegs, considering the following rules: each move consists of taking only one upper disk from one of the stacks and placing it on top of another stack; no disk may be placed on top of a smaller disk; no disk may be placed on top of a disk having the same colour. Theorem. The bicolour tower of Hanoi problem has a solution, and the minimal number of moves required to solve it is 2n — 1, where n is the number of disks.