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

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