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

מגדלי האנוי

אומרים שכאשר אלוהים ברא את העולם, הוא בנה מקדש גדול ובתוכו הציב שלושה עמודים גדולים, ועל אחד העמודים הניח 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

כמה קל להוכיח דברים באינדוקציה! ומכאן אנחנו רואים שמספר המהלכים הדרושים בשביל לסיים את המשחק הוא רק 2^64-1. למזלנו המספר הזה הוא די גדול. 2^64-1 שניות זה בערך 10^30 שנים שזה הרבה הרבה מאוד זמן. פיסיקאים היום מעריכים שבעוד ? שנים השמש שלנו תתפוצץ, ולכן זה יקרה הרבה לפני שהנזירים בהאנוי יגמרו להעביר את כל הדיסקיות שלהם.

למה צריך להזהר?

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

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

אבל יש סיבה לכך שמתמטיקאים אוהבים כל-כך להזהר, והיא שכאשר לא נזהרים נוטים לעשות טעויות.

פרדוקס הסוסים

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

הוכחות שיקריות

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

חזרה להאנוי

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

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