סדרות ביטי ומלכות שחמט

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

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

בואו נניח שהמשבצת השמאלית-תחתונה היא \( \left(0,0\right) \) כי אז הניתוח יצא יפה יותר. בנוסף, בואו נסכים גם ש-\( \left(0,0\right) \) נחשבת למשבצת של הפסד (אפשר להגדיר ש”המפסיד הוא מי שכבר לא יכול לזוז” ואז זה ברור יותר). עכשיו בואו וננסה להבין אילו משבצות הן של ניצחון: ברור ש-\( \left(0,1\right),\left(1,0\right),\left(1,1\right) \) כולן משבצות מנצחות, כי מכולן אפשר להגיע בצעד אחד אל \( \left(0,0\right) \). מה עם \( \left(1,2\right) \)? ובכן, זו משבצת של הפסד, כי אם זזים בשורה אפשר להגיע רק אל \( \left(1,1\right) \) או \( \left(1,0\right) \) שמבטיחות ניצחון ליריב; ואם זזים בעמודה מגיעים אל \( \left(0,2\right) \) שגם היא משבצת ניצחון. בגלל הסימטריה של המשחק גם \( \left(2,1\right) \) היא משבצת הפסד. בגלל אותה סימטריה נרצה למצוא רק משבצות הפסד \( \left(i,j\right) \) שבהן \( i<j \). משבצות שבהן \( i>j \) הן לא מעניינות כי כדי להבין מה קורה בהן מספיק להבין מה קורה ב-\( \left(j,i\right) \); ואם \( i=j \) זה הכי לא מעניין כי ממשבצת כזו אפשר להגיע (באלכסון) ישר אל \( \left(0,0\right) \) ולכן זו תמיד משבצת נצחון.

עכשיו \( \left(2,3\right) \) היא משבצת ניצחון, כי ממנה אפשר לזוז אל \( \left(1,2\right) \) שתבטיח שהשחקן השני יפסיד. ומה עם \( \left(2,4\right) \)? אותו סיפור. בעצם, כל משבצת בשורה \( 2 \) עם עמודה שגדולה מ-1, מובטח לה שתהיה משבצת ניצחון. לכן בשורה 2 לא נמצא אף משבצת הפסד “מעניינת” (יש את \( \left(2,1\right) \) אבל היא לא מעניינת כי הקואורדינטה הראשונה גדולה מהשניה). לכן נעבור לשורה 3. המשבצת המעניינת הראשונה כאן היא \( \left(3,4\right) \); ממנה אפשר להגיע בתנועה באלכסון אל \( \left(1,2\right) \) שהיא משבצת הפסד, ולכן \( \left(3,4\right) \) היא משבצת נצחון. לעומת זאת מ-\( \left(3,5\right) \) כל צעד שנעשה יוביל אותנו למשבצת נצחון, ולכן \( \left(3,5\right) \) היא משבצת הפסד. כאן אפשר לעצור לרגע ולנסות ולראות את התמונה הגדולה.

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

העובדה ש-\( \left(1,2\right) \) היא משבצת הפסד אומרת שכל משבצת מהצורה \( \left(i,i+1\right) \), כאשר \( i>1 \), לא יכולה להיות משבצת הפסד. בדומה, \( \left(3,5\right) \) גורמת לכך ש-\( \left(i,i+2\right) \) לא תהיה משבצת הפסד עבור \( i>3 \). מכאן כבר אפשר לנחש את האופן הכללי שבו בונים את סדרת משבצות ההפסד: בכל צעד בוחרים את מספר השורה הקטן ביותר שטרם הופיעה לא כשורה ולא כעמודה בתוך משבצת הפסד קודם (למשל, מ-\( \left(1,2\right) \) עברנו לטפל בשורה \( 3 \) ולא בשורה 2 כי שורה 2 כבר טופלה בכך ש-\( \left(1,2\right) \) מראה לנו שגם \( \left(2,1\right) \) היא משבצת הפסד), ולמספר השורה הזה מצרפים את מספר העמודה שגדול ממנו ב-\( k \), כאשר \( k \) הוא מספר משבצות ההפסד שמצאנו עד כה.

אם תריצות את ה”אלגוריתם” הזה, תראו שאתם מקבלים את הסדרה הבאה:

\( \left(0,0\right),\left(1,2\right),\left(3,5\right),\left(4,7\right),\left(6,10\right),\left(8,13\right),\left(9,15\right),\left(11,18\right),\dots \).

האיבר הראשון הוא חריג אז בואו נשכח ממנו ונשים לב לתכונה המעניינת של יתר האיברים בסדרה. אפשר לפרק את הקואורדינטות למרכיביהן ולקבל שתי סדרות - סדרת אינדקסי השורות וסדרת אינדקסי העמודות, שאסמן כ-\( a_{n},b_{n} \) - שנראות כך:

