מה שהיה הוא שיהיה

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

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

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

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

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

החידה (שאיני בטוח מי המציא – קראתי שסם לויד המציא אותה, וקראתי שסם לויד שקרן ונויס צ'פמן המציא אותה, וקראתי שצ'פמן רק המציא את המשחק ואחד צ'רלס פיווי המציא את החידה) היא פשוטה: בואו נסתכל על הלוח כשהוא מעורבב "טיפה" – החלפנו את המיקום של לוחית מס' 14 ושל לוחית מס' 15. כיצד אפשר לסדר את הלוח מחדש כשזו הסיטואציה ההתחלתית?

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

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

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

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

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

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

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

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

מה ההפרש הזה? ובכן, גזרנו את המשבצת הימנית התחתונה והשמאלית העליונה, ושתיהן היו לבנות. כלומר, לפני שהתחלנו לכסות את הלוח באבני דומינו ההפרש היה 2 (בהתחלה ההפרש היה אפס; בגזירה הורדנו 2 משבצות לבנות, ואפס משבצות שחורות). גם אחרי שנניח אבן דומינו אחת על הלוח ההפרש יהיה 2. גם אחרי שנניח 20 אבנים על הלוח הוא יהיה 2, וגם אחרי שנניח 31 אבני דומינו על הלוח ההפרש יהיה 2...

אבל רגע, יש בלוח הגזור 62 משבצות, אז אם הנחנו 31 אבני דומינו עליו, זה אומר שכיסינו את כולו (כי כל אבן דומינו מכסה 2 משבצות). כלומר, אין בכלל משבצות גלויות, ולכן ההפרש בין מספר המשבצות הלבנות הגלויות למספר המשבצות השחורות הגלויות הוא 0, וזה לא בסדר. זה סותר את התכונה שראינו שנשמרת. לכן לא ייתכן שנצליח לשים 31 אבני דומינו על הלוח – כלומר, אין סיכוי שנכסה אותו.

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

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

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

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

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

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

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

לסיום, השורדים מקבלים את הפרס המובטח: השמורה של לוח משחק ה-15. אולי יש שמורה פשוטה יותר (אשמח לדעת עליה!), אבל בינתיים זה מה יש. הרעיון הבסיסי הוא להשתמש במושג של "הפרת סדר". יש בלוח הפרת סדר על כל זוג לוחיות שנמצאות במקום לא נכון זו ביחס לזו – למשל, אם לוחית מס' 13 נמצאת לפני לוחית מס' 5 בלוח (כשהסדר הוא משמאל לימין ומלמעלה למטה), זו הפרת סדר. בהינתן לוח כלשהו זה כאב ראש רציני לספור כמה הפרות סדר יש בו – אבל למרבה המזל, זה לא מה שמעניין אותנו. מעניינת אותנו רק הזוגיות של מספר הפרות הסדר.

קצת יותר במדויק – המספר שאנחנו מסתכלים בזוגיות שלו הוא המספר שמורכב ממספר הפרות הסדר שבלוח, ועוד מספר השורה שבה נמצאת המשבצת הריקה. למשל, בלוח המקורי, המסודר, המספר הזה הוא 4: יש 0 הפרות סדר, והשורה שבה נמצאת המשבצת הריקה היא 4. לעומת זאת, בלוח שבו בוצעה ההחלפה בין 14 ו-15, יש הפרת סדר בודדת, ועדיין השורה שבה נמצאת המשבצת הריקה היא 4, ולכן המספר הוא 5. כלומר, בלוח המסודר המספר שלנו הוא זוגי, ובלוח המעורבב הוא אי זוגי. לכן כל מה שיש להראות הוא שזוגיות המספר הזה נשמרת על ידי הפעולות החוקיות שאפשר לבצע על הלוח.

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

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


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com