חצי לוח שחמט...

[עריסטו]

חצי לוח שחמט...

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

 

[גיל14]

../images/Emo58.gif

לא.

 

[עריסטו]

הוכחה...

 

[גיל14]

כאן

http://www.ktn.freeuk.com/4a.htm

 

[Renatius Cartesius]

אממ...

מה זה הדבר הזה?!

 

[גיל14]

ההוכחה לא קצרה

לפחות הרעיון שלי, והייתי בטוח שאמצע אותו באינטרנט. אז חיפשתי.

 

[עריסטו]

דווקא כן קצרה

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

 

[1אברהם]

עוד הוכחה

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

 

[גיל14]

ח"ח - לא חשבתי על זה כך

 

[עריסטו]

../images/Emo127.gif