חידת החיילים של קונווי

הפוסט הראשון שנכתב בבלוג עסק ברעיון מתמטי מקסים - שמורות, והאופן שבו אפשר להשתמש בהן כדי להראות שדברים מסויימים הם בלתי אפשריים. פוסט נוסף שפרסמתי בעבר עסק במשחק “מחשבת” (Peg Solitaire) ובאופן שבו שמורות אכלו גם אותו בלי מלח, או ליתר דיוק הראו שוריאציה עליו איננה פתירה. כעת אני רוצה לעסוק בוריאציה מחוכמת נוספת של המשחק שהומצאה על ידי המתמטיקאי ג’ון קונווי אי שם בשנות השישים, ובהוכחת אי-קיום מבוססת שמורות שקשורה אליו והיא מחוכמת קצת יותר מההוכחות שהראיתי עד כה.

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

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

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

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

אז איך מוכיחים שדבר כזה הוא פשוט בלתי אפשרי? ראשית, הבה ונפשט קצת את מה שצריך להוכיח - מספיק להראות שבלתי אפשרי להביא חייל למשבצת \( \left(0,5\right) \), כלומר המשבצת שב”אמצע” הלוח האינסופי ובגובה 5 מעל הגבול. זה נובע די בקלות מהסימטריה של הלוח - אם, למשל, אני מצליח להביא חייל למשבצת \( \left(3,5\right) \), כל שעלי לעשות הוא לחזור בדיוק על אותה סדרת צעדים אבל כשכולה מופעלת על חיילים במרחק 3 שמאלה מהחיילים שעליהם פעלתי קודם, כדי להביא חייל למשבצת \( \left(0,5\right) \). במילים אחרות, אם אפשר להביא חייל למשבצת כלשהי במרחק 5 מעל הגבול, אז אפשר להביא חייל גם ל-\( \left(0,5\right) \). אם אראה שלא ניתן להביא חייל לשם, פירוש הדבר שלא ניתן להביא חייל לשום משבצת במרחק 5 מעל הגבול.

התעלול, בבסיסו, הוא אותו תעלול כמו בפוסט הקודם על מחשבת. אנחנו הולכים לתת ערך מספרי כלשהו לכל משבצת בלוח, והשמורה שלנו תהיה סכום הערכים של כל המשבצות שיש עליהן חיילים. מה שנראה הוא שככל שמשחקים במשחק, הערך המספרי הזה לא יכול לגדול (הוא עשוי לקטון, אבל זה לא מחוייב המציאות). כמו כן נראה שבתחילת המשחק הערך הזה הוא 1, ושבכל סיטואציה במשחק שבה יש חייל ב-\( \left(0,5\right) \), הערך הוא לפחות 1 והדרך היחידה שהוא יהיה 1 היא אם החייל שב-\( \left(0,5\right) \) הוא החייל היחיד שנותר בחיים. זה יסיים את ההוכחה בגלל שיש אינסוף חיילים ומשחק תמיד כולל מספר סופי של צעדים (מי שלא השתכנע - נחזור לדיון הזה בסוף).

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

ובכן, על טורים אינסופיים כבר דיברתי בעבר. לא אחזור לדיון העקרוני כאן אלא אצטט רק את מה שחשוב לנו: אם \( q \) הוא מספר חיובי קטן מ-1, אז מתקיימת הנוסחה הבאה (“סכום טור הנדסי אינסופי”): \( \sum_{n=0}^{\infty}q^{n}=\frac{1}{1-q} \). כלומר, הסכום \( q^{0}+q^{1}+q^{2}+\dots \) דווקא כן מסתכם למספר סופי, וזה כל מה שנזדקק לו כאן. לספקנים שביניכם, ההוכחה של אי-פתירות החידה הזו היא דווקא הזדמנות טובה להיווכח בכוחו של מושג הסכום האינסופי; את כל ההוכחה שאני עומד לכתוב מכאן ואילך אפשר לכתוב גם בלי להזדקק למילה “סכום” אלא רק לדבר על גבולות; ההוכחה תהיה טובה באותה מידה, אם כי ברורה פחות, וזה ממחיש שהמושג עצמו מועיל לנו בלי קשר לשם שאנחנו נותנים לו.

