חיילי קונוויי

חיילי קונוויי הוא משחק מתמטי לאדם יחיד, הדומה למשחק מחשבת, שהומצא ונחקר על ידי המתמטיקאי הבריטי ג'ון הורטון קונוויי בשנת 1961.

תיאור המשחק

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

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

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

הוכחת קונוויי

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

משקל

נבחר משבצת יעד. נגדיר את ה"משקל" של משבצת בלוח להיות $\ \varphi ^{n}$ כאשר $\ \varphi =1/\phi =\phi -1={\frac {{\sqrt {5}}-1}{2}}$ הוא ההופכי של יחס הזהב $\ \phi$, ו-n הוא המרחק של המשבצת ממשבצת היעד (מספר המשבצות המינימלי במאונך ובמאוזן שיש לעבור כדי להגיע מהמשבצת למשבצת היעד, בדומה לגאומטריית נהגי המוניות). בהתאם להגדרה זו, המשקל של משבצת היעד עצמה הוא $\ \varphi ^{0}=1$. מהגדרתו של $\ \varphi$ נובע: $\ \varphi ^{2}+\varphi -1=0$ (למעשה בחרנו את $\ \varphi$ כך שיקיים זהות זו). נבחין כי מהזהות נובע כי לכל $\ n>1$ מתקיים $\ \varphi ^{n}=\varphi ^{n-2}-\varphi ^{n-1}$. נשתמש בכך כדי לחשב את סכום הטור הטלסקופי שישמש אותנו בהמשך (ניתן לחשב גם עם הנוסחה לסכום טור הנדסי):

$\ \sum _{n=2}^{\infty }\varphi ^{n}=\sum _{n=2}^{\infty }(\varphi ^{n-2}-\varphi ^{n-1})=1$.

ערך של מצב

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

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

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

הוכחה שלא ניתן להגיע לשורה החמישית

נראה עכשיו כי עם מספר סופי של צעדים לא ניתן להגיע לשורה החמישית. הערך התחילי המקסימלי מתקבל כאשר על כל המשבצות שמתחת לקו יש כלי. נחשב את הערך במקרה כזה: נניח כי משבצת היעד מצויה בשורה ה-m מעל לקו. ערך המשבצת הקרובה ביותר אליה מתחת לקו נמצאת m משבצות בדיוק מתחתיה ומשקלה $\ \varphi ^{m}$. המשבצות מימינה משמאלה הן בעלות משקל $\ \varphi ^{m+1}$, ולצד כל אחת מהן מצויה משבצת בעלת משקל $\ \varphi ^{m+2}$ וכן הלאה. בסך הכל סכום משקלי המשבצות בשורה הראשונה מתחת לקו הוא:

$\ \varphi ^{m}+2\varphi ^{m+1}+2\varphi ^{m+2}+\ldots =\varphi ^{m-1}(\varphi +2(\varphi ^{2}+\varphi ^{3}+\varphi ^{4}+\ldots ))=\varphi ^{m-1}(\varphi +2)$ (השוויון האחרון לפי סכום הטור שחישבנו).

השורה השנייה מתחת לקו מרוחקת משבצת אחת מן השורה הראשונה ולכן סכום משקלי משבצותיה שווה לסכום משקלי השורה הראשונה כפול $\ \varphi$. ובאופן כללי סכום משקלי השורה ה-k מתחת לקו הוא: $\ \varphi ^{m+k-2}(\varphi +2)$. את הערך של המצב נקבל כסכום המשקלים של כל השורות מתחת לקו, כלומר:

$\ \sum _{k=1}^{\infty }\varphi ^{m+k-2}(\varphi +2)=\varphi ^{m-2}(\varphi +2)\sum _{k=1}^{\infty }\varphi ^{k}=\varphi ^{m-2}(\varphi +2)(\varphi +1)$

בפרט ההצבה m=5 נותנת ערך תחילי מקסימלי $\ \varphi ^{3}(\varphi +2)(\varphi +1)=1$ (ניתן לחשב ישירות). כלומר הדרך היחידה שבה אולי ייתכן להגיע למשבצת בשורה החמישית מעל הקו היא להתחיל עם אינסוף כלים על כל המשבצות מתחת לקו (ערך 1) ולסיים עם כלי יחיד על משבצת יעד בשורה החמישית (ערך 1) - כל כלי נוסף יעלה את הערך מעל 1. אך גם זה לא ייתכן, כי לא ניתן להעלים את כל הכלים ולהישאר עם כלי אחד במספר סופי של צעדים.

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

הכללות

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

הוכח כי בגרסה ה-n ממדית של המשחק ניתן להגיע לשורה ה-3n-2, אך לא לשורה ה-3n-1. ההוכחה של קונווי יפה גם למקרים אלה, אך להראות שניתן להגיע לשורה ה-3n-2 דורש כבר יותר מאמץ.

בספרות

המשחק (או החידה) מוזכרים בספר המקרה המוזר של הכלב בשעת לילה של מארק האדון.

לקריאה נוספת

• E. Berlekamp, J. Conway and R. Guy, Winning Ways for Your Mathematical Plays, 2nd ed., Vol. 4, Chap. 23: 803—841, A K Peters, Wellesley, MA, 2004.

קישורים חיצוניים

• חיילי קונוויי, באתר MathWorld (באנגלית)
• גדי אלכסנדרוביץ', חידת החיילים של קונווי, באתר "לא מדויק", 31 באוגוסט 2011