ארכיון חודשי: יוני 2009

על סכומי ריבועים והקשר להדדיות ריבועית

פורסם בתאריך על ידי
3

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

אם כן, נתחיל מהתחלה. פרמה נהג, כידוע, לתאר תגליות מתמטית במכתבים לידידים, לרוב בלי הוכחה של ממש. כך היה גם במכתב מ-1640 למרסן (אותו מרסן ממספרי מרסן שגם כן הזכרתי כשדיברתי על פרמה). פרמה טען שהוא יודע מתי מספר ראשוני \(p\) ניתן להצגה כסכום של שני ריבועים שלמים, כלומר \(p=x^{2}+y^{2}\) עם \(x,y\) שלמים; הוא טען שזה מתרחש בדיוק כאשר \(p\) מותיר שארית של 1 כאשר מחלקים אותו ב-4. בכתיבה מודרנית, זה מתואר כך: \(p\equiv1\left(4\right)\). פרמה לא עצר כאן – הוא טען שניתן להציג את \(p\) בתור \(p=x^{2}+2y^{2}\) בדיוק כאשר \(p\equiv1,3\left(8\right)\), ולקינוח טען שניתן להציג את \(p\) בתור \(p=x^{2}+3y^{2}\) אך ורק כאשר \(p\equiv1\left(3\right)\) (או כאשר \(p=3\) בעצמו, אבל זה מקרה בודד ולכן לא מעניין). תאמרו שלא ברור למה להתעמק דווקא בראשוניים ולא בכל המספרים – הסיבה לכך היא שכל מספר ניתן לכתיבה כמכפלה של ראשוניים, ולכן הבנת הטענה על הראשוניים היא הצעד הראשון והחשוב ביותר בדרך לטענה כללית על כל המספרים.

פרמה טען במכתב שיש לו "הוכחות מוצקות" לטענות הללו, אך לא כתב אותן. למעשה, לא כל כך ברור מה היו ההוכחות שלו – פשפוש בכתביו מעלה רק הוכחה בסגנון הבא: "אם \(p\equiv1\left(4\right)\) אבל לא ניתן להציג אותו כסכום ריבועים, אז חייב להיות ראשוני קטן יותר מאותה הצורה שגם אותו לא ניתן להציג כסכום של שני ריבועים, וכן הלאה בנסיגה אינסופית עד שמגיעים ל-5 – סתירה". זו לא ממש הוכחה – פרמה לא מסביר למה יש ראשוני קטן יותר, או איך למצוא אותו. נעשו ניתוחים כלשהם של כתבי פרמה שניסו לשחזר הוכחה מסודרת יותר, אך לא אכנס אליהם כאן כי אני רוצה להעביר את הכדור לאוילר – ואוילר, כששמע על פרמה ומשפטיו, לא ידע הרבה יותר משאנחנו יודעים. המשפטים הללו של פרמה נראה לו כמו השערות מעניינות (ואכן, פרמה דייק לגמרי; המשפטים הללו נכונים), אך הייתה חסרה לו ההוכחה.

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

מבחינה היסטורית, את שלב הנסיגה אוילר סיים יחסית מהר – הוא תיאר אותו במכתב לגולדבך בשנת 1741. רק בשנת 1749 עלה בידי אוילר לפתור את שלב ההדדיות עבור המקרה של \(p=x^{2}+y^{2}\); המקרים האחרים דרשו לו זמן רב יותר, והעבודה נשלמה רק בשנת 1772 – יותר מ-40 שנים לאחר שאוילר שמע על הבעיה לראשונה.

בין לבין הוא עשה עוד דברים.

