בתשובה לסמיילי, 21/08/06 12:56
אלכסנדרוביץ' לבני-תמותה 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 לא עובד, ולכן הוא לא טוב. אבל רציתי לקצר, אז השתמשתי בו. נראה לי די ברור שגדי ואני התכוונו לאותו הדבר.

אני לא מתעקש מתוך רשעות.

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

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