משולש של נקודות

[עריסטו]

משולש של נקודות

יש 55 נקודות מסודרות בצורת משולש: . .. ... .... ..... ...... ....... ........ ......... .......... רוצים למחוק את כל הנקודות על ידי שרטוט קו שבור אחד. צריך להוכיח שמספר הקטעים מהם מורכב הקו השבור חייב להיות לפחות עשרה.

 

[Shappiro]

ב-18 קטעים זה ממש קל... ../images/Emo4.gif

 

[Shappiro]

אופס..

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

 

[עריסטו]

גם בעשרה קטעים זה ממש קל.

זאת לא החידה. החידה היא להוכיח שאי אפשר לעשות זאת בעזרת קו שבור שיש בו פחות מעשרה קטעים.

 

[baraba1]

שאלה

האם הפתרון הוא ע"פ עקרון המקסימום?

 

[עריסטו]

מה זה עקרון המקסימום?

 

[baraba1]

שאלה טובה

 

[Elad Hollander]

הצעה לפתרון

הנקודות מסודרות במשולש- 1 בקודקוד, 2 בקומה הבאה וכן הלאה. עבור כל קומה, החל מהקומה הראשונה מתקיים- יש שתי אופציות לקו שמגיע לנקודה (היחידה) בקומה זו. נדגים: בקומה הראשונה שתי אופציות למתיחת קו- אנכי, ישירות למטה, או אלכסוני, לאורך הצלע השמאלית. נבחר אחד מהם, ונתבונן בקומה הבאה- בהכרח מחקנו את אחת הנקודות בו, אך לא את האחרת. למעשה, אפשר להסתכל על כל שאר הקומות ולראות שממשולש של 10 קומות ו-55 נקודות, צמצמנו את הבעיה למשולש של 9 קומות ו-45 נקודות, ועכשיו נשאר להוכיח באופן זהה שיידרשו לנו עוד לפחות 9 קווים...

 

[עריסטו]

לא נכון

בקומה הראשונה יש אינסוף אופציות למתיחת קו, לא רק שתיים.

 

[Elad Hollander]

תיקון + שאלה

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

 

[עריסטו]

לא, לא הוכחת.

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

 

[snogal]

באופן גס

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

 

[עריסטו]

לא מובן

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

 

[eviljelly]

אולי ?

כדי להשתמש בכמה שפחות קוים ננסה שהקו יעבור דרך כמה שיותר נקודות : מכאן שהקו הראשון יעבור דרך 10 נקודות (דרך אחת "הצלעות" של המשלוש) וברגע שזה קרה נוצר משולש חדש ("שווה צלעות") שכל צלע שלו היא 9 נקודות וכו'

 

[עריסטו]

ראה מה שעניתי לאלעד

 

[eviljelly]

לא שמתי לב ..