ובכן, מהם שני השלבים? אתאר ראשית את שלב הנסיגה עבור המקרה של סכום שני ריבועים, שהוא הפשוט ביותר; בשני המקרים האחרים ההכללה די מיידית אך מעט יותר מסובכת. אני מזהיר מראש שהשלב הזה טכני למדי ואינו המטרה העיקרית שלי בפוסט, כך שמי שמתייאש יכול לדלג. שלב הנסיגה אומר שאם הראשוני \(p\) מחלק סכום של שני ריבועים, \(a^{2}+b^{2}\), אז הוא ניתן לכתיבה כסכום של שני ריבועים בעצמו. ההוכחה של הטענה הולכת כך: מניחים שלא ניתן לכתוב את \(p\) כסכום של שני ריבועים, ומוכיחים כי נובע מכך שקיים ראשוני \(q<p\) שגם הוא מחלק סכום של שני ריבועים אך אינו ניתן לכתיבה כסכום של שני ריבועים. מכאן שאפשר שוב לחזור על הטענה ולקבל עוד ראשוני \(q^{\prime}<q\) שגם כן מקיים את התכונה הזו, וכן הלאה וכן הלאה – וכך נגיע לראשוניים קטנים יותר ויותר, עד שניתקע עם ראשוני קטן מדי, שכן ניתן להציג כסכום של שני ריבועים (למשל, 2).

עד כה לא אמרנו הרבה יותר מאשר פרמה – רק פרטים קצת יותר מדוייקים. עלינו להראות כיצד, בהינתן \(p\) שמחלק סכום של שני ריבועים אך אינו סכום שכזה בעצמו, ניתן למצוא \(q<p\) דומה. לב העניין הוא באבחנה שאם \(N=a^{2}+b^{2}\) הוא סכום של שני ריבועים זרים ("זרים" פירושו שאין ל-\(a,b\) מחלק משותף גדול מ-1) ו-\(q\) הוא ראשוני שהוא בעצמו סכום של שני ריבועים, אז גם \(\frac{N}{q}\) הוא סכום של שני ריבועים זרים. ההוכחה של האבחנה הזו היא טכנית ומכילה כמה משוואות ואני מעדיף לא להיכנס אליה.

אם כן, נתון לנו ש-\(N=a^{2}+b^{2}\), כך ש-\(p|a^{2}+b^{2}\) (הקו פירושו "\(p\) מחלק את \(a^{2}+b^{2}\)"). נשים לב שאפשר לחסר או לחבר את \(p\) בחופשיות הן ל-\(a\) והן ל-\(b\) ועדיין ש-\(p\) יחלק את סכום הריבועים שלהם (בדקו זאת!), ולכן אפשר להניח כי שניהם קטנים יחסית ל-\(p\), נניח \(\left|a\right|,\left|b\right|<\frac{p}{2}\) (אחרת אפשר לחסר מהם את \(p\) שוב ושוב עד שהם נהיים קטנים מספיק). אחרי שעשינו זאת צריך לחלק את \(a,b\) שקיבלנו בגורם המשותף הגדול ביותר שלהם כדי להבטיח ששני המספרים שנקבל יהיו זרים זה לזה (למה \(p\) עדיין יחלק את \(a^{2}+b^{2}\) גם אחרי שנחלק אותם בגורם הזה? כי \(p\) לא מחלק את הגורם הזה בעצמו – למה, ולמה זה מספיק?)

אם כן, נסכם את מה שמגיעים אליו: שקיים \(N=a^{2}+b^{2}\) כך ש-\(p|N\) וכמו כן \(a,b\) זרים זה לזה ומקיימים \(\left|a\right|,\left|b\right|<\frac{p}{2}\), כלומר \(N=a^{2}+b^{2}<\frac{p^{2}}{4}+\frac{p^{2}}{4}=\frac{p^{2}}{2}\). מכאן עולה שאם \(q\) הוא גורם ראשוני של \(N\) השונה מ-\(p\), הוא בהכרח קטן מ-\(p\); אחרת היינו מקבלים \(\frac{p^{2}}{2}>N\ge pq\ge p^{2}\) – סתירה. כעת, אם \(q\) הוא סכום של שני ריבועים, אז מהאבחנה שתיארתי לעיל היה נובע שגם \(\frac{N}{q}\) הוא סכום של שני ריבועים; ואם היינו חוזרים על החלוקה הזו לכל גורם של \(N\) שאיננו \(p\), היינו מקבלים בסופו של דבר את \(p\) כסכום של שני ריבועים (וזה מה שרצינו). לכן אם \(p\) איננו סכום של שני ריבועים, אז קיים \(q<p\) שגם הוא איננו סכום של שני ריבועים, ועם זאת \(q|N=a^{2}+b^{2}\), כלומר זה הראשוני הקטן יותר שחיפשנו – וזה מסיים את ההוכחה.

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

