Konkurs nr 145
informacje | zadania | ranking | ostatnie zgłoszenia
Wieża Hanoi
Wieża Hanoi to problem polegający na odbudowaniu, z zachowaniem kształtu, wieży z krążków o różnych średnicach, przy czym podczas przekładania wolno posługiwać się dodatkowym drążkiem. Należy jednak przestrzegać zasady, która mówi, że nie można położyć krążka większego na mniejszym oraz jednorazowo można przenieść tylko jeden krążek. Dla wieży złożonej z dziesięciu krążków minimalna liczba ruchów potrzebna do ich przeniesienia, równa jest $2^{10} - 1 = 1023$.
Zmieńmy trochę zasady. Tak jak poprzednio mamy trzy drążki i $10$ krążków o średnicach $1,2, \ldots, 10$ ułożonych na drążku A. Celem jest przeniesienie, zgodnie z powyższymi zasadami, wszystkich krążków o średnicach nieparzystych na drążek B, a krążków o średnicach parzystych na drążek C. Jaka jest minimalna liczba ruchów potrzebnych do rozdzielenia krążków o średnicach parzystych i nieparzystych?