חידת מסע הפרש
וריאציות > שינוי גודל הלוח > קיום פתרון

הוכח, שיש מסלול סגור אם מתקיימים התנאים הבאים:
mn הוא זוגי (אחרת לא ניתן למצוא מסלול סגור, מאחר שבכל מהלך הפרש משנה את צבע המשבצת עליה הוא נמצא, ומכאן שהוא חייב להתחיל ולסיים במשבצות באותו צבע, ולכן אינו יכול לדלג ביניהן)
גם m וגם n הם לפחות 5, או אחד מהם 3 והשני 10 ומעלה
ההוכחה למשפטים אלה מתבססת על חלוקה ללוחות קטנים יותר.
| סקירת ההוכחה |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
ההוכחה תעשה בשלבים שברובם ניעזר באינדוקציה. את קיומם של מקרי הבסיס נזכיר בלי להראות אותם במפורש.  הערה: במונח "אלכסון של פינה" נתכוון למשבצת הסמוכה הנוגעת בה באלכסון. לדוגמה, אלכסון של הפינה הימנית התחתונה הוא המשבצת השנייה מימין ושנייה מלמטה (ז2 בלוח רגיל).: 
טענה 1: לכל לוח 5xm יש מסלול פתוח המתחיל בפינה השמאלית התחתונה ונגמר באלכסון של הפינה הימנית התחתונה.: 
בסיס האינדוקציה: הצגת מסלול כזה עבור 5x5, 5x6, 5x7, 5x8, 5x9.: 
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את המסלול הזה לאלכסון של הפינה הימנית התחתונה ומשם נמשיך לפינה השמאלית התחתונה של הלוח מימין ונעשה את המסלול על פי הנחת האינדוקציה.: 
טענה 2: לכל לוח 6xm יש מסלול פתוח המתחיל בפינה השמאלית התחתונה ונגמר באלכסון של הפינה השמאלית העליונה.: 
בסיס האינדוקציה: הצגת מסלול כזה עבור 6x5, 6x6, 6x7, 6x8, 6x9.: 
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד לפינה הימנית התחתונה, משם נעבור לפינה השמאלית התחתונה של הלוח מימין ונבצע בו את המסלול על פי הנחת האינדוקציה. המסלול נגמר בפינה השמאלית העליונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.: 
טענה 3: לכל לוח 6xm יש מסלול סגור.: 
הוכחה: ניתן להציג מסלול כזה עבור 6x5, 6x6, 6x7, 6x8, 6x9. אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד לפינה ימנית תחתונה, משם נעבור לפינה שמאלית תחתונה של הלוח מימין ונבצע בו את המסלול שקיומו הוכח בטענה 2. המסלול נגמר בפינה שמאלית עליונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.: 
טענה 4: לכל לוח 8xm יש מסלול סגור.: 
בסיס האינדוקציה: הצגת מסלול כזה עבור 8x5, 8x6, 8x7, 8x8, 8x9.: 
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד לפינה הימנית התחתונה, משם נעבור לפינה השמאלית התחתונה של הלוח מימין ונבצע בו את המסלול על פי הנחת האינדוקציה. המסלול נגמר משבצת מעל הפינה הימנית התחתונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.: 
טענה 5: לכל לוח 8xm יש מסלול פתוח שמתחיל בפינה השמאלית התחתונה ומסתיים באלכסון של הפינה השמאלית העליונה.: 
הוכחה: ניתן להציג מסלול כזה עבור 8x5, 8x6, 8x7, 8x8, 8x9. אם 10≤m, נחתוך משמאל לוח בגודל 5xm, נבצע בו את תחילת המסלול עד למשבצת רביעית מלמטה בשורה ימנית ביותר, משם נעבור למשבצת מעל אלכסון של פינה שמאלית תחתונה ונבצע בו את המסלול שקיומו הוכח בטענה 4. המסלול נגמר בפינה שמאלית תחתונה ממנה ניתן לקפוץ להמשך המסלול של הלוח השמאלי ולסיים אותו.: 
טענה 6: בכל לוח nx5 כאשר n זוגי ו-10≤n, יש מסלול סגור.: 
הוכחה: נחתוך מלמטה לוח בגודל 5x5. על פי למה 1, יש מסלול שמתחיל בפינה השמאלית העליונה ומסתיים באלכסון של הפינה הימנית התחתונה. נבצע אותו, ומשם נקפוץ לפינה הימנית התחתונה של הלוח העליון, ועל פי למה 1 ניתן לבצע מסלול שיגמר באלכסון של הפינה השמאלית התחתונה, ממנה ניתן לחזור לנקודת ההתחלה.: 
טענה 7: לכל לוח nxr כאשר r בין 5 ל-9 ו-n אי זוגי יש מסלול פתוח המתחיל בפינה השמאלית העליונה ומסתיים באלכסון של הפינה הימנית העליונה.: 
הוכחה: עבור r=5,6,8 זה הוכח בטענות 6,5,2 (עם סיבוב הלוח) עבור r=7,9 נבצע טיעון אנלוגי לטיעונים של טענות 1,7 (עם בניית לוחות מתאימים להנחת האינדוקציה).: 