השלב השני בהוכחה של אוילר הוא מה שמכונה "שלב ההדדיות". בשלב הנסיגה, נקודת המוצא הייתה ש-\(p\) מחלק סכום של שני ריבועים, או בלשון מודרנית, ש-\(a^{2}+b^{2}\equiv0\left(p\right)\), עבור \(a,b\) זרים (ולכן בפרט לא שקולים שניהם לאפס מודולו \(p\) – כלומר, אנחנו רוצים פתרון "לא טריוויאלי" למשוואה). האתגר של שלב ההדדיות הוא להראות עבור אילו ערכי \(p\) הדבר הזה מתקיים. אוילר הוכיח בשיטה משלו – חשבון הפרשים, המקבילה הדיסקרטית של החשבון הדיפרנציאלי, נושא מעניין לכשעצמו – כי כדי שלמשוואה הזו יהיה פתרון צריך להתקיים \(p\equiv1\left(4\right)\). עם זאת, אני רוצה לגשת לשאלה הזו מנקודת מבט מעט יותר מודרנית, ותוך התייחסות לשתי הבעיות הנוספות – אוילר גם רצה לדעת באילו תנאים על \(p\) יש פתרון למשוואה \(a^{2}+2b^{2}\equiv0\left(p\right)\), ובאילו תנאים יש פתרון למשוואה \(a^{2}+3b^{2}\equiv0\left(p\right)\).

נתחיל מהמשוואה \(a^{2}+b^{2}\equiv0\left(p\right)\). על ידי העברת אגפים נקבל \(a^{2}\equiv-b^{2}\left(p\right)\). מכיוון שאנו מניחים ש-\(b\not\equiv0\left(p\right)\) (כי \(b\equiv0\left(p\right)\) יתן לנו את הפתרון הטריוויאלי של המשוואה, שכאמור לא מועיל לנו) אפשר לחלק בו ולקבל \(\left(\frac{a}{b}\right)^{2}\equiv-1\left(p\right)\). על ידי החלפת משתנים אפשר לכתוב את המשוואה הזו בתור \(x^{2}\equiv-1\left(p\right)\). כלומר, הצטמצמנו לשאלה הבאה: מתי \(-1\) הוא ריבוע מודולו \(p\)? ובטרמינולוגיה שבדרך כלל משתמשים בה: מתי \(-1\) הוא שארית ריבועית מודולו \(p\)?

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

כדי לטפל בבעיה הזו בצורה רצינית, מאוד מועיל לבצע שינוי נוסף של נקודת המבט – במקום להמשיך לדבר על מספרים מודולו \(p\) כל הזמן, אפשר לעבור ולדבר על איברים בחבורה \(\mathbb{Z}_{p}^{*}\) – אוסף כל המספרים \(\left\{ 1,\dots,p-1\right\} \) עם פעולה של כפל מודולו \(p\) (כופלים שני מספרים, מחלקים ב-\(p\) והתוצאה היא השארית). החבורה הזו היא אחד מהאובייקטים הבסיסיים בתורת המספרים, וידוע עליה הרבה מאוד – בפרט, שהיא ציקלית, כלומר לכל \(p\) קיים \(g\in\mathbb{Z}_{p}^{*}\) כך שכל איבר \(a\in\mathbb{Z}_{p}^{*}\) ניתן לכתיבה בתור \(a=g^{k}\) עבור \(k\) מתאים כלשהו. ברור שאם \(a=g^{2k}\), כלומר \(a\) הוא חזקה זוגית של \(g\), אז \(a\) הוא שארית ריבועית, כי הוא ניתן לכתיבה בתור \(\left(g^{k}\right)^{2}\); ניתן להראות גם את ההפך, שאם \(a=g^{2k+1}\), כלומר הוא חזקה אי זוגית, אז הוא אינו שארית ריבועית (זהו תרגיל נחמד לאלו מכם שבקיאים בתורת החבורות). כעת, \(g\) מקיים \(g^{p-1}=1\) (זהו "המשפט הקטן של פרמה"), ולכן ברור שאם \(a=g^{2k}\) אז \(a^{\frac{p-1}{2}}=\left(g^{p-1}\right)^{k}=1\); ולעומת זאת, אם \(a=g^{2k+1}\) אז \(a^{\frac{p-1}{2}}=\left(g^{2k}\cdot g\right)^{\frac{p-1}{2}}=\left(g^{p-1}\right)^{k}\cdot g^{\frac{p-1}{2}}=g^{\frac{p-1}{2}}=-1\) – שוב, הבקיאים בתורת החבורות ודאי ירצו להצדיק לעצמם את המעבר האחרון, דהיינו ש-\(g^{\frac{p-1}{2}}=-1\) (רמז: מהו אגף שמאל בריבוע? ומדוע ידוע לנו שאגף שמאל שונה מ-1?). האבחנות הללו מובילות אותנו למה שמכונה "קריטריון אוילר" (אם כי לא ברור לי כלל שאוילר הגיע אליו כך): מספר \(a\) הוא שארית ריבועית מודולו \(p\) אם ורק אם \(a^{\frac{p-1}{2}}\equiv1\left(p\right)\).

