חידה יפה מספר

[אלעדדדדד]

חידה יפה מספר

יחיאל צייר על דף 1000 נקודות אדומות ו 1000 כחולות. אין 3 נקודות (כלשהם) הנמצאות על ישר אחד יחיאל רוצה למתוח 1000 קווים כך שכל קו יוצא מנק' אדומה ומגיע לנק' כחולה, אבל אף קו לא חותך קו אחר. האם יצליח? תוכיחו

 

[עריסטו]

הערה חשובה: הקווים ישרים

 

[Tesseract]

מטרת ההערה..?

לומר שהקווים אינם מפותלים? או שמדובר בישרים ולא בקטעים? (או גם וגם

)

 

[עריסטו]

לומר שהם אינם מפותלים, אבל

בעצם אתה צודק - צריך להדגיש שמחברים את הנקודות בקטעים, לא בישרים.

 

[עריסטו]

../images/Emo207.gif חידת המשך

מה קורה בגרסה האינסופית? יחיאל צייר על דף אלף-אפס נקודות אדומות ו אלף-אפס כחולות. אין 3 נקודות (כלשהם) הנמצאות על ישר אחד יחיאל רוצה למתוח אלף-אפס קווים כך שכל קו יוצא מנק' אדומה ומגיע לנק' כחולה, אבל אף קו לא חותך קו אחר. האם יצליח? תוכיחו (הערה חשובה מאוד: למי שתהה איך הצליח יחאל לצייר כל כך הרבה נקודות- את הנקודה הראשונה הוא צייר בשנייה אחת, את הנקודה השנייה הוא צייר בחצי שנייה, את השלישית הוא צייר ברבע שנייה... אחרי שתי שניות הוא צייר אלף-אפס נקודות

)

 

[clocker]

מותר להשתמש בתותחים כבדים ?

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

 

[slallum]

אתה איכשהו קשור לקורס אח"מ שחקים?

יש לנו את אותה חידה. רק שאצלנו שכחו לציין שאין 3 נקודות שנמצאות על אותו ישר

ואני כמובן ישר חשבתי על אפשרות כזאת ולכן אמרתי שהפרכתי את ההשערה, אבל כמובן שזה היה קל מדי. אז זה הפרט החסר, הא? סבבה, עכשיו ננסה

 

[Tesseract]

שאלה

נדרש ידע בתורת הגרפים כדי להוכיח (בצורה נורמלית)?

 

[עריסטו]

מקווה שמותר לי לענות במקומו

לא.

 

[clocker]

יש לי רעיון לפתרון

זה בעצם באינדוקציה, בסיס האינדוקציה: נקודה אדומה יחידה ונקודה כחולה יחידה ברור שהקו היחיד שמחבר ביניהן לא חותך אף קו אחר. צעד האינדוקציה: נניח שזה נכון לכל m קטן מn ונוכיח עבור n נמצא את הנקודה הכחולה בעלת קורדינטת Y מקסימלית, נסמן בb0, b00 נמצא את הנקודה האדומה בעלת קורדינטת Y מקסימלית, נסמן בr0, r00 הערות: 1. b00,r00 לא בהכרח קיימות, אם כן קורדינטת הX של p0 קטנה משל p00 2. לא יכולות להיות יותר משתי נקודות בעלות קורדינטת Y מקסימלית, כי אין שלוש נקודות על ישר אחד. כעת יש 3 מצבים, 1. אם יש רק נקודה מקסימלית אחת לכל צבע, נחבר אותן בקו ונמשיך הלאה. 2. אם יש 2 נקודות כחולות b0,b00 ונקודה אדומה אחת r0, נחבר את r0 עם הנקודה שיותר קרובה אליה בקורדינטת הX. (המצב עם נקודה כחולה בודדת ושתיים אדומות סימטרי לחלוטין) 3. אם יש 2 נקודות אדומות ו2 כחולות, אז נחבר את r0 עם b0 ואת r00 עם b00. אפשר להוכיח עם גאומטריה שהבנייה שעשיתי עובדת, אבל בכנות - אין לי כוח להתברבר עם זה באמצע הלילה. (בתקווה שלא טעיתי) ולכן על סמך הנחת האינדוקציה, יש גם "זיווג" שכזה על ידי קטעים ישרים גם לשאר הנקודות.

 

[ןן גיל ןן]

לא נראה לי שזה יעבוד

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

 

[ןן גיל ןן]

חצי פיתרון (רדוקציה לחידה אחרת)

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

 

[ןן גיל ןן]

... החצי השני של הפיתרון

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

 

[עריסטו]

../images/Emo58.gif רמז בפנים

תחשבו על סכום אורכיהם של 1000 הקטעים.

 

[Tesseract]

שאלה

פתרת את החידה הזו בעצמך?

 

[עריסטו]

כן

 

[1אברהם]

../images/Emo62.gif

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

 

[mor48]

לא בטוח

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

 

[עריסטו]

הסבר

טענה: סידור בו יש חיתוך אינו מינימלי. זה שקול לטענה: בסידור מינימלי אין חיתוך.

 

[mor48]

אולי הסבר יותר מפורט

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