בסיס האינדוקציה: טענה 7.: 
צעד האינדוקציה: אם 10≤m, נחתוך משמאל לוח בגודל nx5, נבצע בו את המסלול הזה לאלכסון של הפינה הימנית העליונה ומשם נמשיך לפינה השמאלית העליונה של הלוח מימין ונעשה את המסלול על פי הנחת האינדוקציה.: 
משפט: לכל לוח nxm כאשר nm זוגי ושניהם לפחות 5 יש מסלול סגור.: 
הוכחה: נניח ללא הגבלת הכלליות ש-n זוגי. אם m=6,8 זה נובע מטענות 3,4. אחרת 10≤n ואז נחתוך מלמעלה לוח 5xm ונבצע בו על פי טענה 1 מסלול שמתחיל בפינה השמאלית התחתונה ומסתיים באלכסון של הפינה הימנית התחתונה. משם נקפוץ לפינה הימנית העליונה של הלוח התחתון. משם נפעיל את טענה 6 (הורדנו מ-n‏ 5 ולכן נשארנו עם מספר אי זוגי) ולהגיע לאלכסון של הפינה השמאלית העליונה, ממנה ניתן לחזור לנקודת ההתחלה.: 
משפט: לכל לוח mxn כששניהם לפחות 5 יש מסלול פתוח.: 
הוכחה: אם mn זוגי אז יש מסלול סגור, ובפרט מסלול פתוח (אם מורידים ממנו צעד 1) אם mn אי זוגי זה נובע מטענה 8.: 
נראה אי קיום של מסלול סגור בשאר הלוחות:
עבור 1xn או 2xn אי אפשר אפילו להגיע מכל משבצת לכל משבצת, ובוודאי שלא לעבור על כל המשבצות.
עבור 4xn נצבע את הלוח בצורה המתוארת משמאל: שורות עליונה ותחתונה בירוק, אמצעית באדום.
עבור 3x6 או 3x8 נסתכל על גרף של הלוח. נשים לב שניתן לקבל מסלול המילטוני על ידי הסרת קשתות עד שנקבל רק את הקשתות שמרכיבות את המסלול הרצוי. אולם, ניתן להוכיח שהסרה כזאת בהכרח תהפוך את הגרף ללא קשיר (כלומר גרף שיש בו נקודות שאינן מחוברות זו לזו כלל, אפילו על ידי מסלול) ולכן לא יכול להיות בו מסלול כמבוקש.
מסלול פתוח קיים לכל לוח mxn, למעט 1xn, ‏2xn, ‏3x3, ‏3x5, ‏3x6 ו-4x4.