הקריטריון הזה מחסל לנו מייד את המקרה של \(-1\): \(\left(-1\right)^{\frac{p-1}{2}}=1\) אם ורק אם \(\frac{p-1}{2}\) הוא זוגי, כלומר אם ורק אם \(p-1\) מתחלק ב-4, כלומר אם ורק אם \(p\equiv1\left(4\right)\). כדי להתחיל את הטיפול במקרים האחרים, אני רוצה להכניס לתמונה סימון נוח – סימן לג'נדר. סימן לג'נדר של \(a\) מעל \(p\) מסומן בתור \(\left(\frac{a}{p}\right)\), מה שמזכיר באופן מבלבל שבר, אבל ניתן כמעט תמיד להבין מההקשר שמדובר בסימן לג'נדר ולא בשבר. הוא מוגדר כך: אם \(a\) אינו זר ל-\(p\), אז \(\left(\frac{a}{p}\right)=0\); אם \(a\) הוא שארית ריבועית מודולו \(p\) אז \(\left(\frac{a}{p}\right)=1\), ואם הוא אינו שארית ריבועית מודולו \(p\), אז \(\left(\frac{a}{p}\right)=-1\). אם כן, את קריטריון אוילר ניתן לכתוב בצורה קומפקטית באופן הבא: \(\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\left(p\right)\).

סימן לג'נדר מאפשר לנו לתת תיאור קומפקטי של עוד עובדות בסיסיות, למשל \(\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\) – נסו להבהיר לעצמכם שאתם מבינים מה זה אומר (ולבקיאים בתורת החבורות – איך להוכיח את זה?). כמו כן, אם \(a\equiv b\left(p\right)\) אז \(\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)\). לבסוף, הוא מאפשר לנו לתאר בצורה פשוטה גם את התכונה המשמעותית ביותר של שאריות ריבועיות – משפט ההדדיות הריבועית. הוא מנוסח בפשטות כך: אם \(p,q\) שניהם ראשוניים אי זוגיים שונים זה מזה, אז מתקיים הקשר הבא: \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}\). בניסוח מילולי, אפשר לומר שמשפט ההדדיות אומר שסימן לג'נדר של \(p\) מעל \(q\) וסימן לג'נדר של \(q\) מעל \(p\) הם זהים תמיד, פרט למקרה שבו \(p\equiv q\equiv3\left(4\right)\), ואז הם הפוכים זה לזה.

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

