חידות חשיבה (164)

מגדלי האנוי

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

המשחק כולל שלושה מוטות אנכיים (ה"מגדלים" השחורים שבאיורים) שעליהם ניתן להשחיל דיסקיות (המלבנים שבאיור). כל הדיסקיות הן בגדלים שונים. בתחילת המשחק יש 4 דיסקיות שמסודרות על פי גודלן על מגדל א' (ראו איור), כשהגדולה ביותר למטה והקטנה ביותר למעלה.

עליכם להעביר את כל הדיסקיות ממגדל א' למגדל ג' (מותר להיעזר במגדל ב'), כלומר לעבור מהמצב המתואר באיור 1 למצב המתואר באיור 2. זאת בכפוף לשני חוקים :(א) בכל צעד מותר להזיז רק דיסקית אחת ממגדל למגדל; (ב) אסור להניח דיסקית על דיסקית שקטנה ממנה.

אם הצלחתם לבצע את המשימה עם 4 דיסקיות, נסו לפתור את אותה חידה עבור 5 דיסקיות.

מי שמעוניין להתנסות מעשית בפתרון יכול להשתמש בכמה חפצים ביתיים כגון אלה שבתמונת הכותרת.

רמזים (אם אתם זקוקים להם):

(א) אל תזיזו את אותה דיסקית בשני צעדים עוקבים.

(ב) לכל מספר N של דיסקיות יש מספר צעדים מינימלי עד לפתרון. המספר הוא (2 בחזקת N) מינוס 1, כלומר 15 צעדים עבור 4 דיסקיות ו-31 צעדים עבור 5 דיסקיות. נסו להגיע לפתרון גם אם עברתם את המספר המינימלי.

פתרון:

הפתרון עבור 4 דיסקיות מתואר באיור 3.

כדי לחסוך במקום נתאר את הפתרון עבור 5 דיסקיות בטבלה הבאה. הדיסקיות מסומנות במספרים לפי הגודל. מספר גדול יותר פירושו דיסקית גדולה יותר. במצב ההתחלתי דיסקית 5 היא למטה, מעליה דיסקית 4, מעליה דיסקית 3, מעליה דיסקית 2 ולמעלה דיסקית 1. הרישום בטבלה הוא בצורה (מגדל ג'-מגדל ב'-מגדל א'). כך למשל המספר 145-2-3 פירושו שדיסקית 3 היא במגדל ג', דיסקית 2 היא במגדל ב' ודיסקיות 145 הן במגדל א'.

הפתרון הקצר ביותר מכיל את 31 הצעדים הבאים (מימין לשמאל):

12345-0-0   2345-0-1   345-2-1    345-12-0   45-12-3    145-2-3   145-0-23   45-0-123   5-4-123

5-14-23       25-14-3     125-4-3    125-34-0   25-34-1    5-234-1   5-1234-0   0-1234-5   1-234-5

1-34-25       0-34-125   3-4-125    3-14-25     23-14-5    123-4-5   123-0-45   23-0-145   3-2-145

3-12-45       0-12-345   1-2-345    1-0-2345   0-0-12345

הערות:

(1) ניתן להבחין שבפתרון עבור 5 דיסקיות מעבירים תחילה את הדיסקית הגדולה ביותר למגדל ג', ואז משתמשים בפתרון עבור 4 דיסקיות. זה נכון לגבי כל מספר של דיסקיות – תחילה מעבירים את הדיסקית הגדולה ביותר למגדל ג', ואז משתמשים בפתרון עבור מספר קטן באחד של דיסקיות. פתרון כזה, שבו משתמשים בשלב מוקדם יותר של הפתרון, נקרא פתרון בשיטת הרקוּרסיה (נסיגה).

(2) נניח שאדם זריז במיוחד מצליח, מבלי להתבלבל, להעביר דיסקית ממגדל למגדל בכל שנייה. עבור כמה דיסקיות לכל היותר הוא יספיק לבצע את הפתרון אם הוא יעשה זאת מרגע לידתו ועד יום מותו בגיל 120 שנים? ובכן, 120 שנים הם קרוב ל-3.8 מיליארד שניות. אם יש 32 דיסקיות אזי מספר הצעדים המינימלי הוא (2 בחזקת 32) מינוס 1, כלומר 4.3 מיליארד, ולכן אותו אדם זריז לא יספיק לבצע את המשימה עבור 32 דיסקיות, אלא עבור 31 דיסקיות לכל היותר.

אם יש 59 דיסקיות אזי מספר הצעדים המינימלי הוא (2 בחזקת 59) מינוס 1, כלומר 576 מיליון-מיליארדים. במקרה זה לא יספיק לביצוע הפתרון אפילו הזמן מאז שנוצר היקום שהוא 13.8 מיליארד שנים, כלומר 435 מיליון-מיליארדים שניות.

שיתוף ב facebook
Facebook
שיתוף ב twitter
Twitter
שיתוף ב linkedin
LinkedIn
שיתוף ב whatsapp
WhatsApp
שיתוף ב email
Email

5 תגובות

  1. כל שבוע אני נדהם מחדש ממיגוון החידות

    כל שבוע אני נדהם מחדש ממגןון החידות והכיוונים שלהן, והפתרונןת

כתיבת תגובה

האימייל לא יוצג באתר.

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

עשוי לעניין אותך