Wieża Hanoi

[Pan Szczepan]

Witam.
Przez jakiś czas próbowałem znaleźć rozwiązanie tego problemu ale bez większych rezultatów. Temat wieży Hanoi był tutaj poruszany ale dotyczył minimalnej liczby ruchów.

Problem jest następujący:
Mamy wieże Hanoi składająca się z 4 krążków. (Wieża Hanoi składa się z 3 słupków oraz 4 krążków z których każdy ma inny rozmiar. Krążki można przemieszczać na dowolny słupek jednak większy krążek nie może znajdować się na mniejszym. ) Ile jest możliwych kombinacji położeń tych krążków?

Nie mam żadnych podstaw jeśli chodzi o kombinatorykę więc nawet nie mam pomysłu jak to rozwiązać. Próbowałem zliczyć liczbę możliwych kombinacji i wychodzi mi 87.

[norwimaj]

Powinno wyjść \(\displaystyle{ 3^4=81}\), bo każdy kolejny krążek, poczynając od największego, można umieścić na jednym z trzech słupków.