לא אכנס כאן לניתוח של השאלה מתי \(-2\) הוא שארית ריבועית מודולו \(p\) (מן הסתם המסקנה הסופית היא ש-\(p\equiv1,3\left(8\right)\)) כי הוא טכני ולא מחכים עד כדי כך. לעומת זאת, הניתוח של המקרה של \(-3\) נותן לנו הזדמנות יפה לראות את משפט ההדדיות הריבועית בשיא כוחו (והעובדה שאני נזקק להדדיות ריבועית רומזת משהו על הקושי שהיה לאוילר, שלא הכיר את משפט ההדדיות הריבועית, כשניסה לטפל במקרה הזה בעצמו). זאת מכיוון ש-3 הוא ראשוני, ולכן אפשר להשתמש בו בתור ה-\(q\) שמופיע במשפט ההדדיות הריבועית. היתרון של משפט ההדדיות הריבועית יהיה בכך שהוא יהפוך את השאלה "מתי \(3\) הוא שארית ריבועית מודולו \(p\)?" לשאלה "מתי \(p\) הוא שארית ריבועית מודולו 3?", ומהתכונה שהצגתי קודם, לפיה אם \(a\equiv b\left(q\right)\) אז \(\left(\frac{a}{q}\right)=\left(\frac{b}{q}\right)\) אפשר לראות שזו שאלה יחסית קלה כי מספיק לבדוק באופן ישיר מספר קטן של מקרים: לא קשה לראות כי \(\left(\frac{1}{3}\right)=1\) ואילו \(\left(\frac{2}{3}\right)=-1\).

אם כן, נשתמש בהדדיות ריבועית ובמה שכבר גילינו על \(\left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}}\) ונקבל את החישוב הישיר הבא:

\(\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=\left(-1\right)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\left(-1\right)^{\frac{p-1}{2}}=\left(\frac{p}{3}\right)\)

כלומר, משפט ההדדיות הריבועית לימד אותנו ש-\(\left(\frac{-3}{p}\right)\) הוא בדיוק \(\left(\frac{p}{3}\right)\), ולכן הוא 1 אם ורק אם \(p\equiv1\left(3\right)\), בדיוק כפי שציפינו שנקבל. כמובן שהשתמשתי כאן בתותח כבד; אבל מכיוון שמטרת הפוסט העיקרית הייתה להציג את התותח הזה, אין לי חרטות.

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

פורסם בתאריך על ידי
22

הפוסט הראשון שלי בבלוג תיאר את הצורה שבה מושג השמורות (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\), ומכיוון שצבע זה לא מופיע בכלל על הלוח (הוא קיים רק כ"סכום" של צבעים, מבחינתנו), לא ייתכן שבסיום המשחק (או בכל שלב שלו) יהיה חייל בודד על הלוח. כלומר- המשחק לא פתיר, סוף פסוק.

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

איך תופסים אריה במדבר?

פורסם בתאריך על ידי
23

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

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

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

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

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

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

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

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

