בשנת 1883 הגיע לחנויות הצעצועים בפריז משחק עץ קטן ומוזר בשם "מגדל האנוי". על האריזה התנוסס שמו של הממציא: פרופסור נ' קלאוס מסיאם.

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

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

חוקי המשחק:

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

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

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

רמז דק

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

1, 3, 7, 15, 31 ... מה היחס בין כל מספר לזה שלפניו?

רמז עבה

חשבו רקורסיבית - כלומר, בנו את הפתרון של n מתוך הפתרון של n-1.

כדי להזיז את הדיסקית התחתונה והגדולה ביותר, שאלו: מה חייב לקרות קודם לכל n-1 הדיסקיות שמעליה? היכן הן יכולות להיות באותו רגע?

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

סמנו ב-T(n) את מספר המהלכים, ורשמו את הנוסחה שמקשרת בין T(n) ל-T(n-1).

פתרון

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

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

1. העברת n-1 הדיסקיות העליונות לעמוד העזר - T(n-1) מהלכים.

2. העברת הדיסקית הגדולה ליעדה - מהלך אחד.

3. העברת n-1 הדיסקיות מעמוד העזר אל מעל הגדולה - שוב T(n-1) מהלכים.

ומכאן נוסחת הנסיגה: T(n) = 2 × T(n-1) + 1, כאשר T(1) = 1.

נפתח: T(1)=1, T(2)=3, T(3)=7, T(4)=15, T(5)=31 - כל אחד מהם קטן באחד מחזקה של 2. וזה לא במקרה: אם נוסיף 1 לשני האגפים נקבל T(n)+1 = 2 × (T(n-1)+1). כלומר הסדרה T(n)+1 פשוט מוכפלת פי 2 בכל שלב ומתחילה ב-2, ולכן T(n)+1 = 2 בחזקת n.

ומכאן T(n) = 2 בחזקת n, פחות 1.

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

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

קץ העולם, מסתבר, יכול לחכות בסבלנות.

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