בתשובה לסמיילי, 21/08/06 13:31
 |
|
 |
||
|
||||
 |
הטריק אצל גדי הוא אותו הטריק, למיטב הבנתי - אין הוכחה של תנאי ההתחלה. הוא פשוט ניסח את תנאי ההתחלה אחרת. אני קיצרתי. |  |
 |
 |
|
|
|
||
|
||||
|
לא, הטריק שלו הוא אחר, יפה יותר. גדי "מוכיח" שכל קבוצה של n סוסים היא בעלת צבע יחיד. לצורך כך יש להוכיח שזה נכון עבור קבוצה של סוס אחד (תנאי התחלה), ושאם זה מתקיים לקבוצה של n סוסים, זה מתקיים גם עבור קבוצה של n+1 סוסים. את תנאי ההתחלה קל להוכיח, כל קבוצה עם סוס אחד מכילה סוס אחד, ולכן יש לכל חבריה צבע יחיד1, הצבע של הסוס. עכשיו, מה שגדי עושה זה להניח שההנחה שלו נכונה עבור כל קבוצה עם n סוסים, ולהוכיח אותה עבור קבוצה עם n+1 סוסים. לצורך זה, גדי לוקח כל קבוצה של n+1 סוסים, מוציא ממנה סוס אחד, ו... טוב, את השאר קראת. הבעיה היא שזה לא עובד עבור כל n, ז"א כש-n=1 זה לא עובד. זה הטריק. ואם הוא היה מצליח להוכיח שלכל קבוצה של שני סוסים יש צבע אחיד, ההוכחה שלו היתה נכונה. 1 בוא נתעלם מהאפשרות של סוסים עם כתמים וכל זה, זה סתם יוזיל את הטריק. אם זה קשה לך, תחליף את ה"צבע" בגובה. ז"א, גדי מוכיח שכל הסוסים הם בעלי גובה זהה (ואח"כ הוא יבחר איזשהו פוני, ויוכיח שכל הסוסים נמוכים). במקרה כזה קל לדבר על כך שלכל סוס יש גובה יחיד, ולכן תנאי ההתחלה מתקיים. |
|
|
|
|
|
|
||
|
||||
|
הטריק הוא שמקרה הבסיס הוא קבוצה עם שני סוסים, כי הפעולה של גדי משתמשת בשניים - קודם מוציאים אחד, אח"כ מחזירים אותי ואז מוציאים אחד *אחר*. אבל הוא לא הוכיח את מקרה הבסיס - קבוצה של שניים. הוא הוכיח מקרה אחר, והעמיד פנים שזה היה מקרה הבסיס. וזה מה שאמרתי בהתחלה, רק במשפט אחד - הטריק הוא שלא מוכיחים את מקרה הבסיס. 1 תודה לך על הדאגה, אבל לא קשה לי. |
|
|
|
|
|
|
||
|
||||
|
ולפני שאיזו טעות שלי תתגלה, אתקן ''תודה לך על הדאגה, אבל לא קשה לי עם החלק הזה של הנושא, קרי, הצבע דווקא.'' | |
|
|
|
|
|
||
|
||||
|
ממש לא. מקרה הבסיס הוא לא קבוצה בעלת שני סוסים, מקרה הבסיס הוא קבוצה בעלת סוס אחד, ועבורו גדי הוכיח את המקרה, והוכיח יפה. לאינדוקציה יש שלושה חלקים: 1. הנחת האינדוקציה. 2. הוכחה עבור מקרה יחיד. 3. הוכחה עבוד המקרה "הבא" בהנחה שהמקרה "הקודם" מתרחש. כששולשת התנאים האלה מתקיימים יש לך הוכחה באינדוקציה. מאחר שאין לנו דרך לתקוף את 1, ומאחר ש-3 נראה בלתי תקיף, הדבר הקל הוא תמיד "לחפש" טעויות ב-2. זה מה שאתה עשית, וטעית. הטריק הוא ב-3, בגלל ש-3 לא נכון עבור כל n אלא רק עבור n>1. חבל שתמשיך להתעקש. |
|
|
|
|
|
|
||
|
||||
|
הניסוח שלי לא היה אידיאלי, אבל דיברתי על אותו הדבר - שההסקה עובדת רק למקרים שבהם n>=2, כי חייב להשאר לפחות סוס אחד בקבוצה בכל רגע ורגע. דרך יותר קצרה היא להגיד שמקרה הבסיס צריך להיות n=2. הניסוח הזה לא מסביר למה מקרה הבסיס n=1 לא עובד, ולכן הוא לא טוב. אבל רציתי לקצר, אז השתמשתי בו. נראה לי די ברור שגדי ואני התכוונו לאותו הדבר. אני לא מתעקש מתוך רשעות. |
|
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |