اگر $n$ مهره به ترتیب شماره در داخل میله‌ی $A$ باشند و دو میله‌ی $B$ و $C$ خالی باشند٬ آن‌گاه حداقل با $2^n-1$ حرکت می‌توان مهره‌ها را از $A$ به $C$ منتقل کرد به طوری که مهره‌های با شماره‌ی بزرگ‌تر هرگز روی مهره‌های با شماره‌ی کوچک‌تر قرار نگیرند.

اثبات: فرض می‌کنیم با حداقل $h_{n-1}$ حرکت بتوان $n-1$ مهره با شرایط مذکور را از $A$ به $C$ منتقل کرد. ابتدا $n-1$ مهره را با $h_{n-1}$ حرکت از $A$ به $C$ منتقل می‌کنیم. فقط مهره‌ی $n$ در داخل میله‌ی $A$ باقی می‌ماند. با یک حرکت مهره‌ی $n$ را به $C$ منتقل می‌کنیم و با$h_{n-1}$ حرکت $n-1$ مهره‌ی دیگر را از $B$ به $C$ انتقال می‌دهیم. پس مجموع حرکات برای چنین کاری برابر $h_{n-1}+1+h_{n-1}$ یعنی $2h_{n-1}+1$ خواهد بود. پس:

$$h_n=2h_{n-1}+1 \quad\quad\quad (1)$$

می‌دانیم:

$$h_1=1,h_2=3,h_4=7,...$$

با استفاده از رابطه‌ی بازگشتی $(1)$ معلوم می‌شود که:

$$h_n=2^n-1$$

برای حل مسئله مورد نظر الگوریتم زیر را پیاده می‌کنیم:

• مهره‌ی ۱ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۲ را به میله‌ی ۱ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۱ را به میله‌ی ۱ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۴ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۱ تا ۳ را به میله‌ی ۳ منتقل می‌کنیم(با توجه به لم۷٬ حرکت).

پس مجموعا ۱۱ حرکت می‌شود و با کم‌تر از این٬ ممکن نیست.

برای حل مسئله الگوریتم زیر را پیاده می‌کنیم:

• مهره‌ی ۲ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۱ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۳ را به میله‌ی ۲ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۱ را به میله‌ی ۱ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۱ را به میله‌ی ۲ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۵ را به میله‌ی ۳ منتقل می‌کنیم(یک حرکت).
• مهره‌ی ۱ تا ۴ را به میله‌ی ۳ منتقل می‌کنیم(با توجه به لم۱۵٬ حرکت).

پس مجموعا ۲۲ حرکت می‌شود و با کم‌تر از این٬ ممکن نیست.