אל תנסו לדמיין שישים וארבע דיסקיות. התחילו מאחת, אחר כך שתיים, אחר כך שלוש, ורשמו את מספר המהלכים המינימלי בכל מקרה. הסדרה שתקבלו מזוהה מיד.

חשבו רקורסיבית. כדי להעביר מגדל של n דיסקיות מהמוט הראשון לשלישי, חובה בשלב מסוים להזיז את הדיסקית הגדולה מכולן. כדי שזה יתאפשר, המוט השלישי חייב להיות ריק לגמרי וכל n מינוס אחת הדיסקיות שמעליה חייבות להיערם על המוט האמצעי.

כלומר: פותרים בעיה של n מינוס אחת, מזיזים מהלך אחד, ופותרים שוב בעיה של n מינוס אחת. סמנו ב-H(n) את מספר המהלכים וכתבו את הנוסחה שנובעת מכך.

מספר המהלכים המינימלי הוא שתיים בחזקת n פחות אחת.

הנימוק: כדי להזיז את הדיסקית התחתונה, יש להעביר קודם את כל n מינוס אחת הדיסקיות שמעליה למוט העזר - וזו בדיוק אותה בעיה בגודל קטן יותר. אחר כך מהלך אחד מעביר את הדיסקית הגדולה ליעד, ולבסוף חוזרים על אותה עבודה כדי להעביר את n מינוס אחת הדיסקיות מהמוט האמצעי אל היעד.

מכאן H(n) = 2 כפול H(n-1) ועוד 1, כאשר H(1) שווה 1. פתרון הנוסחה נותן H(n) = 2 בחזקת n פחות 1.

אפשר לבדוק: דיסקית אחת - מהלך אחד. שתיים - שלושה מהלכים. שלוש - שבעה. ארבע - חמישה עשר. עשר דיסקיות דורשות כבר 1023 מהלכים.

וכמה זמן ייקח לכוהנים?

עבור שישים וארבע דיסקיות מדובר ב-2 בחזקת 64 פחות 1 מהלכים, כלומר 18,446,744,073,709,551,615 מהלכים.

במהלך אחד בשנייה, ובלי הפסקה אחת, זמן העבודה הוא כ-584 מיליארד שנה. לשם השוואה, גיל היקום מוערך בכ-13.8 מיליארד שנה בלבד - כלומר הכוהנים היו צריכים להתחיל בערך ארבעים ושתיים "יקומים" לפני שלנו כדי לסיים היום.

נקודה נוספת ויפה: מספר המהלכים אינו רק גדול, הוא גם מדויק - אין דרך לחסוך אפילו מהלך אחד. בנוסף, לרצף המהלכים האופטימלי יש קשר מפתיע: אם רושמים את מספרי המהלכים בבינארית, הדיסקית שיש להזיז בכל שלב נקבעת לפי מיקום הסיבית הימנית ביותר שדולקת. זהו גם הקשר הידוע בין מגדלי הנוי לקוד גריי ולעקומת סירפינסקי.