אז מה לפיוצ'רמה ולתורת החבורות?

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

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

המתמטיקה לא יכולה לסבול תיאורים מילוליים כאלו. צריך לעשות סדר ולכתוב את הכל במסודר. ראשית כל ננסה להבין איזה אובייקט מתמטי יש לנו כאן - המושג המתאים הוא תמורה (ובעברית: פרמוטציה), אחד מהמושגים הבסיסיים שבתורת החבורות (אם כי יש להודות שאין הרבה תורת החבורות בפוסט הזה - הרעיונות הם בעיקרם קומבינטוריים). תמורה של \( n \) מספרים או אותיות מתארת החלפה ביניהם - כל מספר עובר למספר אחר מהקבוצה. התיאור של “כל אדם עובר לגוף אחר” הוא די מדוייק כאן. הנה הדרך שבה מתארים את התמורה שעברו אליס, בוב וצ’רלי: \( \left(\begin{array}{ccc}a & b & c\\c & a & b\end{array}\right) \). ה-\( a,b,c \) שלמעלה מסמלים את המוחות של אליס, בוב וצ’רלי; ה-\( c,a,b \) שלמטה מסמלים את הגופים שאליהם הם עברו. \( a \) מעל \( c \) אומר “אליס עברה לגוף של צ’רלי”, ו-\( b \) מעל \( a \) אומר שבוב עבר לגוף של אליס, וכן הלאה. המצב התקין שבו כל אחד בגוף האמיתי שלו מתואר על ידי \( \left(\begin{array}{ccc}a & b & c\\a & b & c\end{array}\right) \) (דבר כזה נקרא “תמורת הזהות”). לא יודע מה איתכם, אבל לי הרבה יותר קל להבין את הסיטואציה כשאני רואה \( \left(\begin{array}{ccc}a & b & c\\c & a & b\end{array}\right) \) מול העיניים. זה לקח חשוב לדעתי - סימונים מתמטיים נועדים לעשות את החיים קלים יותר, למרות שלעתים קרובות אוהבים להציג אותם כדברים קשים ומבלבלים.

כיצד ניתן להמשיך מהמצב הנוכחי? מכיוון ש-\( a \) רוצה לחזור ל-\( a \), וכרגע הוא ב-\( c \), אז מתבקש להחליף את הגוף של \( c \) עם הגוף של \( a \). זה יעביר אותנו לסיטואציה \( \left(\begin{array}{ccc}a & b & c\\a & c & b\end{array}\right) \) - תמורה שזהה לקודמת פרט לכך ש-\( a,c \) בשורה התחתונה החליפו את מקומותיהם. אבל זה מצב בעייתי כי החלפת הגופים של \( b,c \) כבר בוצעה פעם אחת ולא חוקי לבצע אותה שוב. אז עושה רושם שאי אפשר לתקן את הסיטואציה המעוותת על ידי הכנסת דמות חדשה אחת לתמונה. האם אפשר עם שתיים? כמובן שהפרק חיש קל יוצר ערבוביה איומה ונוראית מכל הדמויות בסדרה, אבל לבסוף הכל בא על מקומו בשלום כשמסתבר שאכן, אפשר לתקן כל מהומה שכזו - ולא משנה כמה הדמויות התערבבו, ולא משנה כמה החלפות כבר בוצעו (ולכן “נשרפו” ואסור להשתמש בהן יותר) אם מכניסים לתמונה שתי דמויות חדשות שאפשר להשתמש בהן.

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

