עצים

[doronimous]

עצים

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

 

[בסג]

אם הבנתי נכון אז התשובה היא >>>>

 

[doronimous]

לא נכון

יש עץ בקו המחבר בין זוג עצים אחד לפחות

 

[Alkhimey]

חידת המשך

הוכח או הפרך: ניתן לחבר את כל חמשת הקודקודים אחד עם השני (כל קודקוד מחובר לארבעת האחרים) כך ששום קו חיבור לא יחתוך קו חיבור אחר.

 

[doronimous]

זה לא המשך זו בדיוק החידה

 

[Alkhimey]

אחרי ההערה שרשמת למטה, זה באמת נראת

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

 

[doronimous]

הערה לחידה:

לגבי מה שכתוב בסוף בסוגריים צריך להיות: צלעות המחומש ואלכסוניו לא עוברים על נקודת חיבור

 

[טלמון סילבר]

גם הניסוח המקורי היה ברור.

 

[טלמון סילבר]

../images/Emo62.gif פתרון החידה המקורית -

לא, אי אפשר (את "חידת ההמשך" לא הבנתי). תהי הרשת מעין מערכת צירים. שיעורי העצים:

(x[1], y[1]) (x[2], y[2]) (x[3], y[3]) (x[4], y[4]) (x[5], y[5]) :גם אפשר להניח לשם הפשטות ש x[1] = y[1] = 0​

כלומר, לקבוע את תחילת הצירים על אחד העצים. על מנת שנמלא את המשימה, עבור כל n≠m

:המספרים x[n] - x[m] y[n] - y[m] חייבים להיות זרים, כלומר, שלא יהיו להם מחלקים משותפים, אחרת​

הקטע המחבר את עצים מספר n ו-m יעבור דרך נקודה/ות נוספת/ות של הרשת. ובפרט, עבור כל n≠m אסור ששני ההפרשים הללו יהיו זוגיים בו זמנית. אך זה בלתי אפשרי. נראה, מהן האפשרויות עבור ארבעת העצים מס.2,3,4,5. אם לפחות לשלושה איקסים שלהם יש אותה זוגיות, אז שלושת העצים הללו כבר מקלקלים: בין שלושת ה-y-ים שלהם יש לפחות שניים בעלי אותה זוגיוּת, וכך אנו מקבלים שני עצים, שהן הפרש האיקסים שלהם והן הפרש ה-y-ים זוגי. נשארה האפשרות, שבדיוק שני איקסים זוגיים, ובדיוק שניים אי-זוגיים. למשל:

x[2] - זוגי x[3] - זוגי x[4] - אי-זוגי x[5] - אי-זוגי​

עכשיו, לשני העצים שהאיקסים שלהם זוגיים, חייבים להיות y-ים בעלי זוגיוּת שונה, אחרת נקבל שוב שני עצים, ששני ההפרשים שלהם זוגיים. אם כך, יש לפחות עץ אחד ששני שיעוריו זוגיים. עץ זה ביחד עם העץ מס. 1, אשר עד עכשיו עמד בצד, נותנים שני הפרשים זוגיים, מה שהורס את המשימה סופית.

 

[Alkhimey]

הסבר לחידת ההמשך:

