חידה גאומטרית (קשה) -על ישר אחד-

[E s t e b a n]

הממ?

מדובר על מספר סופי של נקודות, כלומר מספר הנקודות שייך למספרים הטבעיים, והוא בדיד. כל קבוצה סופית מסויימת של N>3 נקודות סופיות היא בהכרח איחוד של קבוצה סופית מסויימת בעלת N-1 נקודות, עם נקודה נוספת. אין כאן בעיות של השערת הרצף ובעיות רציפות...

 

[Tukon]

לא בהכרח

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

 

[E s t e b a n]

זוהי האינדוקציה

הנחת האינדוקציה היא, שהדבר מתקיים -לכל- אוסף של N-1 נקודות כלשהן ללא הגבלות, ומזה מראים שנובע שזה מתקיים -לכל- אוסף של N נקודות כלשהן ללא הגבלות. חשבתי שזה היה ברור.. אז הראתי שכאשר N=3 זה מתקיים (לכל אוסף בן 3 נקודות שהוא ללא הגבלות), בלי קשר להנחת האינדוקציה. ועכשיו דרך האינדוקציה הראתי שאם זה מתקיים עבור N=3, בהכרח זה מתקיים עבור N=4. ואם זה מתקיים עבור N=4, זה מתקיים עבור N=5... וכן הלאה וכן הלאה. כל עוד N הוא מספר סופי או בן מניה... זוהי אינדוקציה סטנדרטית. מה הבעיה?

 

[E s t e b a n]

אופס...

ברפרוף חוזר הבנתי מה הבעיה, אם -התנאי- בהכרח מתקיים על N, לא בהכרח שהוא מתקיים על N-1. אם כן מתקיים, סיימנו. אם לא, סימן שלפחות זוג אחד של נק' בקבוצה בגודל N-1, עובר בינהם ישר שלא נוגע באף נקודה אחרת. (נכנה אותם a,b). אם מוסיפים את נק' N, ואז כל הישרים עוברים דרך 3 נקודות, זה אומר שבהכרח קיים ישר (a,b,N). ישר a,N חייב לעבור דרך b, ולכן בקבוצה בגודל N-1, כל ישר b,x0 אסור לו לעבור דרך a. (כמובן x0 שונה מ-a). אבל בקבוצה בגודל N, הישר b,x0 עובר דרך נק' אחרת. מקרה 1: אם הנקודה היא N, אז הישר b,x0,N זהה לישר b,a,N - יש להם 2 נקודות משותפות. ואם הישר זהה, סימן שבקבוצה בגודל N-1 קיים הישר a,b,x0 כלומר סתירה שהישר (a,b) לא עובר דרך אף נקודה אחרת שהיא לא N. ומכיוון שיש סתירה - לא יתכן שהתנאי מתקיים עבור N ולא מתקיים עבור N-1. מקרה 2: אם הנקודה היא לא N, סימן שהיא שייכת לקבוצה בגודל N-1. נסמן אותה x1, והיא שונה מ-b, שונה מ-x0, ושונה מ-a. אבל בקבוצה בגודל N, הישר x0,x1 עובר דרך נקודה נוספת. אם הנקודה היא N, סתירה כמו מקרה 1 למעלה. אם לא, אז אותה נקודה הנוספת שנסמן אותה x2, שייכת לקבוצה בגודל N-1, והיא שונה מ-a,b,x0,x1 וכן הלאה, וכך נמשיך ונמצא נקודה xk שחייבת להיות שונה מ-k+2 נקודות, ונראה שזה גורר שקיימת נקודה xk+1 שחייבת להיות שונה מ-k+3 נקודות... ומכיוון ש-N סופי, לא יתכן שתהיה נקודה ששונה מ-N נקודות, וזו סתירה. מקווה שזה ברור למרות שעת הלילה המאוחרת... אני לא מי יודע מה קוהרנטי עכשיו.

 

[Tukon]

לא חייב להיות X2 הנקודה הנוספת

של x0,x1 יכולה להיות B

 

[Tukon]

נתון לך אוסף מסוים של N נקודות