אם כן, מה הפתרון? קילר משתמש בתעלול נפוץ שנוקטים בו כשעוסקים בתמורות - כל תמורה אפשר לפרק למכפלת מעגלים זרים. למה הכוונה? ובכן, נניח שנתונה לנו תמורה כללית כלשהי. נבחר באופן שרירותי את אחד מהמשתתפים במשחק ונסמן אותו ב-\( 1 \). כעת, נסמן את מי ש-\( 1 \) עבר אליו כ-\( 2 \), ואת מי ש-\( 2 \) עבר אליו כ-\( 3 \) וכן הלאה. מתישהו חייב להופיע מישהו שכבר סימנו במספר כי יש רק מספר סופי של משתתפים במשחק. כלומר, יש מספר \( k \) שעובר למספר שכבר ראינו. אבל לאן \( k \) יכול לעבור בכלל? הוא לא יכול לעבור ל-\( 2 \), כי \( 2 \) כבר תפוס - \( 1 \) עבר אליו. וגם ל-\( 3 \) הוא לא יכול לעבור מאותה סיבה, וכן הלאה; אם כן, הוא יכול לעבור רק ל-\( 1 \). זהו ה”מעגל” המדובר - \( 1 \) עובר ל-\( 2 \), ו-\( 2 \) עובר ל-\( 3 \) וכן הלאה. מסמנים זאת כ-\( \left(\begin{array}{cccc}1 & 2 & \cdots & k\\2 & 3 & \cdots & 1\end{array}\right) \) (ולעתים גם כ-\( \left(123\dots k\right) \) אבל לא אשתמש כאן בסימון זה).

עכשיו, ייתכן מאוד שלא תפסתי את כל המשתתפים בתמורה באופן הזה. אם כן, פשוט אקח מישהו שטרם סימנתי, אסמן אותו ואתחיל לבנות מעגל חדש החל ממנו. כך למשל התמורה \( \left(\begin{array}{cccc}1 & 2 & 3 & 4\\3 & 4 & 1 & 2\end{array}\right) \) ניתנת לתיאור כמכפלת שני המעגלים \( \left(\begin{array}{cc}1 & 3\\3 & 1\end{array}\right)\left(\begin{array}{cc}2 & 4\\4 & 2\end{array}\right) \) (אם כי אם ננקוט בשיטה שהצעתי, המספור של האיברים יהיה שונה). הפאנץ’ פה הוא שיספיק לנו לטפל בכל מעגל בנפרד ו”לתקן” אותו, כל עוד לא נעבור על הכלל שלפיו אסור לבצע את אותה החלפה יותר מפעם אחת.

אם כן, נניח שיש לנו את המעגל \( \left(\begin{array}{cccc}1 & 2 & \cdots & k\\2 & 3 & \cdots & 1\end{array}\right) \). מה עושים? קילר מציע קודם כל להכניס למשחק שני שחקנים חדשים, \( x,y \). נקבל את התמורה \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\2 & 3 & \cdots & 1 & x & y\end{array}\right) \). כעת הוא מציע להחליף את מי שבגוף של \( 1 \) עם מי שבגוף של \( x \) - הוא מסמן זאת כ-\( \left\langle 1,x\right\rangle \). בפועל זה אומר להחליף את שני המספרים בשורה התחתונה של התמורה שמעליהם, בשורה העליונה, מופיעים \( 1 \) ו-\( x \). כלומר, נקבל \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\x & 3 & \cdots & 1 & 2 & y\end{array}\right) \).

עכשיו קילר מציע לבצע את \( \left\langle 2,x\right\rangle \). נקבל \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\x & 2 & \cdots & 1 & 3 & y\end{array}\right) \). אני מניח שהרעיון ברור כעת - “תיקנו” את \( 2 \), ואם נבצע את \( \left\langle x,3\right\rangle \) נתקן גם את 3 וכן הלאה. אז למה לא מספיק להשתמש ב-\( x \) וחסל? כי אם נמשיך להשתמש ב-\( x \) לכל אורך הדרך, בסופו של דבר נגיע לתמורה \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\x & 2 & \cdots & k & 1 & y\end{array}\right) \) וכדי לתקן אותה נזדקק להחלפה \( \left\langle 1,x\right\rangle \) שכבר ביצענו. פתרון אפשרי אחד הוא לבצע כעת \( \left\langle x,y\right\rangle \) ולקבל \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\x & 2 & \cdots & k & y & 1\end{array}\right) \) ולאחר מכן לבצע \( \left\langle 1,y\right\rangle \) ולקבל \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\1 & 2 & \cdots & k & y & x\end{array}\right) \) אבל אז אמנם תיקנו את המעגל המקורי, אך במחיר החלפה של \( x,y \) שכבר לא נוכל לתקן (כי ביצענו את \( \left\langle x,y\right\rangle \)).

