מגדלי האנוי

[רון חשבון]

מגדלי האנוי

אני כותב כאן משהו שהוא שילוב של חידה, משחק, בעיה מתמטית וגם סתם דבר מעניין לקרוא עליו... לפני זמן לא רב נכנסתי ללמד בכיתה י"א את השיעור הראשון ב"אינדוקציה". מנסיוני זהו שיעור מאד קשה, מופשט, ובעל אופי "הוכחתי" – ולמי שלא "חולה" על מתמטיקה זהו שיעור מאד משעמם. תוסיפו לזה שהיה יום שרבי במיוחד והשיעור היה בשעה אחת בצהריים ! מה עושים ? הדרך היחידה לעבור את השיעור הזה בשלום היא להביא לאנשים בכיתה משחק שירתק אותם. וכמובן שזה צריך להיות קשור לאינדוקציה... נזכרתי במשהו שהראו לי עוד בתור ילד, ונקרא "מגדלי האנוי" (The Towers of Hanoy) . למי שאינו מכיר, ניתן להסתכל בתמונה שצירפתי. אלו בסך הכל שלושה מוטות שעל אחד מהן מושחלות מספר דסקיות בגדלים שונים (בציור מופיעות 4 דסקיות, אבל אפשר לשחק את זה עם כל מספר שרוצים). עליך להעביר את כל הדסקיות מהמוט הזה אל המוט הימני, כך שבכל שלב מותר להעביר רק דיסקית אחת, ואין להניח אף דיסקית על דיסקית קטנה ממנה. מותר כמובן להיעזר במוט האמצעי. לפני שאני אגש לשאלה המתמטית כאן, אני מציע למי שלא נתקל בזה לנסות ולהגיע למטרה. כשמדובר ב 2-3 דסקיות זה די קל, אבל כדאי לנסות גם עם מספר גדול יותר. מי שמעוניין "לשחק" – מוזמן להיכנס לאתר הבא, שם אתם ממש יכולים לבחור את מספר הדסקיות ו"להזיז" אותן וירטואלית ממוט למוט. אבל מי שרוצה גם למצוא כאן צד מתמטי – אז הנה מספר שאלות : א. האם ניתן לבצע את המשחק עבור כל מספר של דסקיות ? האם ניתן להוכיח את זה ? (התשובה היא כמובן כן – אבל כדי לענות אני מציע קודם לקרוא את סעיף ב´) ב. נסו להוכיח שמספר המהלכים המינימלי הדרוש כדי להעביר את כל הדסקיות הוא 2ⁿ-1 (כאשר n הוא מספר הדסקיות). הכי קל זה להשתמש באינדוקציה מתמטית. ג. האם תוכלו לתת דרך קונסטרוקטיבית לבצע את המשחק ? כלומר, לא באמצעות ניחוש וטעייה, אלא דרך שתנחה אותנו בדיוק מה לעשות בכל שלב ? נסו להיעזר בסעיף הקודם. אני אולי גם אוסיף בשלב זה שנושא האינדוקציה, למרות שנראה כמו פרק מופשט וחסר שימוש, יכול להיות מאד פרקטי. ההוכחה באינדוקציה של סעיף ב´ ממש מדריכה אותנו איך לשחק את המשחק !

רון חשבון α•βƒ²(Δ)³+πº∑Ǿ ℓim(x→∞)ε∫¼±

 

[sharc]

דרך קונסטרוקטיבית לבצע את המשחק

יש N דיסקיות. 1) העבר N-1 דיסקיות לעמוד הפנוי (לא לעמוד הסופי) 2) העבר את הדיסקית ה N (האחרונה והכי גדולה ) לעמוד הסופי 3) העבר את N-1 הדיסקיות מהעמוד הפנוי לעמוד הסופי איך מעבירים את N-1 הדיסקיות לעמוד הפנוי ) העבר N-2 דיסקיות לעמוד הסופי 2) העבר את הדיסקית ה N-1 לעמוד הפנוי 3) העבר את N-2 הדיסקיות מהעמוד הםופי לעמוד הפנוי וכך הלאה רואים שכל שלב יש בו פי 2 ועוד 1 העברות ועל זה מבוססת ההוכחה

 

[GalRatz]

באינדוקציה

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

 

[רון חשבון]

וכמובן צריך להוסיף...

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

רון חשבון α•βƒ²(Δ)³+πº∑Ǿ ℓim(x→∞)ε∫¼±

 

[רק עכשיו נכנסתי]

זאת בעיה מאוד מפורסמת במדעי המחשב

מגדלי הנוי קשורים גם לריקורסיה (נוסחאות נסיגה) ולא רק לאינדוקציה

 

[yontanbn]

טרמינולוגיה

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

 

[רון חשבון]

אגדה או מציאות ?

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

האם יש לנו מקום לחשש ? (כעזרה לתשובה אני מציע גם לקרוא את השירשור שלמעלה)

רון חשבון α•βƒ²(Δ)³+πº∑Ǿ ℓim(x→∞)ε∫¼±

 

[פייד-ראותא]

הייתי אומר שייקח להם הרבה מאוד

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

פייד!

 

[The Ancient Mariner]

עשיתי חישוב קטן...

