בתשובה לדורפל, 21/08/06 0:27
אלכסנדרוביץ' לבני-תמותה 403817
*נכון, אחת שתים שלוש ורבע הם המצאה, אבל מספר מרוכב הוא המצאה שסותרת את הראשונה.
*הסלידה שלי ממתמטיקה התפתחה דווקא בכיתה י'א תודות לאינדוקציה ומספרים מרוכבים (מפליא דווקא מקטורים לא סלדתי).
*לאיזה דורפל אני עונה עכשיו (דורפל תמסור לדורפל שלא יפה שלא אמר שיש לו פיצול אישיות -זה קצת מבלבל)?
אלכסנדרוביץ' לבני-תמותה 403829
אינדוקציה זה אכן תמוה. אף פעם לא הבנתי למה מלמדים את זה כך. בכל התואר הראשון שלי לא השתמשתי אף פעם באינדוקציה כדי להוכיח משהו מהדברים שהוכיחו בכיתה במשך שבועות ארוכים (ומשתמשים באינדוקציה כל הזמן).

מה שכן כדאי ללמד את התלמידים זה איך מוכיחים באינדוקציה שכל הסוסים שחורים ולמה זה לא נכון.
אלכסנדרוביץ' לבני-תמותה 403832
היית צריך לדבר עם המורה שלי למתמטיקה, כל העולם היה חרב והוא עדיין היה מתעקש שכל הסוסים שחורים...
אלכסנדרוביץ' לבני-תמותה 403837
איך?
אלכסנדרוביץ' מתעלל בסוסים 403838
מכיוון שאני יודע שקיים סוס שחור ("הסיח השחור") אני אוכיח משהו יותר פשוט: שלכל הסוסים בעולם אותו צבע. לכן הם בטח מאותו צבע כמו הסוס השחור ולכן כולם שחורים.

כלומר, בצורה פורמלית מה שאני צריך להוכיח הוא שבכל קבוצה של n סוסים, כל הסוסים מאותו הצבע.

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

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