\( 1,3,4,6,8,9,11,\dots \)

\( 2,5,7,10,13,15,18,\dots \)

האם יש חוקיות כאן? במבט ראשון קצת קשה לראות כזו, אבל שני דברים צצים לעין כמעט מייד - ראשית, ששתי הסדרות הן זרות - אין איבר ששייך לשתיהן. שנית, הן מכסות את כל הטבעיים, כלומר כל מספר טבעי ייכנס אליהן. זה לא באמת מפתיע אם חושבים על אופן הבניה שלהן: הכלל שלפיו בוחרים את המספר החדש להכניס לסדרה הראשונה הוא “בחר את המספר הקטן ביותר שטרם הופיע”, מה שמבטיח שנתפוס את כולם מתישהו; קצת יותר טריקי להראות שאין איבר שמופיע בשני הסדרות גם יחד, אבל ההגיון פה גם די ברור - על פי הבניה, \( a_{n}<b_{n} \) תמיד, ולכן אם יש שוויון הוא של \( a_{n}=b_{m} \) עם \( m<n \), אבל \( a_{n} \) נבחר רק מקרב מספרים שלא הופיעו עד כה, ומכיוון ש-\( b_{m} \) כבר הופיע לפני השלב \( n \), אין סיכוי ש-\( a_{n}=b_{m} \).

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

סדרת ביטי של מספר אי רציונלי \( a \) היא פשוט סדרת הכפולות שלו, כשהיא מעוגלת למטה. כלומר, זו הסדרה \( \left\lfloor a\right\rfloor ,\left\lfloor 2a\right\rfloor ,\left\lfloor 3a\right\rfloor ,\dots \), כשהקווים מסמנים כאן את פונקציית הערך השלם התחתון - \( \left\lfloor x\right\rfloor \) הוא המספר הטבעי הגדול ביותר שקטן או שווה ל-\( x \). אפשר כמובן לדבר על סדרה דומה גם עבור \( a \) רציונלי, אבל אז לא יתקיים המשפט המעניין שאני רוצה לדבר עליו כאן - אם \( a \) אי רציונלי אז קיים אי רציונלי אחר \( b \) כך שסדרות הביטי שמתאימות ל-\( a,b \) - הבה ונסמן אותן ב-\( a_{n},b_{n} \) - הן זרות ומשלימות (אין להן איבר משותף, והן מכסות את כל הטבעיים). בואו ונוכיח את המשפט הזה.

ראשית, מי אותו \( b \) מסתורי יכול להיות? הנה שיקול יפה שנותן לנו רמז: סדרת הביטי שמתאימה ל-\( a \) תופסת בערך \( \frac{1}{a} \) מבין כל הטבעיים. בצורה קצת יותר פורמלית אפשר לדבר על \( \lim_{n\to\infty}\frac{\left|\left\{ a_{1},\dots,a_{n}\right\} \cap\left\{ 1,\dots,n\right\} \right|}{n} \) ולהראות שהוא שווה ממש ל-\( \frac{1}{a} \). אם כך, כדי ש-\( b_{n} \) תהיה סדרה משלימה, היא צריכה לתפוס את כל יתר הטבעיים, כלומר צריך שיתקיים \( \frac{1}{a}+\frac{1}{b}=1 \). קצת חילוץ אלגברי ומקבלים \( b=\frac{a}{a-1} \).

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

הרעיון הוא כזה: דמיינו אצטדיון בצורת מעגל, שהיקפו הוא בדיוק 1. כעת, מהנקודה הצפונית ביותר באצטדיון, שנסמן בתור ה”ראשית” \( O \), יוצאים שני רצים - אליס ובוב - כל אחד לכיוון אחר (אחד עם כיוון השעון והשני נגד כיוון השעון). מהירות אליס היא \( \frac{1}{a} \) (כלומר, מרחק של \( \frac{1}{a} \) אצטדיון בכל יחידת זמן) ומהירות בוב היא \( \frac{1}{b} \) - כלומר, הם משלימים סיבוב סביב האצטדיון בזמנים \( a,b \) בהתאמה, ובגלל ש-\( \frac{1}{a}+\frac{1}{b}=1 \) הם נפגשים בדיוק כל יחידת זמן. כעת התעלול פשוט: כאשר אליס עוברת ב-\( O \) היא צועקת את מספר הפעמים שהיא חלפה עד כה על פני בוב; וכאשר בוב חולף ב-\( O \) הוא צועק את מספר הפעמים שהוא חלף עד כה על פני אליס.