לא כל N נקודות האוסף הזה מקיים את התכונה שצינתי כל ישר המחבר שני נקודות מהקבוצה מתחבר ללפחות נקודה אחת נוספת מהקבוצה צ"ל שגם מתקיים שהנקודות בהכרח על ישר אחד

 

[shabaz]

*מתמתח ומפהק*

אני חושב שפתרתי את זה מהבחינה הרעיונית, אבל יש כל כך הרבה אופציות לעבור עליהן אפילו מהבחינה הכי קיצונית- הכי קלה <<בדרך שלי, כן? המסורבלת>>, וכל כך הרבה הוכחות, שיקח לי שנתיים לכתוב את כולן. אין לי כח לחפש טריק:] כך או כך, הנה אחת האופציות שהגעתי אליהן- בתור צורה גיאומטרית שבכדי להביא את ההנחה שכל ישר בין 2 נקודות עובר לפחות על עוד נקודה אחת נצטרך אינסוף נקודות, דבר שאינו מקובל על פי ההנחה שN סופי. הנקודות שנוצרות על ישרים CO ו-CD ע"י הנקודות A ו-B: כל נקודה שנוצרת על ישר שעובר ב-A צריך להיות לפי ההנחה ההתחלתית, ולכן על הישר שנוצר בינו לבין B צריכה להיות נקודה נוספת. כדי לא לסבך את זה יותר מדי, שמתי את כל הנקודות על ישר שכבר קיים על 3 נקודות <<שאחרת זה בכלל היה פשוט, שכן יכולתי לבחור לפחות אחד מבין הנקודות שעל הישר כדי "להצטרך" נקודה נוספת>>. נוצר בעצם איזה שהוא לופ, שרק באינסוף הישרים CB וCA מתלכדים. מבחינת הנקודות על ישר CO.

 

[shabaz]

ההוכחה:

הערה: ההוכחה חלה לגבי הצורה שסרקתי. תיאורטית היא נכונה עבור כל הצורות האפשריות, אבל אין לי חשק לבדוק את כולן:] ================================================================ נוכיח שאם ורק אם כאשר לכל N סופי של נקודות, בין כל 2 נקודות עובר ישר שעובר דרך נקודה אחת נוספת לפחות, כל הנקודות נמצאות על ישר אחד בלבד. כיוון ראשון: נניח שכל הנקודות הן על ישר אחד. מכיוון שכך, אין 2 נקודות שהישר שלהן אינו עובר דרך נקודה אחת נוספת לפחות, וממילא ההנחה מתקיימת. כיוון שני: נוכיח בשלילה. נניח שישנן 2 נקודות כל שהן. נניח שישנה עוד נקודה שאינה על הישר שנוצר מ-2 הנקודות הראשוניות. מכיוון שהוא אינו על אותו ישר, הוא גורר יצירת עוד 2 נקודות. מכיוון שהנקודה השלישית אינה על הישר הנוצר מ-2 הנקודות הראשונות, הרי שכל אחד מהישרים שנוצרים בין 2 הנקודות לנקודה השלישית אינם מתלכדים עם הישר שיוצרים 2 הנקודות הראשוניות. בהנחה ש-2 הנקודות הראשונות אינן מתלכדות, הרי שנוצרים לנו עוד 2 ישרים, שכל אחד מהם צריך לעבור דרך עוד נקודה אחת לפחות. נקרא לנקודות החדשות A ו-B. A, שנמצאת על הישר שנוצר בין הנקודה הראשונה לשלישית, אינה נמצאת על שום נקודה שנוצרה ע"י הנקודה השניה עם נקודה קיימת כל שהיא, שכן: 1. A אינה נמצאת על הישר שנוצר בין 2 הנקודות הראשונות, שכן הישר הנוצר בין הנקודה הראשונה ו-A הוא בעל שיפוע שונה משל הישר הנ"ל, ונקודת החיתוך, שהיא יחידה, כבר ידועה- הנקודה הראשונה. 2. A אינה נמצאת על הישר שנוצר בין הנקודה השניה לשלישית, זאת מכיוון שלישר הנ"ל שיפוע שונה מהישר שנוצר בין הנקודה הראשונה והשלישית, בהנחה שהנקודות לא מתלכדות <<הנודה השלישית היא נקודת החיתוך>>. בצורה אנלוגית, ניתן להוכיח לפי שיקולים דומים, אותו דבר לגבי B והנקודה הראשונה. מכיוון שכך, לפי ההנחה שלנו, צריכה להווצר לפחות עוד נקודה אחת על מנת שההנחה שלנו תתקיים. כדי להקל על העניין, נניח ש-2 הנקודות מתלכדות לנקודה אחת ונמצאת על ישר שכבר קיים. נתייחס עתה ל-2 הנקודות הראשונות- מכיוון שגם עליהן צריכה לחול ההנחה, הרי שצריכה להיות נקודה נוספת על הישר שנוצר בין שתיהן. נחבר את הנקודה השלישית עם הנקודה הנ"ל, כמו גם את הנקודה שעל הישר שעובר דרך הנקודה הראשונה והשלישית. נחבר את הנקודה השניה עם הנקודה שעל הישר שנוצר בין הנקודה הראשונה והשלישית. ===== אם תסתכלו על הצורה שלי, תראו שפה הלופ מתחיל, עם אותן צלעות שציינתי.

 