אם כן, מראש אנו מחליטים שלכל משבצת ניתן ערך שהוא מהצורה \( q^{n} \), אבל השאלה היא רק מה יהיה \( q \) ומה יהיה ה-\( n \) שמתאים לכל משבצת. נשאיר את בחירת \( q \) להמשך - נגיע עוד מעט למקום שבו הבחירה שלו נובעת מאליה וחלקכם יגלו שמדובר על אחיו של ידיד ותיק - ונדבר לעת עתה על מה שהולך להיות בחזקה.

נניח ש-\( \left(x,y\right) \) היא משבצת כלשהי. מה המרחק שלה ממשבצת היעד שלנו, \( \left(0,5\right) \)? ובכן, זה תלוי בשאלה איך מודדים מרחק, נכון? בהקשר שלנו הגיוני למדוד מרחק במספר צעדים שחייל דמקה צריך לבצע כדי להגיע מ-\( \left(x,y\right) \) אל \( \left(0,5\right) \). בכל צעד שלו, החייל משנה ב-1 את אחת מהקוארדינטות, אך לא יכול לשנות את שתיהן בו זמנית. אז מה המרחק של, נניח, \( \left(2,1\right) \) מ-\( \left(0,5\right) \)? צריך ללכת שני צעדים שמאלה ועוד ארבעה צעדים למעלה - סך הכל \( 2+4=6 \). למה שני צעדים שמאלה? כי זה ערכו של \( 2-0 \). ולמה שני צעדים למעלה? כי זה ערכו של \( 5-0 \). שימו לב איזה חיים קלים עשיתי לעצמי - תמיד חיסרתי את הקטן מהגדול כדי לקבל מספר חיובי. באופן כללי משתמשים בסימון לערך מוחלט כדי להגיד שעושים את זה, ומקבלים שבאופן כללי המרחק מ-\( \left(x,y\right) \) אל \( \left(a,b\right) \) הוא \( \left|x-a\right|+\left|y-b\right| \). השיטה הזו למדידת מרחק נקראת “מטריקת מנהטן” או “מטריקת נהגי המוניות” - אני מנחש שתוכלו לנחש למה.

במקרה שלנו, המרחק מ-\( \left(0,5\right) \) הוא \( |x|+\left|5-y\right| \) (עקרונית לא סביר שנדבר על משבצת שקוארדינטת ה-\( y \) שלה גדולה מ-5 אבל אנחנו לא רוצים לפסול שום דבר על הסף). כדי לפשט את החיים והסימונים אשתמש ב-\( d \) כדי לציין את זה בקיצור כשה-\( x \) וה-\( y \) הספציפיים לא חשובים לנו. במילים אחרות, \( q^{d} \) יהיה הערך המספרי של כל משבצת שמרחקה מהיעד הוא \( d \). כך למשל הערך של היעד עצמו הוא 1, של כל משבצת שרחוקה ממנה בצעד אחד הוא \( q \) (אלו המשבצות \( \left(0,4\right),\left(0,6\right),\left(1,5\right),\left(-1,5\right) \)) וכן הלאה.

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

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

במקרה הראשון, הכלי המקפץ התקרב אל היעד יותר מאשר קודם. נניח שקודם הוא היה במרחק \( d \) מהיעד, וכשהוא נע הוא עבר שתי משבצות (הוא דילג על פני משבצת אחת ונכנס לבאה אחריה), זה אומר שאחרי ההגעה הוא נמצא במרחק \( d-2 \) מהיעד. הכלי שמעליו הוא קפץ חייב להיות במרחק \( d-1 \) מהיעד, מהטעם הפשוט שהוא נמצא בין משבצת שמרחקה מהיעד \( d-2 \) ומשבצת שמרחקה מהיעד \( d \) (אם הוא היה במרחק \( d-2 \) או קטן יותר בעצמו, לא ייתכן ששכנו היה במרחק \( d \) - גם השכן היה קרוב יותר; בדומה, אם הוא במרחק \( d \) או גדול יותר, לא ייתכן שיש לו שכן במרחק \( d-2 \)). לכן מהניקוד הכולל מופחת \( q^{d}+q^{d-1} \) ומתווסף אליו \( q^{d-2} \). אנחנו רוצים שהסוג הזה של צעדים - אלו שבהם כלי מתקרב למטרה - לא ישנה את הניקוד הכללי. לשם כך חייב להתקיים \( q^{d-2}=q^{d}+q^{d-1} \). אנחנו רוצים \( q \) חיובי (אם \( q=0 \) אז הניקוד הכולל הוא תמיד 0 וזה לא עוזר לכלום) ולכן מותר לחלק ב-\( q^{d-2} \), להעביר אגפים ולקבל את המשוואה: \( q^{2}+q-1=0 \).

