سوال

سه میله با شماره‌های ۱,۲و۳و چهار مهره‌ی سوراخدار با شماره‌های ۱ تا ۴ مطابق شکل زیر داده شده است :

می‌خواهیم با حرکت دادن این مهره‌ها و رعایت قواعد زیر کلیه‌ی مهره‌ها را به صورت زیر بر میله‌ی سوم ببریم :

در هر حرکت تنها یک مهره حرکت داده شود.
هیچ‌گاه مهره‌ی با شماره‌ی بزرگتر بر روی مهره با شماره‌ی کوچیکتر قرار نگیرد.
آیا می‌توان با کمتر از ۱۱ حرکت این کار را انجام داد؟ ( اثبات کنید‌)

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

اثبات : فرض می‌کنیم با حداقل h_{n - 1} حرکت بتوان n - 1 مهره با شرایط مذکور را از A به C منتقل کرد. ابتدا n - 1 مهره   را با h_{n - 1} حرکت از A به B منتقل می‌کنیم. فقط مهره‌ی 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     (1)A

می‌دانیم :

h₁ = 1 , h₂ = 3 , h₄ = 7 , …A

با استفاده از رابطه‌ی بازگشتی (۱) معلوم می‌شود که :
برای حل مسأله مورد نظر الگوریتم زیر را پیاده می‌کنیم :
مهره‌ی ۱ را به میله‌ی ۳ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۲ را به میله‌ی ۱ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۱ را به میله‌ی ۱ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۴ را به میله‌ی ۳ منتقل می‌کنیم ( یک حرکت ).
مهره‌ی ۱ تا ۳ را به میله‌ی ۳ منتقل می‌کنیم (با توجه به لم , ۷ حرکت ).
پس مجموعأ ۱۱ حرکت می‌شود و با کمتر از این , ممکن نیست.