משתמש:טוקיוני/שיר אהבה למחשבה/מגדלי האנוי ואינדוקציה: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
דף חדש: ==מגדלי האנוי== left|250px אומרים שכאשר אלוהים ברא את העולם, הוא בנה מקדש גדול ובתוכו הציב ...
(אין הבדלים)

גרסה מ־01:24, 17 בינואר 2009

מגדלי האנוי

 

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

עם יש מישהו, מבין הקוראים שלא שיחק במשחק הזה בתור ילד, אני ממליץ לו בחום ללכת לחנות הצעצועים הקרובה ולקנות לעצמו את המשחק, או לחתוך כמה מלבנים מנייר ולשחק איתם. מי שכן שיחק במשחק יכול להעיד שלפתור את החידה עבור מגדל עם מספר קטן של דיסקיות, 3 או 4 זה לא קשה במיוחד. לפתור את החידה כאשר יש 6 דיסקיות זה כבר לא קל בכלל, ולכן סביר להניח שזה לא יהיה קל בכלל לפתור את החידה עבור מגדל עם 64 דיסקיות. אבל האם בכלל זה אפשרי? האם העולם שלנו אי פעם ייחרב?

אינדוקציה

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

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

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

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

ניתן לפתור את מגדלי האנוי

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

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

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

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

כמה זמן נותר לעולם?

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

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

H(n+1)=2H(n)+1

נוסחא מהסוג הזה, המבטאת איבר בסידרה על פי האיבר הקודם בסידרה נקראת נוסחאת נסיגה. בוא נראה מה הנוסחא הזאת אומרת לנו. ובכן אנחנו יודעים שלוקח רק מהלך אחד להעביר מגדל עם דיסקית אחת בלבד, ולכן H(1)=1, ואם נציב את זה בנוסחא נקבל ש: H)2(=2H)1(+1=3, H)3(=7, H)4(=15, וכך הלאה. אנחנו מקבלים את הסידרה 1,3,7,17,31,... האם היא נראית לכם מוכרת?

הסידרה הזאת קרויה מספרי מרסן, והיא מתקבלת על ידי החסרה של 1 מהחזקות של 2: 1=2-1

3= 4-1

7= 8-1

31 = 32-1

וכך הלאה...

רגע אחד, האם מותר לנו להשתמש במילה 'וכך הלאה?' אולי זה רק צירוף מקרים שהמספרים הראשונים שקיבלנו בסידרה הם באמת 1 פחות מחזקות של 2, אולי אם נמשיך הלאה צירוף המקרים הזה יישבר?

אבל ראינו בדיוק איך ומתי מותר לנו להשתמש במילים 'וכך הלאה', ראינו שבשביל להשתמש במילים האלו אנחנו צריכים להוכיח את שני שלבי האינדוקציה. קודם כל אנחנו צריכים להראות שהכלל שגילינו הוא נכון עבור האיבר הראשון בסידרה. ואכן H)1(=2^1-1. שנית אנחנו צריכים להוכיח את שלב האינדוקציה, כלומר להראות שאם הנוסחא נכונה לאיבר הn, כלומר אם אכן H(n)=2^n-1 אזי הנוסחא גם נכונה לאיבר ה n+1. אבל זה קל להוכיח: H(n+1)=2H(n)+1=2*(2^n-1)+1=2^)n+1)-1