אבן נייר ומספרים ולטאה וספוק ובלבאוזר וצ'רמנדר וגרפים איזומורפיים

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

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

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

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

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

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

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

אחרי ההפשטה, מה שנשאר לנו מהמשחק הוא זה:

ציור כזה נקרא גרף. יש בו שני סוגים של דברים: “עיגולים” ו”חצים”. לעיגולים קוראים צמתים ולחצים קוראים קשתות. ברמה הכי פורמלית של העניין, גרף הוא קבוצה \( V \) של צמתים (במקרה שלנו, הצמתים הם המספרים מ-1 עד 5) ועוד קבוצה \( E \) של קשתות, כשכל קשת היא זוג של צמתים, עם חשיבות לסדר: \( e=\left(v,u\right) \), ולפעמים מסמנים פשוט \( v\overset{e}{\to}u \).

גרף כזה הוא נקודת ההתחלה שלנו כשאנחנו באים לבנות משחק “אבן-נייר-ומספריים” מוכלל עבור חמישה נשקים - אנחנו לוקחים את הגרף, נותנים שם לכל צומת, ואז עבור כל קשת \( v\overset{e}{\to}u \) אנחנו ממציאים הסבר למה \( v \) מנצח את \( u \).

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

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

בואו ניקח את הגרף שהראיתי קודם:

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

עכשיו, מהצומת של בלבאוזר יוצאות שתי קשתות, אל הצמתים 2 ו-3. המשמעות שאני רוצה שתהיה לקשת \( v\overset{e}{\to}u \) היא “\( v \) מנצח את \( u \)” ולכן אני רוצה לשים בצמתים 2 ו-3 את הפוקימונים ש”עשב” מנצח - במקרה שלנו, הפוקימונים של “קרקע” ו”סלע”. אז אני אשים אותם שם, אבל צריך להיות זהירים: יש לי שתי דרכים לעשות את זה. או “2 הופך לסלע, 3 הופך לקרקע” או “2 הופך לקרקע, 3 הופך לסלע”. האם שתי הדרכים לגיטימיות? ובכן, לא! כי אני רוצה להמשיך לכבד את היחס \( 3\to2 \) שמופיע בגרף. מכיוון ש-3 מנצח את 2, גם מי ש-3 יהפוך אליו צריך לנצח את מי ש-2 הופך אליו. על פי חוקי הפוקימונים קרקע מנצחת סלע, ולכן 3 יהפוך לפוקימון הקרקע ו-2 יהפוך לפוקימון הסלע:

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

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

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

כדי לראות את זה, בואו נשים זה לצד זה את שני הגרפים כוכבי הפוסט:

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

• אבן עוברת אל עשב
• מספריים עוברים אל קרקע
• נייר עובר אל אש
• לטאה עוברת אל סלע
• ספוק עובר אל קרח

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

במקרה של גרף, יש לנו מבנה נוסף שאנחנו רוצים להתחשב בו - השאלה “מאיפה לאיפה יש קשת”. אני רוצה שאם ניקח שני קלטים \( x,y \) מהגרף המקורי כך שיש קשת \( x\to y \) אז תהיה קשת גם מהפלט של \( x \) אל הפלט של \( y \) - זה מה שהתאמצתי כל כך לשמור עליו כשבניתי את הגרף של הפוקימונים. בואו נראה איך זה כתוב פורמלית במתמטית: אם יש לנו שני גרפים, \( G_{1}=\left(V_{1},E_{1}\right) \) ו-\( G_{2}=\left(V_{2},E_{2}\right) \), ויש לנו פונקציה \( f:V_{1}\to V_{2} \) (כלומר, פונקציה שלוקחת קלט ששייך ל-\( V_{1} \) ומחזירה פלט ששייך ל-\( V_{2} \)) אנחנו רוצים שיתקיים ש-\( u\to v \) מתקיים אם ורק אם \( f\left(u\right)\to f\left(v\right) \) (או קצת יותר פורמלית: ש-\( \left(u,v\right)\in E_{1} \) מתקיים אם ורק אם \( \left(f\left(u\right),f\left(v\right)\right)\in E_{2} \)).

במקרה שבו יש לנו פונקציה \( f \) שמקיימת את התנאי הנ”ל והיא חד-חד-ערכית ועל, אומרים שהגרפים \( G_{1},G_{2} \) הם איזומורפיים ושהפונקציה \( f \) הזו היא איזומורפיזם של הגרפים הללו. המושג הזה, של איזומורפיזם של גרפים, הוא המושג המתמטי המרכזי שהולך לשחק תפקיד בכל מה שאני רוצה לדבר עליו בהקשר של אבן-נייר-ומספריים בהמשך.

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

• אבן עוברת אל סלע (זה מה שרציתי לעשות מההתחלה! זה הכי טבעי!)
• מספריים עוברים אל קרח
• נייר עובר אל קרקע
• לטאה עוברת אל אש
• ספוק עובר אל עשב

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

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