את המשוואה הזו אפשר לפתור עם נוסחת השורשים הרגילה: פתרונותיה הם \( \frac{-1\pm\sqrt{5}}{2} \). בפני עצמם המספרים הללו נראים קצת מכוערים, אבל כשנותנים להם סימונים ושמות מפוצצים הם פתאום הופכים ליפים יותר. יש מספר מפורסם למדי (מהסיבות הנכונות או שלא מהסיבות הנכונות) בשם “יחס הזהב”, \( \varphi \), שלא אתחיל לתאר כאן - רק אציין שמבחינה מספרית, \( \varphi=\frac{\sqrt{5}+1}{2} \), שזה בדיוק מינוס של אחד הפתרונות שקיבלנו. אבל הפתרון הזה ממילא לא מעניין אותנו - אנחנו מתעניינים בפתרון השני, החיובי הקטן מ-1, \( \frac{\sqrt{5}-1}{2} \), שאסמן כ-\( \lambda \) (למה למבדא? כי אין לי רעיון יותר טוב, זה למה). אז לא קשה לראות שמתקיים \( \varphi-1=\lambda \) אבל פרט לכך יחס הזהב לא יעניין אותנו יותר.

אם כן, ה-\( \lambda \) שבחרנו מקיים \( \lambda^{2}+\lambda-1=0 \) ולכן גם \( \lambda^{d-2}=\lambda^{d}+\lambda^{d-1} \) ולכן צעד “לכיוון היעד” לא מגדיל את הניקוד בשיטת הניקוד שלנו. מה עם סוגי הצעדים האחרים?

ובכן, יש צעד “הרחק מהיעד” שבו מתחילים במרחק \( d \) ומסיימים במרחק \( d+2 \) אחרי שאוכלים כלי במרחק \( d+1 \). במקרה כזה השינוי בניקוד יהיה \( \lambda^{d+2}-\lambda^{d+1}-\lambda^{d}=\lambda^{d}\left(\lambda^{2}-\lambda-1\right) \). כעת, אם \( \lambda^{2}+\lambda-1=0 \) ו-\( \lambda^{2}-\lambda-1 \) מתקבל ממנו על ידי הפחתת \( 2\lambda \), ברור ש-\( \lambda^{2}-\lambda-1<0 \), כלומר צעד “הרחק מהיעד” מקטין את הניקוד הכללי (וזה לא ממש מפתיע).

בדומה, יש צעד “נייטרלי” שבו מתחילים במרחק \( d \) ומסיימים במרחק \( d \). זה קורה רק כשחולפים מעל כלי שנמצא בקו ישר עם היעד, ולכן קרוב יותר, כלומר במרחק \( d-1 \). במקרה זה השינוי בניקוד יהיה \( \lambda^{d}-\lambda^{d}-\lambda^{d-1}=-\lambda^{d-1} \) וזה שינוי שהוא בבירור שלילי.

מסקנה: עבור בחירת ה-\( \lambda \) שלנו, הניקוד הכולל במהלך המשחק לא יכול לגדול. כמו כן ברור שחייל שנמצא על משבצת היעד מוסיף 1 לניקוד הכולל (\( \lambda^{0} \)). כל שנותר להבין כעת הוא מה הניקוד הכולל בתחילת המשחק, כשכל החיילים מעבר לגבול. כאן סוף סוף מגיעה מתמטיקה טיפה טכנית אבל אתם כבר יודעים את הסוף - זה יצא 1; אז מי שמתייאש, לא נורא, זה לא העיקר.

