טורבו החילזון

[ספי12310]

טורבו החילזון

איך עונים על השאלה המצורפת?

 

[עריסטו]

רמז

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

 

[עריסטו]

חידת המשך

הוכיחו שאם טורבו לא "בורחת לאינסוף" אז היא תחזור מתישהו למיקומה ההתחלתי.

 

[אורי769]

הבהרה

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

 

[עריסטו]

כן

 

[אורי769]

נסיון

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

 

[עריסטו]

ההוכחה שלי היא כזו

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

 

[אורי769]

יפה

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

 

[עריסטו]

טורבו וחבריה

נתון פאון. על כל אחת מפאותיו יש חלזון. החלזון מפטרל על היקף הפאה בכיוון השעון. הוכיחו: אם כל חלזון השלים הקפה שלמה, התרחשה התנגשות בין חלזונות.

 

[עריסטו]

טורבו על לוח שחמט

על כל משבצת של לוח שחמט בגודל 101x101 מצוייר חץ שמצביע באחד משמונת כיווני המצפן (צפון, צפון מזרח, מזרח, דרום מזרח וכו'). לכל שתי משבצות בעלות צלע משותפת, כיווני החיצים שבהן נבדלים ב-45 מעלות לכל היותר. טורבו מתחילה מהמשבצת האמצעית ונעה ממשבצת למשבצת לפי כיווני החיצים. הוכיחו: טורבו תיפול מהלוח.

 

[הפרבולה]

ניסיון

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

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

 

[אורי769]

יש בעיה

טיעון הקשירות הוא בעייתי כאן, כי המסלולים הולכים גם באלכסון. נניח המסלול המינימלי P עובר ממשבצת שחורה A1 למשבצת שחורה B2. תיאורטית מסלול פנימי יכול לעבור ממשבצת לבנה A2 למשבצת לבנה B1.

 

[הפרבולה]

אהה...אני חושב שאפשר לפסול את האפשרות הזאת

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

 

[אורי769]

צודק!

 

[הפרבולה]

יש לי פה איזה בעיה

לא הוכחתי למה חייב להיות מסלול מעגלי בתוך המסלול המעגלי הגדול יותר....

 

[הפרבולה]

תיקון

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

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

המסלול החדש שקבלנו בין אם הוא מסתיים חזרה ב A או ב B תוחם שטח קטן יותר שכל מסלול פנימי שלו לא יכול לצאת ממנו .

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

 

[עריסטו]

פתרון יפה, אפשר גם אחרת קצת

קודם כל אין מסלול בצורת הספרה 8 כי זה סותר את הנתון, לכן כל מסלול סגור הוא מעגל פשוט. נניח שיש מסלול כזה. אם הוא בכיוון השעון נסובב את כל החיצים בלוח 45 מעלות בכיוון השעון. זה שומר על התנאי ביחס לכיווני החיצים שבמשבצות סמוכות. אבל עכשיו אם טורבו מתחילה מנקודה בתוך המעגל היא תישאר בתוך המעגל, כלומר קיבלנו מסלול סגור קטן יותר. וכן הלאה.
הנה עוד פתרון: כמו קודם אין מסלול בצורת 8. נצייר על הלוח מסלול סגור כלשהו (לא בצורת 8) - בלי קשר לכיווני החיצים - ונטייל עליו עד שנשלים סיבוב שלם. נעקוב אחרי כיווני החיצים במסלול. לפעמים החץ מסתובב ימינה, לפעמים שמאלה ולפעמים לא משתנה. הטענה היא שסך כל הסיבובים האלה הוא 0. זה נובע מכך שבריבוע 2x2 או משולש של 3 משבצות זה כך, ואת התחום שבתוך המסלול ניתן להרכיב מריבועים ומשולשים כאלה. אבל אם טורבו תשלים הקפה לפי החיצים סך כל הסיבובים אינו 0.