[Tukon]

לא לגמרי הבנתי

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

 

[pazro]

נסיון לפיתרון

נראה לי שאני בכיוון הנכון יש רק בעיה לנסח נכון את הסוף. נניח מערכת בעלת 4 נקודות, 3 נקודות (1,2,3) על ישר אחד אחת (4) במקום אחר. נוצרים לנו 3 ישרים חדשים (4>1 , 4>2 , 4>3 ). נוסיף נקודה חדשה (5) על הישר המקורי נוכל ליראות כי למערכת שלנו נוסף עוד ישר אחד חדש (4>5) . נעצור לשניה ונסכם את מספר הישרים והנקודות בין נקודה 4 לנקודה N: מספר הנקודות מספר הישרים 3 1 4 4 5 5 6 6 N N נראה כי כאשר נגיע ל N נקודות נקבל N ישרים. נוכל להראות גם כי למערכת של 3 נקודות על ישר ושתי נקודות בחוץ יש טור מספרים דומה ורק המקדם שונה. נקודות ישרים 5 6 אפשר יותר ישרים אבל אנו מחפשים את מספר הישרים המינימלי. 6 8 7 10 8 12 נוכל לראות בקלות כי בנקודה N מספר הישרים המינימלי הוא 2N-4 . נוכל ליראות גם כי בכול מצב התחלתי שבו יש ישר עם 3 נקודות ומספר כלשהוא X של נקודות אחרות במרחב, תוספת של נקודות על הישר המקורי תגדיל את מספר הישרים המינימלי בטור חשבוני בעל מקדם X.ל B נקודות במצב ריאשוני יש N-B * N-1 ) +2 ) קווים. מספר הקווים במערכת שכזו עולה תמיד בהרבה ממספר הנקודות. נבחן את תנאי השאלה ונראה כי כדי לקיים את השאלה מספר הקווים ביחס למספר הנקודות האפשרי בשאלה חייב להיית שווה ל N/3 וזו בהנחה כי לכל שלוש נקודות יש רק קו אחד. כמובן שזה לא אפשרי כי יוצרו לנו עוד N-3*N-1 קווים (קווים חדשים בין כל נקודה ושאר הנקודות שלא על הישר שלה. ולכל ישר נוסיף עוד נקודה כדי לעמוד בתנאי השאלה וע"פ הסעיף הקודם ראינו כי גידול של מספר הנקודות יגדיל את מספר הקווים וחוזר חלילה. כדי לפתר את הבעיה נעלץ לאחד נקודות כדי לימנוע גידול במספר הקווים. טוב אני נרדם על המיקלדת, אני מבטיח להמשיך מחר כלומר היום בבוקר. לילה טוב

 

[pazro]

אחרי הירהורים בשעות יותר שפויות

של היום החלטתי שדרך הפתרון שלי מובילה בסופו של דבר ללולאה לוגית ואין לי דרך לצאת ממנה.

 

[neko]

האינדוקציה נכשלה, רעיון אחר:

נראה לי אינטואיטיבית שלא מסובך להוכיח שתחת התנאים הללו, נק' מחוץ לישר אחד גוררת קיומן של אינסוף נק' - אבל אני מסתבך. ננסה בכ"ז. טענה: בהנתן מס' סופי של נק' תחת התנאי, כולן על אותו ישר. הוכחה: נניח בשלילה שלא כל הנק' על אותו ישר. משום מה נראה לי נוח יותר לעבור דרך למה: למה: בהנתן מס' סופי של נק' המקיימות את התנאים הללו (כל זוג גורר נק' על הישר, לא כולן על אותו ישר), נק' מחוץ לישרים המוגדרים גוררת קיום נק' נוספת מחוץ לישרים. הוכחה: בודאי קיימות 3 נק' על אותו ישר (נובע ישירות מהנתונים). נסמנן P1, P2, P3. נניח בשלילה שקיימת נק' מחוץ לישר P1-P3, נסמנה P4. קיומה של P4 מייצר ישר עם כל אחת מהנק' הקיימות P1, P2, P3, אף אחד מהישרים אינו מתלכד עם ישר קיים (מכיוון ש-P4 אינה על אותו ישר כמו האחרות), ולכן צריכה להיות נק' נוספת על כל אחד מהישרים. ספציפית, חייבת להיות נק' נוספת על הישר P1-P4, נסמנה P5. עכשיו נסתמך על הלמה להגעה לסתירה: ברור שקיימות לפחות 3 נק' שהן על אותו ישר, נסמנו L. אם קיימת נק' A מחוץ לישר, לפי הלמה קיימת נק' נוספת מחוץ לישר, נסמנה B, אולם אז נוצר ישר חדש בין B לבין הנק' שעל הישר L, ולכן קיימת מחוץ לו נק', וחוזר חלילה. מכאן שישנן אינסוף נק' במישור. סתירה, ולכן הנק' כולן על אותו ישר. נראה לי שאני ממש קרוב, אבל זה עדיין לא 100% פורמלי. אולי אינדוקציה תסדר את זה.

 

[pazro]

טוב, עוד ניסיון.

יהיה ישר (S1). על הישר יש מספר נקודות בין שלוש ל B (B יכול להיות שווה ל שלוש). קיימות עוד מספר נקודות סך של N-B . צריך לסדר את הנקודות במרחב כך שיקימו את תנאי ההתחלה (ראה החידה המקורית) . כל נקודה חדשה שאני שם במרחב יכולה להיות גם במרחב וגם על הישר S1 . נניח כי הנחנו את כל הנקודות חוץ מהאחרונה (PN ) נשארת עדיין בידנו. חשוב לציין כי כל הנחת נקודה במרחב גוררת באופן ישיר ציור של ישרים מאותה נקודה לכל שאר הנקודות במרחב. מה צריך להיות המצב במרחב לפני שאנו מניחים את PN ? חייבת להיות נקודה שתקיים את הסעיפים הבאים: 1. נקודה ריקה W. כלומר אין בה נקודה ששיכת לקבוצה P (לא הנחתי שם נקודה בעבר) 2. בנקודה יעברו ישרים שיחברו את כל הנקודות במרחב. כלומר לכל נקודה במרחב יש לפחות נקודה נוספת שחיבור שני הנקודות יתן ישר העבור דרך הנקודה W1 הסבר: 1. כי לא יכולות שתי נקודות שונות להתקיים באותה נקודה במרחב. 2. אסור שהנחת הנקודה האחרונה PN במרחב בW1 יצור ישר חדש כי אין לנו עוד נקודות לשים (יש רק N נקודות). מה יהיה המצב במרחב כששמנו את הנקודה לפני נקודה PN (בנקודה מרחבית W2)? נקודה P(N-1) (הסוגריים לא יוצאים בסדר, הכוונה לנקודה מספר N-1) יכולה ליצר רק ישר אחד חדש, למה? כי יש לנו רק עוד נקודה אחד שנוכל להשלים את מספר הנקודות על הישר ל 3 . נקודה N-1 כדי לא ליצר ישרים חדשים (חוץ מאחד) חייבת לקיים את שני התנאים כמו נקודה PN חוץ מכך שיותר לה ליצר ישר אחד חדש. וכאן עשיתי קפיצה קטנה של אמונה. כי האינדוקציה שאני עובד עליה נעשית יותר ויותר מסובכת. אבל האמונה (וההיגיון) שלי אומרים לי שבסוף אצליך לפתור אותה. כל נקודה חדשה שאני מניח במרחב חיבת לקיים את שני החוקים כמו נקודה PN כלומר להיתמקם בנקודה מרחבית שהיא גם ריקה וגם נקודת החיבור של כל הישרים במרחב חוץ מהישר היחיד שמותר לה ליצר. נדמיין שניה מערכת של 3 P1,P2,P3נקודות. שלושתם יושבות על ישר אחד (כדי לקיים את תנאי ההתחלה) נוסיף נקודה P4 . היכן תתקים נקודה מרחבית W4 כך שתנאי הנקודות שלי יתקיימו? כל נקודה במרחב תיתן לי שלוש ישרים חדשים (ישרים מנקודה P4 ולנקודות P1,P2,P3 וזה לא מקיים את חוקי הנקודות שלי. טווח הנקודות האפשריות במרחב שיקימו את החוקים יושבות על הישר S1 . גם נקודה P5 תהיה מוכרחה להיתמקם הנקודה הישובת על הישר וכל עד נקודה PN. אני בטוח כי הדרך הלוגית שלי יציבה, הבעיה היחידה שעדיין לא הצלחתי להראות (באינדוקציה או בכל דרך אחרת) כי הכללים המתקימים לגבי נקודה N-1 חיביים להתקיים לכל שאר הנקודות. אבל אני די קרוב לכך.

 

[pazro]

הרחבה והפשטה

אותו רעיון אבל ללא אינדוקציות מעצבנות. כללי הנקודה האחרונה נכונים לפי ההודעה הקודמת שלי. חייבת להיות נקודה שתקיים את הסעיפים הבאים: 1. נקודה ריקה W. כלומר אין בה נקודה ששיכת לקבוצה P (לא הנחתי שם נקודה בעבר) 2. בנקודה יעברו ישרים שיחברו את כל הנקודות במרחב. כלומר לכל נקודה במרחב יש לפחות נקודה נוספת שחיבור שני הנקודות יתן ישר העבור דרך הנקודה W1 הסבר: 1. כי לא יכולות שתי נקודות שונות להתקיים באותה נקודה במרחב. 2. אסור שהנחת הנקודה האחרונה PN במרחב בW1 יצור ישר חדש כי אין לנו עוד נקודות לשים (יש רק N נקודות) נסתכל על נקודה N-2 , הנקודה חיבת ליצור ישר עם נקודה אחרת (נקודה A)שיעבור דרך נקודה מרחבית WN (זוהיא הנקודה המרחבית שבה נמקם את נקודה N .) זה חייב להיות כך מאחר ונקודה N ע"פ החוקים שלי חייבת להיות במגע עם כל שאר הנקודות כולל N-2 . נראה כי נקודה N-1 חיבת להיות על הישר שעובר דרך N-2 וN כי אם לא ישב על הישר הנקודה תיצר ישר חדש (אחד לפחות) שיעבור בין N-1 לבין A (אלה אם היא ממקומת על ישר קיים שכבר עובר בין שני הנקודות WN-1 ו A מה שלא ישנה כלום). והשורה הסופית היא שאנו רואים כי שני הנקודות N וN-1 ממוקמות על נקודות מרחביות WN וWN-1 שאפיון שלהם הוא כי כל האלכסונים במרחב עוברים דרכם (הגדרה של אלכסון: בצורה כל שהיא יש V מסויים של קודקודים ואנו מניחים כי לכל צלע העובר לפחות דרך 3 קודקודים, אלכסונים כך שכל אלכסון עובר דרך שני קודקודים בלבד) זהוא זה מוכיח כי יתכן מרחב כזה, כי לכל תצורה מרחבית יש רק נקודה אחת בה נפגשים כל האלכסונים.

 

[pazro]

ואחרי עוד קצת מחשבה הבנתי

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

 

[pazro]

נו קצת תגובות.

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

 

[dimag]

אולי ..

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