מחשבת - נקמתן של השמורות

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

מחשבת הוא משחק לשחקן בודד. לוח המשחק נראה בתחילת המשחק כך:

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

לפני שנים רבות (שלושים?) רעשה וגעשה הארץ כאשר יצאה לשוק גרסה “מורחבת” של המשחק, שבה הלוח גדול יותר, ונראה כך:

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

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

לצבעים אני הולך לקרוא \( a,b,c \). בנוסף יהיה עוד צבע, \( e \), שלא אצבע בו את הלוח אבל יבוא לידי ביטוי בכללי החשבון. הכללים הם פשוטים: \( a+a=b+b=c+c=e \), כלומר סכום של כל צבע עם עצמו הוא \( e \), ו-\( a+e=a,b+e=b,c+e=c \), כלומר הסכום של \( e \) עם כל צבע לא משנה את אותו הצבע (החיבור אצלי מקיים את חוק החילוף, כלומר \( a+e=e+a \) וכך לכל זוג צבעים). שימו לב שמשני הכללים שכבר נתתי נובעים דברים מורכבים יותר, נניח \( a+a+a=a+e=a \).

הכלל האחרון שאני נזקק לו הוא הכלל הבא: \( a+b=c,b+c=a,c+a=b \). כלומר, סכום של שניים משלושת הצבעים ה”מעניינים” נותן את הצבע השלישי. מכאן נובע, למשל, ש-\( a+b+c=c+c=e \). תכף נראה איך כל זה טוב לנו.

לאלו מכם שכל העסק נראה שרירותי מדי, אפשר לתת לסימבולים הללו משמעות מתמטית יותר קונקרטית. חשבו על \( \mathbb{Z}_{2}^{2} \) - אוסף הזוגות של 0 ו-1, עם פעולת חיבור רכיב-רכיב מודולו 2 (כלומר, בהינתן שני זוגות \( \left(x,y\right),\left(u,v\right) \) הסכום שלהם הוא \( \left(x+u,y+v\right) \) ובנוסף לכך מחלקים כל רכיב ב-2 ולוקחים את השארית). לא קשה לראות שאז אפשר לחשוב על \( e=\left(0,0\right),a=\left(1,0\right),b=\left(0,1\right),c=\left(1,1\right) \). ליצור הזה - אוסף ארבעת האיברים יחד עם פעולת החיבור הספציפית הזו - קוראים “חבורת קליין”.

כעת נצבע את הלוח, באופן הבא:

במבט ראשון הצביעה עשויה להיראות כמעט אקראית; אבל השיטה מאוד פשוטה. אני מעביר אלכסונים דרך הלוח, וצובע כל אלכסון באחד מהצבעים - תחילה ב-\( a \), אחר כך ב-\( b \), אחר כך ב-\( c \) ואז שוב ב-\( a \) וחוזר חלילה. האלכסונים עוברים מלמעלה מימין אל למטה משמאל. המטרה בצביעה בסגנון הזה פשוטה - להבטיח שבכל שלוש משבצות שאקח, שהן סמוכות זו לזו במאוזן, או סמוכות זו לזו במאונך, יהיו לי כל שלושת הצבעים \( a,b,c \) יחד (בדקו שזה אכן כך!). תכף יתברר מדוע זה טוב.

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

כדי לראות זאת, בואו נחשוב שוב מה אומר “מהלך” - קחו שלוש משבצות סמוכות (בשורה או בעמודה) שיש חיילים על שתיים סמוכות מהן והשלישית פנויה, ו”תחליפו” את הסיטואציה בכזו שבה שני החיילים הוסרו, ובמקום זאת יש לנו חייל על המשבצת שקודם הייתה פנויה. אם, למשל, המשבצות היו \( a,b,c \) כך שהמשבצות התפוסות היו \( a,b \), אז בתחילה התרומה של החלק הזה לסכום הכולל של הלוח הייתה \( a+b \) שהוא \( c \); ואחרי שסילקנו את החיילים מ-\( a,b \) ושמנו אחד ב-\( c \), התרומה של החלק הזה לסכום הכולל היא עדיין \( c \), ולכן שום דבר לא השתנה. זה הכל.

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

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

ועכשיו, בואו ננסה להשתמש בשיקול הזה גם על הלוח ה”מורחב”:

מה נשתנה בעצם? הוספנו ללוח ארבע משבצות, שנצבעות ב-\( a,b,b,c \). כלומר, סכום הצבעים שלהן הוא \( a+c+b+b=b+b+b=b \). מכאן שסכום הצבעים הכולל של הלוח הוא \( b+b=e \). מכאן שגם בסוף המשחק סכום הצבעים צריך להיות \( e \), ומכיוון שצבע זה לא מופיע בכלל על הלוח (הוא קיים רק כ”סכום” של צבעים, מבחינתנו), לא ייתכן שבסיום המשחק (או בכל שלב שלו) יהיה חייל בודד על הלוח. כלומר- המשחק לא פתיר, סוף פסוק.

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