חידה גאומטרית (קשה) -על ישר אחד-
- פותח הנושא Tukon
- פורסם בתאריך
E s t e b a n
New member
אותה הבעיה
יכול להיות שיש קבוצה של N נקודות שמקיימות את התנאי, ואם תוריד נקודה כלשהי, תקבל N-1 נקודות -שלא- מקיימות את התנאי. זאת אומרת שאתה לא מתחיל מ-N-1 נקודות שמקיימות את התנאי.. אתה מתחיל מ-N-1 נקודות כלליות, מוסיף נקודה -ואז- התנאי מתקיים.
יכול להיות שיש קבוצה של N נקודות שמקיימות את התנאי, ואם תוריד נקודה כלשהי, תקבל N-1 נקודות -שלא- מקיימות את התנאי. זאת אומרת שאתה לא מתחיל מ-N-1 נקודות שמקיימות את התנאי.. אתה מתחיל מ-N-1 נקודות כלליות, מוסיף נקודה -ואז- התנאי מתקיים.
ומרפרוף בשרשור אני רואה שגם
חשבת כך בעבר, ושינית דעתך משום מה. אציין שכדי להפיל את ההוכחה הזאת, אתה צריך להראות טעות אינהרנטית בה, ולשם כך מספיקה גם דוגמא יחידה. אני בטוח שאם תחשוב על זה קצת תשים לב שאין דוגמא כזאת (בדיוק בגלל מה ששנינו אמרנו: אם יש 3 נק' המקיימות, הרביעית תקיים וכו' עד אינסוף).
חשבת כך בעבר, ושינית דעתך משום מה. אציין שכדי להפיל את ההוכחה הזאת, אתה צריך להראות טעות אינהרנטית בה, ולשם כך מספיקה גם דוגמא יחידה. אני בטוח שאם תחשוב על זה קצת תשים לב שאין דוגמא כזאת (בדיוק בגלל מה ששנינו אמרנו: אם יש 3 נק' המקיימות, הרביעית תקיים וכו' עד אינסוף).
E s t e b a n
New member
מבלבל...
יכולה להיות קבוצה בגודל N שמקיימת את התנאי, שנוצרה מקבוצה בגודל N-1 שלא מקיימת את התנאי, פלוס נקודה חדשה... אם קבוצה בגודל N מקיימת את התנאי, יש שני מקרים: 1. אם נפחית נקודה, תמיד נקבל קבוצה בגודל N-1 שמקיימת את התנאי 2. אם נפחית נקודה, יתכן שנקבל קבוצה בגודל N-1 שלא מקיימת את התנאי. בקיצור, אנחנו הוכחנו שאם יש לנו קבוצה N מהטיפוס הראשון, אז זה נכון כי אפשר להשתמש בהנחת האינדוקציה. אבל לא הוכחנו -לכל- קבוצה בגודל N שמקיימת את התנאי, כי לא התייחסנו לטיפוס השני, שבו אי אפשר להשתמש בהנחת האינדוקציה (שתקפה רק אם התנאי תקף). מה שנשאר זה להוכיח שהטיפוס השני לא קיים...
יכולה להיות קבוצה בגודל N שמקיימת את התנאי, שנוצרה מקבוצה בגודל N-1 שלא מקיימת את התנאי, פלוס נקודה חדשה... אם קבוצה בגודל N מקיימת את התנאי, יש שני מקרים: 1. אם נפחית נקודה, תמיד נקבל קבוצה בגודל N-1 שמקיימת את התנאי 2. אם נפחית נקודה, יתכן שנקבל קבוצה בגודל N-1 שלא מקיימת את התנאי. בקיצור, אנחנו הוכחנו שאם יש לנו קבוצה N מהטיפוס הראשון, אז זה נכון כי אפשר להשתמש בהנחת האינדוקציה. אבל לא הוכחנו -לכל- קבוצה בגודל N שמקיימת את התנאי, כי לא התייחסנו לטיפוס השני, שבו אי אפשר להשתמש בהנחת האינדוקציה (שתקפה רק אם התנאי תקף). מה שנשאר זה להוכיח שהטיפוס השני לא קיים...
רגע רגע...
יכולה להיות קבוצה בגודל N שמקיימת את התנאי, שנוצרה מקבוצה בגודל N-1 שלא מקיימת את התנאי, פלוס נקודה חדשה... מה שאתה בעצם אומר זה שההנחה שלי שאם יש קב' של N-1 נק' המקיימת את התנאי אזי כל הנק' על אותו ישר אינה נכונה. אבל זו בדיוק הנחת האינדוקציה: לוקחים את המקרה של N-1 ומניחים שהוא כן מקיים את הנדרש.
יכולה להיות קבוצה בגודל N שמקיימת את התנאי, שנוצרה מקבוצה בגודל N-1 שלא מקיימת את התנאי, פלוס נקודה חדשה... מה שאתה בעצם אומר זה שההנחה שלי שאם יש קב' של N-1 נק' המקיימת את התנאי אזי כל הנק' על אותו ישר אינה נכונה. אבל זו בדיוק הנחת האינדוקציה: לוקחים את המקרה של N-1 ומניחים שהוא כן מקיים את הנדרש.
E s t e b a n
New member
זה לא מה שאני אומר...
עוד ניסוח: אתה אומר - יש לנו N-1 נקודות שמקיימות את התנאי. נוסיף נקודה כך שנקבל קבוצה בגודל N שמקיימת את התנאי. לקבוצות מהגודל N שנבנות ככה, ההנחה נכונה. אבל יכולה להיות קבוצה בגודל N שנבנית אחרת... לוקחים N-1 נקודות סתמיות -שלא- מקיימות את התנאי, כלומר לא -כל- ישר שעובר בין שתי נקודות, עובר דרך נקודה נוספת. ואז מוסיפים נקודה חדשה, ומקבלים קבוצה בגודל N שבה, הפלא ופלא, -כן- כל ישר שעובר בין שתי נקודות עובר דרך נקודה נוספת. אז יש טיפוס שלם של קבוצות בגודל N, שכן מקיימות את התנאי ==> כלומר צריך להוכיח שהן על אותו ישר; אבל כל תת-קבוצה שלהן לא בהכרח מקיימת את התנאי, ולכן גם לא בהכרח שהן על אותו ישר... הנחת האינדוקציה אומרת שכל קבוצה בגודל N-1, שבה כל ישר שעובר בין 2 נקודות עובר דרך נקודה שלישית --> כל N-1 הנקודות הן על אותו ישר. הנחת האינדוקציה לא אומרת דבר על קבוצה בגודל N-1 שבה לא כל ישר שעובר בין 2 נקודות עובר דרך נקודה שלישית.
עוד ניסוח: אתה אומר - יש לנו N-1 נקודות שמקיימות את התנאי. נוסיף נקודה כך שנקבל קבוצה בגודל N שמקיימת את התנאי. לקבוצות מהגודל N שנבנות ככה, ההנחה נכונה. אבל יכולה להיות קבוצה בגודל N שנבנית אחרת... לוקחים N-1 נקודות סתמיות -שלא- מקיימות את התנאי, כלומר לא -כל- ישר שעובר בין שתי נקודות, עובר דרך נקודה נוספת. ואז מוסיפים נקודה חדשה, ומקבלים קבוצה בגודל N שבה, הפלא ופלא, -כן- כל ישר שעובר בין שתי נקודות עובר דרך נקודה נוספת. אז יש טיפוס שלם של קבוצות בגודל N, שכן מקיימות את התנאי ==> כלומר צריך להוכיח שהן על אותו ישר; אבל כל תת-קבוצה שלהן לא בהכרח מקיימת את התנאי, ולכן גם לא בהכרח שהן על אותו ישר... הנחת האינדוקציה אומרת שכל קבוצה בגודל N-1, שבה כל ישר שעובר בין 2 נקודות עובר דרך נקודה שלישית --> כל N-1 הנקודות הן על אותו ישר. הנחת האינדוקציה לא אומרת דבר על קבוצה בגודל N-1 שבה לא כל ישר שעובר בין 2 נקודות עובר דרך נקודה שלישית.
E s t e b a n
New member
הנחת האינדוקציה כוללת תנאי...
וכדי להשתמש בה, חייבים להוכיח קודם שבאמת התנאי מתקיים, אחרת ההנחה לא תקפה.
וכדי להשתמש בה, חייבים להוכיח קודם שבאמת התנאי מתקיים, אחרת ההנחה לא תקפה.
E s t e b a n
New member
שכחת כמה ישרים...
למשל הישר שעובר בין הנק' השמאלית למעלה לבין הנק' התחתונה. בכל מקרה בהגדרת השאלה חסר התנאי הבסיסי שבין כל שתי נקודות יכול לעבור רק ישר אחד. רמז: N סופי או ב"מ --> אינדוקציה.
למשל הישר שעובר בין הנק' השמאלית למעלה לבין הנק' התחתונה. בכל מקרה בהגדרת השאלה חסר התנאי הבסיסי שבין כל שתי נקודות יכול לעבור רק ישר אחד. רמז: N סופי או ב"מ --> אינדוקציה.
E s t e b a n
New member
לא פותרת?
בסיס אינדוקציה: N=3 (כאשר N קטן מ-3 בהכרח אין סתירה כי אין 3 נקודות). יש ישר (1,2), ישר (2,3), ישר (1,3). כל אחד מהם חייב לעבור דרך הנקודה השלישית, כלומר יש ישר אחד שעובר דרך (1,2,3), כלומר (1,2,3) על אותו ישר. צעד אינדוקציה: נניח שזה נכון עבור N-1, נראה שנכון עבור N. נסתכל על קבוצת הנקודות (1 עד N-1). יש בה N-1 נקודות ולכן לפי ההנחה כולן על אותו ישר. נסתכל על קבוצת הנקודות (2 עד N). יש בה N-1 נקודות ולכן לפי ההנחה כולן על אותו ישר. נסתכל על הנקודות 2 ו-3. הן שייכות גם לישר מהקבוצה הראשונה וגם לישר מהקבוצה השניה. מכיוון שבין כל שתי נקודות עובר ישר אחד בלבד, הישר של הקבוצה הראשונה הוא הישר של הקבוצה השניה. מכאן ש-N נמצא על הישר שעליו נמצאות (1 עד N-1). סתם ברפרוף, פספסתי משהו?
בסיס אינדוקציה: N=3 (כאשר N קטן מ-3 בהכרח אין סתירה כי אין 3 נקודות). יש ישר (1,2), ישר (2,3), ישר (1,3). כל אחד מהם חייב לעבור דרך הנקודה השלישית, כלומר יש ישר אחד שעובר דרך (1,2,3), כלומר (1,2,3) על אותו ישר. צעד אינדוקציה: נניח שזה נכון עבור N-1, נראה שנכון עבור N. נסתכל על קבוצת הנקודות (1 עד N-1). יש בה N-1 נקודות ולכן לפי ההנחה כולן על אותו ישר. נסתכל על קבוצת הנקודות (2 עד N). יש בה N-1 נקודות ולכן לפי ההנחה כולן על אותו ישר. נסתכל על הנקודות 2 ו-3. הן שייכות גם לישר מהקבוצה הראשונה וגם לישר מהקבוצה השניה. מכיוון שבין כל שתי נקודות עובר ישר אחד בלבד, הישר של הקבוצה הראשונה הוא הישר של הקבוצה השניה. מכאן ש-N נמצא על הישר שעליו נמצאות (1 עד N-1). סתם ברפרוף, פספסתי משהו?
לא התעמקתי בנסיונות של אחרים
(אחרת זה לא כיף לפתור חידה
), אבל נראה לי שאינדוקציה פשוטה בהחלט פותרת את זה. בסיס: ברור שנכון לגבי N=3 (כי הנק' A ו-B יוצרות ישר, ברור ש-C הנק' השלישית תהיה עליו לפי הנתון). הנחה: נניח ש- N-1 נקודות המקיימות את התנאי חייבות להיות על אותו ישר AB. צעד: הרעיון: נוסיף נק' נוספת P, נראה שהיא חייבת להיות על אותו ישר כמו שאר הנק', ומכאן ש-N נק' על אותו ישר וסיימנו. נוסיף נק' נוספת P המקיימת את התנאי הנדרש, ונניח בשלילה שהיא אינה על הישר (ראה שרטוט). אבל הנק' יוצרת עם הנק' A (למשל) את הישר AP. הנחת האינדוקציה היא שכל הנק' על הישר AB, והישר AP חותך את AB רק בנק' A, ולכן הנק' היחידות על הישר AP הן A ו-P, וזאת בניגוד להנחה שבשלילה. מכאן ש-P על הישר AB, כלומר, כל N הנק' על הישר AB. באינדוקציה, QED.
(אחרת זה לא כיף לפתור חידה
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.