אם כן: אחרי קריאת אפס שמות, יש לי \(N\) שמות לחפש בהם. אחרי קריאת שם אחד, יש לי \(\frac{N}{2}\) שמות לחפש בהם. אחרי קריאת שני שמות, יש לי \(\frac{N}{4}\); אחרי קריאת שלושה שמות, \(\frac{N}{8}\); ובאופן כללי, אחרי קריאת \(k\) שמות יש לי \(\frac{N}{2^{k}}\) שמות לחפש ביניהם. השאלה היא – מתי יישאר לי לכל היותר שם אחד? או בניסוח אחר, מתי \(\frac{N}{2^{k}}\le1\)? ובניסוח אחר, מתי \(N\le2^{k}\)? וכאן נכנס לתמונה המושג המתמטי של לוגריתם. תזכורת: \(x=\log_{a}b\) ("לוגריתם של \(b\) על בסיס \(a\)) פירושו שמתקיים \(a^{x}=b\), כלומר הלוגריתם של \(b\) על בסיס \(a\) הוא בדיוק המספר שבחזקתו יש להעלות את הבסיס כדי לקבל את \(b\). במדעי המחשב לוגריתם על בסיס 2 הוא נפוץ מאוד, כך שיש לו סימן מקוצר: \(\log_{2}x=\lg x\). מההגדרה שנתתי אפשר לראות ש-\(\lg2^{k}=k\) (למה?) ולכן התשובה לשאלה "מתי \(N\le2^{k}\)" היא כמו התשובה לשאלה "מתי \(\lg N\le k\)?" (שימו לב שאני מניח שהפעלת לוגריתם על שני האגפים משאירה את אי השוויון בעינו ולא הופכת כיוון או משהו דומה – לא אכנס לסיבה כרגע, אבל נסו לחשוב אם אתם מבינים מהי).

אם כן, המסקנה היא שכדי למצוא שם בספר טלפונים עם \(N\) שמות, אני צריך לבדוק רק \(\lg N\) מהשמות. זה מספר הרבה, הרבה יותר קטן מאשר \(N\). כדי לקבל מושג עד כמה, אציין ש-\(\lg1,000\approx10\) (כלומר, הוא בערך 10; למעשה, הוא יותר בכיוון ה-9.965 משהו משהו משהו), וש-\(\lg1,000,000\approx20\) וש-\(\lg1,000,000,000\approx30\) – הבנתם את הרעיון. המסקנה היא שגם בספר טלפונים שמכיל את שמות כל בני האדם שחיו אי פעם, לא תצטרכו לקרוא יותר מאשר, נניח, 50 שמות כדי למצוא את גוליית – וגם בספר שמכיל את כל שמות כל האורגניזמים שאי פעם התקיימו (אני מהמר על כך שהמספר הזה אינו גדול יותר מ-\(10^{30}\), למרות שאולי זה שקר גס) לא תצטרכו לבדוק יותר מ-100 שמות.

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

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

השימוש השני שאני רוצה לדבר עליו, משפט בולצאנו-ויירשטראס, דורש מעט יותר ידע במתמטיקה, ולכן אנסה להציג גרסה שלו שאיננה הכללית ביותר, אך היא דורשת מעט מאוד מושגים קודמים ולא מאבדת את הרעיון הכללי. נניח, אם כן, שאנו מתבוננים בקטע \(\left[0,1\right]\) שעל הישר הממשי, ויש לנו קבוצה \(A\) שמכילה אינסוף נקודות מתוך הקטע הזה. הטענה של בולצאנו-ויירשטראס היא שקיימת ל-\(A\) נקודת הצטברות בתוך הקטע. "נקודת הצטברות" היא נקודה \(x\), כך שבכל סביבה שלה, קטנה ככל שתהיה (אבל עם גודל שאינו אפס) יש נקודה מ-\(A\). במילים אחרות – לכל \(\varepsilon>0\) קיימת נקודה \(a\in x\) שמרחקה מ-\(x\) הוא לכל היותר\(\varepsilon\): \(\left|x-a\right|\le\varepsilon\). המשפט הזה חשוב מאוד כאשר עוסקים בחשבון אינפיניטסימלי; לא אסביר כעת בפירוט מדוע (למתקדמים, רמז: כדי להראות שכל סדרת קושי של מספרים ממשיים מתכנסת, משתמשים בבולצאנו-ויירשטראס, או במשפט שקול לו).

הרעיון הוא זה: נחלק את הקטע \(\left[0,1\right]\) לשני חצאים: \(\left[0,\frac{1}{2}\right]\) ו-\(\left[\frac{1}{2},1\right]\). מכיוון ש-\(A\) היא קבוצה אינסופית, באחד משני החצאים הללו יש מספר אינסופי של נקודות מ-\(A\) (כי אם היה בשניהם מספר סופי, כך גם באיחוד שלהם, שהוא הקטע \(\left[0,1\right]\) כולו). נבחר אחד משני החצאים הללו שבו יש מספר אינסופי של נקודות, וגם אותו נחתוך לשניים – ושוב, נקבל שני קטעים שבאחד מהם מספר אינסופי של נקודות, נבחר אותו ונמשיך הלאה, וכו' וכו' וכו', עד אינסוף.

התוצאה? סדרה של קטעים, שהאורך שלהם הולך וקטן עד אינסוף, וכל אחד מהם מכיל אינסוף נקודות מ-\(A\). תוך התבססות על תכונות המספרים הממשיים אפשר להראות שיש נקודה שמשותפת לכל סדרת הקטעים האינסופית הזו – זו תהיה הנקודה \(x\) שלנו. כעת, כדי להראות שלכל \(\varepsilon\) קיימת \(a\in A\) שקרובה מספיק ל-\(x\) פשוט מסתכלים על קטע מסדרת הקטעים שבנינו, שאורכו הכולל קטן מ-\(\varepsilon\); הוא מכיל אינסוף נקודות מ-\(A\), ולכן בוודאי שהוא מכיל נקודה אחת \(a\) כנדרש.

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

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