עכשיו כשאני כותב את זה אני נדהם מכמה שהטריק שקוף (בשעתו כששמעתי את החידה לא הצלחתי בהתחלה למצוא את הבעיה), אבל כנראה שזה בגלל שאני כותב גרוע.
אלכסנדרוביץ' מתעלל בסוסים 403842
זה שהכנסת את יוסי הממזר הכחול לקבוצה של סייחים שחורים לא תהפוך את הממזר גם לשחור, לכן אני לא מבינה את ההוכחה...
אלכסנדרוביץ' מתעלל בסוסים 403861
אז את לא מבינה אינדוקציה. לפני שהוא הכניס את יוסי, הוא הניח ש*כל* קבוצה עם k סייחים, מכילה רק סייחים שחורים. מעצם היותו של יוסי חבר בקבוצה כזאת, הוא בהכרח (במידה וההנחה נכונה, זאת אומרת) שחור. הכללתו בקבוצה לא הפכה אותו לשחור, היא רק הוכיחה לנו, המביטים מהצד, את היותו שחור.
מתמטיקה מתעללת בי 403900
נכון, אני לא מבינה מספרים מורכבים ולא אינדוקציה ואני מודעת לזה. הגיון ומתמטיקה (לא כולל מטריצות,טריגונומטריה, גאומטריה ווקטורים) לא מתיישבים אצלי ביחד (אני מעדיפה לדון על הדנ"א שמקודד לצבע שחור מאשר להוכיח באינדוקציה שכל הסוסים בקצובה K שחורים...).
הזכרתי כבר שאני לא אוהבת מתמטיקה?
אלכסנדרוביץ' מתעלל בסוסים 403941
אם איני טועה אתה סטודנט לתואר ראשון. האם אתה מתכוון להמשיך לתואר שני?
אלכסנדרוביץ' מתעלל בסוסים שמדברים עברית 403990
אני לא בטוח שיתנו לי לסיים את הראשון.
עכשיו ענה אתה לי בבקשה - למה אתה שואל?
אלכסנדרוביץ' מתעלל בסוסים שמדברים עברית 403995
כי לאור פתיחת תגובה 403861, אני תוהה האם בכוונתך לתרגל.
אלכסנדרוביץ' מתעלל בסוסים שמדברים עברית 404001
מה לא בסדר בהסבר שם?
אלכסנדרוביץ' מתעלל בסוסים שמדברים עברית 404052
אני לא חושב שיש בעיה בהסבר, אלא בהערה שלפניו.
אלכסנדרוביץ' מתעלל בסוסים שמדברים עברית 404065
הטון שלה בחלק של הדיון שעסק במספרים מרוכבים לא היה ''אני לא מבינה'', הוא היה ''זה לא נכון''. הטון הזה עדיין הדהד באוזניי, והשפיע גם על התגובות הבאות שלי.
אלכסנדרוביץ' מתעלל בסוסים שמדברים עברית 404068
הוא ממש לא היה ''זה לא נכון'', אלא, לכל היותר, ''זה לא מוצא חן בעיניי''.
אלכסנדרוביץ' מתעלל בסוסים שמדברים עברית 404163
את התגובה שלעיל תשמור לשלב הטיעונים לעונש.
גדי צודק: אני מרשיע אותך בזאת בהתנהגות טיפוסית למתרגל מתחיל.
אלכסנדרוביץ' מתעלל בסוסים 403939
(עקרונית את צודקת, אבל) אנחנו לא יודעים שיוסי הוא כחול. אנחנו כן יודעים שהכנסנו אותו לקבוצה שמכילה k סוסים שכולם באותו הצבע - לכן יוסי הוא באותו הצבע כמו שאר חברי הקבוצה.

למשל, אם בקבוצה יש את יוסי, דני וגילי, הרי שאחרי שהוצאנו את יוסי נשארו דני וגילי ושניהם באותו הצבע. עכשיו נוציא את דני ונחזיר את יוסי - אז על פי הנחת האינדוקציה, יוסי באותו צבע כמו גילי, שהוא באותו הצבע כמו דני. לכן שלושתם באותו צבע.
אלכסנדרוביץ' לבני-תמותה 403844
שוכחים להוכיח את תנאי ההתחלה - שקבוצה של סוס אחד (או אפס סוסים) בהכרח מכילה רק סוסים שחורים.
אלכסנדרוביץ' לבני-תמותה 403854
הטריק אצל גדי הוא אחר, קצת יותר מתוחכם, אבל את תנאי ההתחלה הוא דווקא כן מוכיח (קבוצה של סוס אחד מכילה רק סוסים עם צבע אחיד).
אלכסנדרוביץ' לבני-תמותה 403858
הטריק אצל גדי הוא אותו הטריק, למיטב הבנתי - אין הוכחה של תנאי ההתחלה. הוא פשוט ניסח את תנאי ההתחלה אחרת. אני קיצרתי.
אלכסנדרוביץ' לבני-תמותה 403866
לא, הטריק שלו הוא אחר, יפה יותר. גדי "מוכיח" שכל קבוצה של n סוסים היא בעלת צבע יחיד. לצורך כך יש להוכיח שזה נכון עבור קבוצה של סוס אחד (תנאי התחלה), ושאם זה מתקיים לקבוצה של n סוסים, זה מתקיים גם עבור קבוצה של n+1 סוסים.

את תנאי ההתחלה קל להוכיח, כל קבוצה עם סוס אחד מכילה סוס אחד, ולכן יש לכל חבריה צבע יחיד‏1, הצבע של הסוס.

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

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

וזה מה שאמרתי בהתחלה, רק במשפט אחד - הטריק הוא שלא מוכיחים את מקרה הבסיס.

1 תודה לך על הדאגה, אבל לא קשה לי.
1 403901
ולפני שאיזו טעות שלי תתגלה, אתקן ''תודה לך על הדאגה, אבל לא קשה לי עם החלק הזה של הנושא, קרי, הצבע דווקא.''
אלכסנדרוביץ' לבני-תמותה 403904
ממש לא. מקרה הבסיס הוא לא קבוצה בעלת שני סוסים, מקרה הבסיס הוא קבוצה בעלת סוס אחד, ועבורו גדי הוכיח את המקרה, והוכיח יפה. לאינדוקציה יש שלושה חלקים:
1. הנחת האינדוקציה.
2. הוכחה עבור מקרה יחיד.
3. הוכחה עבוד המקרה "הבא" בהנחה שהמקרה "הקודם" מתרחש.
כששולשת התנאים האלה מתקיימים יש לך הוכחה באינדוקציה. מאחר שאין לנו דרך לתקוף את 1, ומאחר ש-‏3 נראה בלתי תקיף, הדבר הקל הוא תמיד "לחפש" טעויות ב-‏2. זה מה שאתה עשית, וטעית. הטריק הוא ב-‏3, בגלל ש-‏3 לא נכון עבור כל n אלא רק עבור n>1.

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

אני לא מתעקש מתוך רשעות.
אלכסנדרוביץ' לבני-תמותה 403860
במה שונות האינדוקציה של תואר ראשון ואינדוקציה של בגרות? עכשא"ז זה אותו דבר?
אלכסנדרוביץ' לבני-תמותה 403862
החומר של הבגרות מתעסק הרבה, ומתעסק באופן בלעדי, בשיוויונים ובאי-שיוויונים של טורים סופיים.
אלכסנדרוביץ' לבני-תמותה 403944
זה אותו רעיון (יש תכונה כלשהי שקשורה למספר טבעי. נוכיח את התכונה בצורה ישירה עבור מספר טבעי אחד, ונראה שאם היא נכונה עבור k אז היא נכונה גם עבור k+1 ומזה נסיק שהיא נכונה לכל k שגדול מהבסיס). השאלה היא מה מוכיחים בעזרתו. כמו שדורפל אמר, בתיכון מוכיחים בעיקר שוויונים ואי שוויונים, וזה מה זה משעמם.

לדעתי היה עדיף להראות שימושים של אינדוקציה בהרבה מאוד מקומות שונים. אני את התיכון סיימתי כשאני חושב ש"אינדוקציה" היא תת תחום של העיסוק באי שוויונים.

אני מניח שהבעיה היא שקשה לבחון על אינדוקציה באופן כללי.
אלכסנדרוביץ' לבני-תמותה 403970
איזה שוויונים/אי שוויונים מוכיחים באינדוקציה? (לי האינדוקציה זכורה בכלל רק מהאוניברסיטה. לא זכור לי שלמדתי אותה בתיכון).
דוגמא 403971
דוגמא 403974
וואו... תודה. עכשיו ברור מדוע הדחקתי את זה.
אלכסנדרוביץ' לבני-תמותה 403843
המספרים המרוכבים לא עומדים בסתירה להמצאות הקודמות (הממשיים וכו'). הבעיה היא לא במספרים המרוכבים, הבעיה היא שלך - את לא מבינה אותם (ולא מודעת לכך).

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

חזרה לעמוד הראשי

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים