מתמטיקה תיכונית/אלגברה תיכונית/אינדוקציה מתמטית/אינדוקציה של טענה כללית/תרגילים

תרגילים

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

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

תרגילים בדרגת קושי גבוהה

1. (*) האם בבעית השד אשר נוסחה קודם קיים סכום שעבורו כבר כדאי לקנות את המנורה? האם הייתם קונים אותה עבור, למשל מליון שקלים? מה בקשר ל-999,999? האם עקרון ההוכחה באינדוקציה אינו נכון?
2. בעיית בוחן הפתע (או בעיית התליין): נגדיר בוחן פתע, כבוחן אשר לא ניתן לקבוע מראש (גם יום אחד מראש) באיזה יום הוא יתרחש. יוכבד היא מורה בבית ספר יסודי בו לומד התלמיד המתחכם ירמיהו. יוכבד מגיעה לכיתה ומודיעה בחגיגיות כי בחודש הבא יתקיים בוחן פתע. כעבור שניות אחדות מצביע ירמיהו ומלין על כי לשיטתו "לא ניתן לקיים בוחן פתע בחודש הבא". "מדוע?", שואלת יוכבד והתלמיד השנון מודיע בחגיגיות כי הוא "הוכיח" באינדוקציה כי לא ניתן לקיים בוחן פתע בחודש הבא כי ביום ה-28 לחודש הרי שלא ניתן לקיים את הבוחן כי אז ביום ה-27 כבר ניתן לאמר בוודאות שהבוחן הוא ב-28 וכו'. נסחו את טענתו של ירמיהו באופן מתמטי והוכיחו באינדוקציה כי לא ניתן לקיים את בוחן הפתע.
3. אנו נוכיח שבקבוצה בת מספר טבעי של סוסים כל הסוסים הם בני אותו צבע:

   "הוכחה":

   • עבור קבוצה בת סוס אחד, ברור שהטענה נכונה, כי כל הסוסים באותו הצבע (יש רק אחד).
   • נניח שעבור קבוצה בת-$\;k$ סוסים הטענה נכונה.
   • נבדוק עבור קבוצה בגודל $\;k+1$ סוסים. מתוך הקבוצה בת ה-$\;k+1$ סוסים נבחר קבוצה בת $\;k$ סוסים. ידוע על פי הנחת האינדוקציה שבקבוצה זו כל הסוסים באותו צבע. נסמנו ב-$\;C$. נותר לנו סוס אחד בחוץ אשר צבעו אינו ידוע. הסוס יסומן ב-$\;s$ וצבעו אינו ידוע. כעת נוריד מהקבוצה של ה-$\;k$ סוסים בעלי הצבע $\;C$ סוס אחד ואת מקומו יחליף הסוס $\;s$. נותרנו עם $\;k$ סוסים, ולכן הם כולם באותו צבע. מכיוון ששאר הסוסים (אלו שלא הוחלפו כלל והיו כל הזמן בקבוצה המקורית בת ה-$\;k$ סוסים) לא החליפו את צבעם רק משום ששינינו את הקבוצה ולפי הנחת האינדוקציה שאומרת שבכל קבוצה בת $\;k$ סוסים כל הסוסים באותו צבע, נותרנו עם המסקנה ש-$\;C$ הוא הצבע של $\;s$ ומכאן מגיעים למסקנה שגם קבוצה בת $\;k+1$ סוסים מכילה רק סוסים באותו צבע. מסקנה: על פי משפט ההוכחה באינדוקציה כל הסוסים הם באותו צבע.

   הרי ברור שלא כל הסוסים באותו צבע. היכן השגיאה בהוכחה?

4. לאור התוצאות של שלוש השאלות האחרונות, האם יש צורך לסייג את השימוש באינדוקציה? נמקו.