משתמש:טוקוני/שיר אהבה למחשבה/מגדלי האנוי

מגדלי האנוי

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

משחק מגדלי האנוי

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

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

עוד חידות עם מגדלי האנוי

אח"כ גלי ביקשה שנספור כמה צעדים לוקח להעביר כל מגדל. אז התחלנו לספור, מגדל עם דיסקיות אחת לוקח צעד אחד להעביר אותו. מגדל עם שני דיסקיות לוקח 3 צעדים להעביר אותו, ומגדל עם 3 דיסקיות לוקח 7 צעדים להעביר אותו, וכך הלאה.... ואז גלי ביקשה שנשרטט טבלה ונכתוב את כל התוצאות שקיבלנו. ואתם יכולים לראות את הטבלה בעמוד ממול. פתאום איילת צעקה "אני יודעת יש פה כלל פשוט!", ואולי גם אתם יכולים לגלות את הכלל הזה. אם לא ניתן לכם כמה רמזים. קודם כל אתם יכולים לראות שכל מספר צעדים הוא פעמיים מספר הצעדים הקודם ועוד אחד. לדוגמא 7=3*2+1, 15=7*2+1, וכך הלאה. אח"כ גלי סיפרה לנו שכלל כזה נקרא כלל 'רקורסיבי', ורקורסיבי זה פשוט אומר שכל מספר מקבלים אותו לפי המספר הקודם. אתם יכולים לנסות להבין לבד למה הכלל הזה עובד. חוץ מזה יש גם חוקיות אחרת שמספר הצעדים להעביר מגדל, זה שתיים בחזקת מספר הדיסקיות פחות אחד. לדוגמא להעביר מגדל עם 3 דיסקיות לוקח 2^3-1=7 צעדים. מאיפה הכלל הזה בא? אני לא יודע, אבל אפשר להוכיח שהוא נכון, בעזרת הכלל הקודם שראינו, באינדוקציה. אגב גלי אמרה שבגלל זה לא צריך לפחד מכך שהנזירים יגמרו בקרוב להעביר את מגדלי האנוי ואז יבוא סוף העולם, בגלל שמספר הצעדים שלוקח להעביר מגדל עם 64 דיסקיות הוא: 2^64-1 שזה אומר שאפילו עם לוקח רק שניה אחת להעביר דיסקית, עדיין ייקח לנזירים יותר זמן מגיל היקום להעביר את כל המגדל.

איך לנצח במגדלי האנוי ברמאות

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

לפעמים אסור להגיד וכך הלאה

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

שודדים שנגמר להם הכסף

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