לכן קילר מציע להפסיק את השימוש ב-\( x \) אי שם באמצע הדרך. הוא מציע לעשות את זה במקום שרירותי שהוא מסמן ב-\( i \), ואני אדגים את זה עבור \( i=1 \). כלומר, אני מבצע רק את ההחלפה \( \left\langle x,1\right\rangle \) ומקבל \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\x & 3 & \cdots & 1 & 2 & y\end{array}\right) \). כעת קילר מכניס את \( y \) לפעולה; אם \( x \) ביצע את כל ההחלפות עד \( \left\langle x,i\right\rangle \), אז מעתה ואילך יתבצעו החלפות \( \left\langle y,i+1\right\rangle \) ומעלה. כלומר, אני מבצע את ההחלפה \( \left\langle y,2\right\rangle \) ומקבל \( \left(\begin{array}{cccccc}1 & 2 & \cdots & k & x & y\\x & y & \cdots & 1 & 2 & 3\end{array}\right) \), ואז מבצע את \( \left\langle y,3\right\rangle \) ובכך “מתקן” את 3, וכן הלאה וכן הלאה עד שאני מקבל \( \left(\begin{array}{cccccc}1 & 2 & 3\cdots & k & x & y\\x & y & 3\cdots & k & 2 & 1\end{array}\right) \). כלומר, גם \( x \) וגם \( y \) נמצאים עכשיו בתוך שטח האויב, אבל קל מאוד לתקן את זה - מבצעים \( \left\langle y,1\right\rangle \) ו-\( \left\langle x,2\right\rangle \) (ובאופן כללי: \( \left\langle x,i+1\right\rangle \)). אלו שתי החלפות שמובטח לי שטרם עשיתי (כי את ההחלפות עם \( x \) הפסקתי ב-\( \left\langle x,i\right\rangle \) ואת ההחלפות עם \( y \) התחלתי רק מ-\( \left\langle y,i+1\right\rangle \)). והופס - אני אקבל \( \left(\begin{array}{cccccc}1 & 2 & 3\cdots & k & x & y\\1 & 2 & 3\cdots & k & y & x\end{array}\right) \). זה בדיוק הפתרון שקיבלתי גם קודם, בהבדל משמעותי אחד: כעת טרם ביצעתי את ההחלפה \( \left\langle x,y\right\rangle \)! אני יכול לבצע אותה כעת ולקבל שהכל שב על מקומו בשלום. שימו לב שכל ההחלפות שביצעתי היו מהצורה \( \left\langle x,i\right\rangle \) ו-\( \left\langle y,i\right\rangle \) עבור \( 1\le i\le k \) כלשהם. כלומר, כל החלפה עירבה את \( x \) או את \( y \) ולכן לא ייתכן שנבצע החלפה “אסורה” - פשוט כי כל ההחלפות שהביאו את התמורה למצבה הנוכחי היו בין זוגות שבהם לא הופיע לא \( x \) ולא \( y \).

אלא מה? זה פותר מעגל אחד, אבל אמרנו שהתמורה הכללית עשויה להיות מורכבת ממספר מעגלים. הבעיה הזו נפתרת עם אבחנה פשוטה אבל מקסימה: לא חייבים להזדרז ולתקן את ההחלפה בין \( x \) ו-\( y \); אפשר לשלוח אותם לטפל במעגל הבא בתור, ולא רק שזה יעבוד באותו האופן, זה גם יחזיר את \( x,y \) לגופים המקוריים שלהם בלי הצורך להחליף אותם במפורש (למה?). כמובן, ייתכן שנצטרך לשלוח אותם לטפל במעגל נוסף, ואז הם שוב יתחלפו… אבל בסופו של דבר, אחרי שנסיים עם כל המעגלים, אחד משניים: או שהם בגוף המקורי שלהם ואז אין בעיה, או שהם הוחלפו, ואז נבצע את ההחלפה \( \left\langle x,y\right\rangle \) ששמרנו לסוף, ונסיים.

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