בואו נתחיל מהשורה הראשונה שעל הגבול. המרחק של האמצע שלה - \( \left(0,0\right) \) - מהיעד הוא 5. המרחק של שני אלו שמצדדיו - 6, ואחר כך 7 וכדומה. בגלל שזה יותר נוח, בואו נסכום קודם כל את הערך המספרי של החלק ה”חיובי” של השורה - כל התאים מ-\( \left(0,0\right) \) כולל וימינה ממנו. נקבל את הסכום הבא:

\( \lambda^{5}+\lambda^{6}+\lambda^{7}+\dots=\lambda^{5}\left(1+\lambda+\lambda^{2}+\dots\right)=\frac{\lambda^{5}}{1-\lambda} \)

החלק השמאלי של השורה, לא כולל \( \left(0,0\right) \), זה אותו הדבר רק מתחיל מ-\( \lambda^{6} \), ולכן נקבל \( \frac{\lambda^{6}}{1-\lambda} \).

בשורה השניה התא האמצעי (\( \left(0,-1\right) \)) הוא במרחק 6, ולכן נקבל שסכום החלק הימני הוא \( \frac{\lambda^{6}}{1-\lambda} \) וסכום החלק השמאלי הוא \( \frac{\lambda^{7}}{1-\lambda} \), וכן הלאה.

בסופו של דבר נרצה לסכום גם את כל תוצאות הביניים הללו. כל תוצאה פרט ל-\( \frac{\lambda^{5}}{1-\lambda} \) מופיעה פעמיים, ולכן נקבל:

\( \frac{\lambda^{5}}{1-\lambda}+2\left(\frac{\lambda^{6}}{1-\lambda}+\frac{\lambda^{7}}{1-\lambda}+\dots\right) \)

נוציא גורם משותף מהסוגריים ונקבל:

\( \frac{\lambda^{5}}{1-\lambda}+\frac{2\lambda^{6}}{1-\lambda}\left(1+\lambda+\lambda^{2}\dots\right) \)

ועל ידי שימוש נוסף בנוסחת הסכום של טור הנדסי נקבל לבסוף:

\( \frac{\lambda^{5}}{1-\lambda}+\frac{2\lambda^{6}}{\left(1-\lambda\right)^{2}} \)

ועכשיו נחבר ונקבל:

\( \frac{\lambda^{5}+\lambda^{6}}{\left(1-\lambda\right)^{2}} \)

לא ברור איך להתקדם מהדבר הזה, עד שנזכרים שבחרנו את \( \lambda \) באופן כזה שיקיים את המשוואה \( \lambda^{2}+\lambda=1 \). כעת הכל נהיה יותר פשוט. במונה נוציא את הגורם \( \lambda^{4} \) ונקבל ש-\( \lambda^{5}+\lambda^{6}=\lambda^{4}\cdot1=\lambda^{4} \), ובמכנה נקבל ש-\( \left(1-\lambda\right)^{2}=\left(\lambda^{2}+\lambda-\lambda\right)^{2}=\lambda^{4} \) והנה המונה והמכנה מצטמצמים ומקבלים 1. קסם!

נסכם: בתחילת המשחק, סכום כל המשבצות שיש עליהן חיילים הוא 1. במהלך המשחק הניקוד הכולל יכול רק לרדת או להישאר כמו שהוא. ב”סוף” המשחק (כשיש חייל ביעד, \( \left(0,5\right) \)) הניקוד של אותה משבצת הוא 1 ושל כל משבצת אחרת שיש עליה חייל הוא חיובי, ולכן אם בסוף המשחק יש יותר מחייל אחד על הלוח, לא ייתכן שיהיה חייל במשבצת היעד. זה אומר שאם המשחק נמשך מספר סופי של צעדים אז אין שום דרך להגיע למשבצת \( \left(0,5\right) \). מלכתחילה זה סוג המשחק שעליו אנחנו חושבים כשמציגים לנו את החידה.

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