יש 5 נקודות על המישור במקומות כולשהם, האם ניתן לחבר כל נקודה עם כל נקודה אחרת בקו (שהוא לא בהכרח ישר, ז"א גם קו עקום הוא בסדר) כך שהקוים לא יחצו זה את זה? אם כן הראה דרך, אם לא הבא הוכחה. במילים אחרות הראה בשום ש בשום דרך שבעולם לא ניתן לחבר את חמשת הנקודות, או לחילופין הראה ציור שממחיש שמראה חיבור כזה. למשל עבור 2 נקודות - אפשר, קו אחד שמחבר בין שתי הנקודות, עבור 3 נקודות - אפשר, כל נקודה מחוברת בקו עם כל נקודה אחרת (כמו משולש). **** דוגמא עבור 2 נקודות: *-------------------------* דוגמא עבור 3 נקודות: *-------------* / \ / \ / \ / \ * אם זה לא תבין, אני נכנע. מה לעשות, אני מספר גרוע.

 

[טלמון סילבר]

מעניין../images/Emo45.gif ואינני רואה דמיון ביניהן

 

[inbal76]

אין השבוע "שטו? גדיה? קגדה?" ../images/Emo10.gif

 

[טלמון סילבר]

מה זה "אין"?!

גמר סדרת הסתו! צריך להתחיל עוד כ-40 דקות. ארשום מה שאספיק, ומחר מהמשרד אתרגם ואכתוב בפורום - כמה שתאפשר לי העבודה במשרד, את השאר אסיים בערב.

 

[inbal76]

../images/Emo45.gif

 

[חול טבעוני]

גמר...? ../images/Emo10.gif

זה אומר ששבוע הבא כבר אין...? מתי יהיה שוב?

 

[טלמון סילבר]

בדצמבר סדרת החורף

וגמר השנה, ובמרץ או אפריל - סדרת האביב 2007.

 

[טלמון סילבר]

../images/Emo62.gif פתרון החידה השנייה -

גם-כן אי-אפשר. "משולש", כלומר, עקומה המתחילה הנקודה A, עוברת דרך נקודה אחרת B, ממשיכה דרך נקודה שלישית C וחוזרת לנקודה A, וכל זאת מבלי לחתוך את עצמה, מחלק את שאר נקודות המישור לשני חלקים מבודדים: ה"בפנים" וה"בחוץ" של המשולש. למעשה, בחידה המדוברת, אין הבדל בין שני תחומים אלה. למרחקים אין משמעות, ולא למונח "אינסוף" בתור מרחק. אם הנקודות הנוספות D ו-E נמצאות בתחומים שונים, אחת "בפנים" ה"משולש" ABC והאחרת "מחוצה" לו, אזי כבר אי-אפשר לחבר ביניהן מבלי לחתוך את העקומה ABC. מה שעדין נשאר לנו לנסות, זה למקם את שתיהן גם יחד באחד התחומים הללו. נניח, כדי שההמחשה תהיה ברורה יותר, שתיהן, D ו-E, נמצאות "בפנים" ה"משולש" ABC. עדין אפשר לחבר את הנקודה D עם כל אחת מהנקודות A,B,C מבלי שה"צלעות" יחתכו זו את זו. חיבורים אלה מחלקים את ה"בפנים" של ה"משולש" ABC לשלושה תחומים, הסגורים בפנים המשולשים הבאים: ABD,ACD,BCD. אם הנקודה D נמצאת "מחוץ" למשולש ABC, זה לא משנה! כשנחבר אותה עם כל אחת משלוש נקודות אלה, ה"חוץ" של ה"משולש" ABC יחולק גם הוא לשלושה תחומים זרים. עכשיו, מכיוון שהנקודה E נמצאת מאותו צד של ה"משולש" ABC כמו הנקודה D, היא (הנקודה E) בהתאם לתנאי השאלה חייבת להיות בפנים אחד משלושת התחומים ABD,ACD,BCD. ואז אי אפשר לחבר אותה עם הקודקוד השלישי של ABC, זה שאינו תוחם את התחומצ'יק שלה: אם הנקודה E נמצאת בתחום ABD, היא מנותקת מ-C אם הנקודה E נמצאת בתחום ACD, היא מנותקת מ-B אם הנקודה E נמצאת בתחום BCD, היא מנותקת מ-A

 

[Alkhimey]

../images/Emo45.gif

מצטער שאני מגיב מאוחר, לא היה לי זמן להכנס לפורום.

 

[טלמון סילבר]

../images/Emo62.gif הרבה יותר מהיר (למקורית)

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

 

[doronimous]

מעולה ../images/Emo45.gif