בהנחה שהם מכירים את האלגוריתום, ולוקח להם שניה אחת להעביר כל טבעת (זה הזמן הממוצע שלוקח לי על המחשב... ככה שהם צריכים להיות ממש מהירים) אז יקח להם 600,000,000,000 שנים (!!!!) לסיים את זה! (המספר מעוגל מין הסתם!)

 

[רון חשבון]

ווהאוו ! עכשו נרגעתי... ../images/Emo9.gif

 

[The Ancient Mariner]

דרך אגב...

יצא לך להסתכל ולראות האם הם בכלל בכיוון הנכון? מתי הם התחילו עם זה?

 

[The Ancient Mariner]

הצלחתי! הצלחתי!

*אלון מנפח את החזה בגאווה* לא נשברתי, לא הסתכלתי על התשובות שלכם וניסיתי לפתור לבד, תראו מה זה, אחרי איזה 5 שעות של חשיבה מרוכזת הצלחתי! (עכשיו אני מקווה שאני אצליח להסביר את עצמי) למעשה כל פעם צריך להזיז שתי טבעות לעמוד מסויים, טבעת שלישית לעמוד האחר, ואז את השתי טבעות לעמוד שהזזנו את השלישית. קל לראות שהמספר המינימלי של צעדים שבהם ניתן להעביר 2 טבעות הוא 3 מהלכים, ככה שלמעשה יש לנו במהלך המשחק כמות מסויימת של מהלכים (מיד נגדיר אותה כפונקציה של n) הדורשת שלוש הזזות. בנוסף לאותם מהלכים, צריך כל פעם להזיז טבעת אחת בין מהלך למהלך, ככה שכמות ה 1 שיהיו לנו, תהיה פחותה בפעם אחת מכמות ה 3 שיהיו לנו. למעשה ע"י כך הוכחנו שגם באינסוף טבעות הדבר אפשרי, מכיוון שכל מה שצריך זה לחזור על אותו מהלך של הזזת שתי טבעות כמות מסויימת של פעמים. עכשיו, רשמתי את כמות הפתרונות הנחוצה כל פעם וניסיתי למצוא איבר כללי: כאשר מדובר ב-3 טבעות: 2 מהלכים של 3, 1 של 1 כאשר מדובר ב-4 טבעות: 4 מהלכים של 3, 3 של 1 כאשר מדובר ב-5 טבעות: 8 מהלכים של 3, 7 של 1 . . . כאשר מדובר ב-n טבעות:

3*2^(n-2) + 2^(n-2)-1​

ןלמעשה אחרי שמפשטים את המשוואה ניתן להגיע לביטוי שרון ביקש (2 בחזקת n פחות 1)

 

[רון חשבון]

בהחלט...

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

רון חשבון α•βƒ²(Δ)³+πº∑Ǿ ℓim(x→∞)ε∫¼±

 

[net4u1]

שבדיות ואינדוקציות

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

 

[The Ancient Mariner]

רק ש...

המורה שלכם תיאר כפי שאמרת הכללה, כלומר הוכחה אינדוקטיבית לא שלמה, אלא שנובעת רק ע"פ הנחה... למעשה המורה שלכם גרם לכם לראות את המתמטיקה כמקצוע שמתבסס על הנחות חצי שלמות, ולא כמקצוע ששואף לשלמות בדיוק... וזה מזכיר לי סיפור קטן שקראתי איפשהו: מסופר על אסטרונום, פיזקאי ומתמטיקאי שנסעו ברכבת בגרמניה, לפתע ראה האסטרונום כבשה שחורה על אחת הגבעות, ומיד אמר: ואוו! כל הכבשים בגרמניה הן שחורות! הפיזקאי מיד ביטל אותו בבוז: לאאאא, רק חלק מהכבשים בגרמניה הן שחורות. המתמטיקאי הרים את הראש הסתכל ואמר: לפחות כבשה אחת בגרמניה, על גבעה אחת, בצידה האחד היא שחורה. השיטה של רון הרבה יותר מוצלחת... דרך אגב, אם אינני טועה המורה שלי בשיעור ראשון של אינדוקציות לימד אותנו את זה גם בדרך סיפורית, רק שהוא אמר לנו: נניח שצעד כלשהו שאני עושה הוא מטר אחד, ושהצעד הבא אחריו הוא גם מטר - האם זה אומר שכל צעד שאני אעשה יהיה מטר? ואז התפתח על זה דיון קצר, שבסופו של דבר לפחות חלק ניכר מהכיתה הבין את הרעיון... דרך אגב - אני סבור שיש לנסות לתת לתלמידים להגיע לעיקרון של אינדוקציה בעצמן, העיקרון הוא לא מסובך, ואני חושב שלפחות בכיתות של 5 יח"ל, אם יתנו לתלמידים אתגר לנסות לפתח כלי מתמטי שבעזרתו יוכלו להוכיח כי ביטוי מסויים מתקיים לכל n טבעי עד אינסוף - מישהו מהם יצריך לפתח את העיקרון של אינדוקציה... (ואם לא, אפשר לנהל דיון בכיתה על איזה שיטות כל אחד מהם חשב וכו´ וכו´, ואז להדריך אותם כביכול "לגלות" את העיקרון בעצמם... אני חושב שאז האנשים יבינו הכי יפה את העיקרון של אינדוקציה, וגם יקשיבו כולם בשיעור)