מגדלי האנוי

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

היתכנות פתרון המשחק - הוכחה באינדוקציה

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

מספר הצעדים הנחוצים לפתרון

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

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

מכאן ניתן לפתור את החידה ב- צעדים. כאמור לעיל, פתרון זה הוא גם היעיל ביותר - לא ניתן לפתור את החידה במספר קטן יותר של צעדים. במונחים של מדעי המחשב, 
מספר ההעברות המינימלי להעברת n דיסקיות הוא , כלומר הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה, ולכן זהו אלגוריתם בעל סיבוכיות מעריכית  - לבעיה אין פתרון "יעיל". 
בהקשר של האגדה של לוקאס, מספר הצעדים שלוקח להעביר מגדל בעל 64 דיסקיות הוא , ומכאן שאפילו אם הנזירים יכולים להעביר דיסקיות בקצב של אחת לשנייה (מבלי להתבלבל), הזמן שיידרש להם להעביר את כל המגדל הוא כ-580 מיליארד שנים - פי 42 מגילו המוערך של היקום.

הקשר למספרים בינאריים

אם נכתוב את סדרת המספרים הטבעיים בבסיס בינארי: 1, 10, 11, 100, 101, 110, ... אזי הספרה הראשונה שאיננה 0 מייצגת את הדיסקית שיש להזיז באותו מהלך. לדוגמה במהלך הרביעי, יש להזיז את הדיסקית השלישית, מכיוון שבייצוג הבינארי של המספר 4 שהוא 100, הספרה הראשונה שאיננה 0 היא הספרה השלישית.

הקשר למשולש שרפינסקי

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