מה שאני טוען הוא שסדרת המספרים שאליס צועקת היא \( a_{n} \) וסדרת המספרים שבוב צועק היא \( b_{n} \). למה? ובכן, זה פשוט למדי: אליס פוגשת את בוב בזמנים\( 1,2,3,\dots \), ולכן כשהיא חולף על פני בוב בזמן \( n \) היא ראתה אותו עד כה בדיוק \( n \) פעמים. בנוסף, אליס חולפת על פני הראשית בזמנים \( a,2a,3a,\dots \) וכדומה; מה מספר הפעמים שבהם אליס ראתה את בוב כשהיא מגיעה לראשית בזמן \( na \)? ובכן, זה חייב להיות המספר הטבעי הגדול ביותר שקטן או שווה ל-\( na \) - זה הזמן האחרון שבו אליס חלפה על פני בוב. לכן הסדרה של המספרים שאליס צועקת היא \( \left\lfloor a\right\rfloor ,\left\lfloor 2a\right\rfloor ,\left\lfloor 3a\right\rfloor ,\dots \) והסדרה של בוב היא \( \left\lfloor b\right\rfloor ,\left\lfloor 2b\right\rfloor ,\left\lfloor 3b\right\rfloor ,\dots \).

אבל עכשיו, למה אלו סדרות זרות ומשלימות? אנחנו מקבלים את זה כמעט בחינם מהמודל שלנו. האבחנה המרכזית פה היא שאליס ובוב לא יחזרו אף פעם להיות בו זמנית ב-\( O \), וזה נובע ישירות מכך ש-\( a,b \) אי רציונליים; אם \( a \) היה רציונלי אז גם \( b=\frac{a}{a-1} \) היה רציונלי, ועל ידי מכנה משותף היינו מגלים מייד מתי שניהם יחזרו להיות יחד ב-\( O \) (בדקו זאת!) והיינו מקבלים שהם צועקים את אותו המספר גם יחד והייתה התנגשות של הסדרות.

אוקיי, אז אם \( a,b \) רציונליים אליס ובוב לא נפגשים בראשית, אבל למה אם הם אי רציונליים מובטח שהם לא ייפגשו בראשית? פגישה כזו פירושה \( na=mb \) עבור \( n,m \) טבעיים, כלומר ש-\( a=\frac{m}{n}b \); ומכיוון ש-\( \frac{1}{a}+\frac{1}{b}=1 \) נקבל ש-\( \left(\frac{n}{m}+1\right)\frac{1}{b}=1 \), כלומר \( b=\frac{n+m}{m} \) שהוא מספר רציונלי לגמרי (ובדומה \( a=\frac{n+m}{n} \)). זו סיטואציה מאוד נפוצה עם מספרים אי רציונליים - תנו להם לרוץ סביב אצטדיון עם אורך רציונלי ותמדדו אותם בנקודות זמן רציונליות, והם אף פעם לא יחזרו לאותו מקום.

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

בואו נחזור עכשיו למשחק המלכה. קיבלנו בו שתי סדרות זרות ומשלימות, של קואורדינטות ה-\( x \) של משבצות הפסד, וקואורדינטות ה-\( y \) שלהן. אני טוען שאלו סדרות ביטי, אבל עבור אילו מספרים \( a,b \)?

ובכן, כאן יש לנו נתון שאפשר להיעזר בו - העובדה ש-\( b_{n}=a_{n}+n \) (זוכרים? זה היה אחד מהקריטריונים שהכתיבו את אופן בניית הסדרה). כלומר, \( \left\lfloor nb\right\rfloor =\left\lfloor na\right\rfloor +n \) לכל \( n \). כדי שזה יקרה, צריך שיתקיים \( b=a+1 \) (הוכיחו את זה לעצמכם!). נוסיף לכך את העובדה ש-\( b=\frac{a}{a-1} \) ונקבל \( a=\left(a+1\right)\left(a-1\right) \). פתיחת סוגריים והעברת אגפים תיתן לנו \( a^{2}-a-1=0 \), והפתרונות למשוואה הזו הם \( \frac{1\pm\sqrt{5}}{2} \), כשאנחנו רוצים מראש את הפתרון החיובי מבין השניים. כלומר, \( a=\frac{1+\sqrt{5}}{2} \). את המספר הזה אתם מכירים כנראה יותר בסימון \( \phi \) ובשם “יחס הזהב”; הרי לכם מקום נחמד שבו הוא צץ מעצמו. מכיוון שיחס הזהב מקיים \( \phi^{2}=\phi+1 \) הרי ש-\( b \) מיודענו הוא \( \phi^{2} \) במקרה זה. במילים אחרות, סדרות הביטי של \( \phi,\phi^{2} \) הן בדיוק מה שנותן את מצבי ההפסד במשחק המלכה. יש אמנם הכללות ודברים נוספים שאפשר לומר בעניין אבל זה נראה לי כמו מקום טוב לעצור בו.