משפט רמזי

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

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

אוקיי, ולמה כשיש שישה אנשים זה כן עובד? נתחיל שוב מצ’נדלר. יש לו חמישה חברים שמשתתפים במשחק, ולכן לפחות שלושה מהם שונאים אותו, או שלפחות שלושה מהם אוהבים אותו (הפעם זה לא בדיוק “או” מתמטי - במובהק רק אחת משתי האפשרויות תתרחש) - זו דוגמה נאה לשימוש בעקרון שובך היונים הכללי יותר שאומר שאם מחלקים \( n \) עצמים ל-\( m \) תאים יש בהכרח תא שמכיל לפחות \( \left\lceil \frac{n}{m}\right\rceil \) עצמים (הסימון הזה הוא לערך שלם עליון - המספר הטבעי הקרוב ביותר מלמעלה ל-\( \frac{n}{m} \)).

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

התרגיל הבא בתור הוא להראות שאם יש 9 אנשים, אז מובטח שתהיה שלישיית שונאים או רביעיית אוהבים (או לחילופין, תהיה שלישיית אוהבים או רביעיית שונאים - הסבירו לעצמכם למה זה לא אותו דבר כמו לומר שתהיה רביעיית אוהבים או רביעיית שונאים, מה שדורש כבר 18 אנשים), ונראה לי שהעיקרון כבר ברור. השאלה שאנו שואלים את עצמנו היא - האם זה תמיד עובד? האם לכל \( r,s \) קיים מספר חברים, שנסמן \( R\left(r,s\right) \), כך שבקבוצה עם לפחות \( R\left(r,s\right) \) אנשים מובטחת לנו קבוצה של \( r \) אוהבים או קבוצה של \( s \) שונאים? משפט רמזי אומר שהתשובה חיובית בכך שהוא נותן חסם עליון על \( R\left(r,s\right) \) לכל \( r,s \). מה שדיברנו עליו בתחילת הפוסט הוא בדיוק המקרה של \( R\left(3,3\right) \) וראינו כי \( R\left(3,3\right)=6 \).

ההוכחה של המשפט היא באינדוקציה, ואינדוקציה קצת יותר מחוכמת מהרגיל במובן זה שהיא “דו ממדית”. ראשית שמים לב לכך ש-\( R\left(1,s\right)=R\left(r,1\right)=1 \) תמיד, באופן די טיפשי - קבוצה של אדם בודד היא תמיד קבוצה של אוהבים/שונאים “באופן ריק”. למי שזה נשמע לו לא הגיוני בעליל, תחשבו על זה כך - קבוצת אנשים היא קבוצה של אוהבים או שונאים כל עוד לא הוכח אחרת; כדי להוכיח שקבוצה איננה קבוצת אוהבים צריך להביא זוג שונאים בתוכה, וכדי להוכיח שהיא לא קבוצת שונאים צריך להביא זוג אוהבים בתוכה. בקבוצה בעלת אדם אחד אי אפשר להביא זוג שכזה ממילא, ולכן הקבוצה נחשבת הן לקבוצת אוהבים והן לקבוצת שונאים בו זמנית. כן, זה מוזר וקשה לעיכול למדי למי שטרם נתקל בשיקולים שכאלו, אבל במתמטיקה הם נפוצים למדי ותקינים לחלוטין.

השלב הבא באינדוקציה הוא זה: אנחנו רוצים למצוא חסם עליון על \( R\left(r,s\right) \) בהינתן שאנחנו כבר יודעים חסמים עליונים על \( R\left(r-1,s\right) \) ו-\( R\left(r,s-1\right) \). החסם העליון יהיה פשוט למדי - נוכיח שמתקיים \( R\left(r,s\right)\le R\left(r-1,s\right)+R\left(r,s-1\right) \), וחסל.

אם כן, הבה ונתבונן על קבוצה בעלת \( R\left(r,s\right) \) אנשים. ניקח איש אחד, נקרא לו צ’נדלר, ונחלק את שאר האנשים לשתי קבוצות - חברי צ’נדר ואויבי צ’נדלר. אני מניח שאתם מבינים לאן אני הולך - הפתרון של המקרה הכללי יהיה הכללה פשוטה של המקרה של \( R\left(3,3\right) \). מה שאנחנו רוצים לראות הוא שיש לצ’נדלר מספיק חברים או מספיק אויבים כדי להפעיל אחת מהנחות האינדוקציה.

אם לצ’נדלר יש לפחות \( R\left(r-1,s\right) \) חברים, סיימנו - בקבוצה הזו או שיש \( s \) אויבים (ואז סיימנו) או שיש בה \( r-1 \) חברים ואז יחד עם צ’נדלר נקבל קבוצה של \( r \) חברים וסיימנו. בדומה, אם יש לו לפחות \( R\left(r,s-1\right) \) אויבים סיימנו באותו האופן. למה לא ייתכן שאין לו לא מספיק חברים ולא מספיק אויבים?

כדי לא להתבלבל נכניס עוד כמה סימונים למשחק. \( A \) יהיה מספר החברים של צ’נדלר, \( B \) יהיה מספר האויבים שלנו, וראינו ש-\( A+B+1=R\left(r-1,s\right)+R\left(r,s-1\right) \) (הפלוס 1 הוא כי גם את צ’נדלר סופרים). אז אם \( A<R\left(r-1,s\right) \) וגם \( B<R\left(r,s-1\right) \) זה אומר ש-\( A+B\le R\left(r-1,s\right)+R\left(r,s-1\right)-2 \), כלומר שלא ייתכן ש-\( A+B+1=R\left(r-1,s\right)+R\left(r,s-1\right) \) (למי שעדיין לא רואה את זה, \( a<b \) שקול לאמירה ש-\( a\le b-1 \) אם \( a,b \) הם טבעיים; זו אבחנה מועילה מאוד לעתים).

זה מסיים את ההוכחה; עוד הרחבה לא מסובכת מטפלת במקרה יותר כללי, שבו זוג אנשים יכול להיות יותר מסתם חברים או אויבים, אלא יש \( s \) סוגים שונים אפשריים של קשרים ביניהם - ושוב, אפשר להראות שלכל סדרת מספרים \( r_{1},r_{1},\dots,r_{s} \) קיימת כמות אנשים שהחל ממנה, מובטח שעבור \( i \) כלשהו יש קבוצה של \( r_{i} \) אנשים שהקשרים ביניהם הם רק מסוג \( i \). בניסוח אינטואיטיבי יותר ופחות פורמלי - במבנים גדולים מספיק חייבות לצוץ תבניות מסויימות (זה, על רגל אחת, הרעיון של תורת רמזי; משפט רמזי מטפל בסוג ספציפי של תבניות - בלשון מתמטית, הוא מטפל בתת-גרפים מונוכרומטיים של גרף עם קשתות צבועות).

לסיום, הנה שאלה קטנה וחביבה. ראינו ש-\( R\left(3,3\right)=6 \), כלומר שאם יש 6 אנשים מובטחת לנו שלישיית חברים או שלישיית שונאים, וש-5 אנשים אינם מספיקים. אפשר להראות גם ש-\( R\left(4,4\right)=18 \). אם כן, מהו \( R\left(5,5\right) \)?

באופן מפתיע למדי, ממבט ראשון, התשובה אינה ידועה עד היום. משפט רמזי אמנם נותן חסם עליון פשוט על \( R\left(5,5\right) \), אבל לא עוזר למצוא את הערך המדויק שלו. בדי עמל הצליחו המתמטיקאים להראות ש-\( 43\le R\left(5,5\right)\le49 \), אבל זהו זה. הרי לכם בעיה פתוחה במתמטיקה שתיאוריה הוא אלמנטרי דיו כדי להיות מוסבר בפוסט קצר. אתם עשויים לתהות מה הקושי הגדול כל כך - האם לא ניתן לגייס מחשבים לעבודה ולעשות חיפוש ממצה כלשהו? נאמר, ניקח את כל הקבוצות האפשריות של יחסי אהבה/שנאה על 43 אנשים ונבדוק לכל אחת… כן, ובכן, תשכחו מזה. אם יש לנו 43 אנשים אז יש לנו \( \frac{43\cdot42}{2}=903 \) זוגות בסך הכל. לכל אחד מהם אנחנו יכולים לבחור, באופן בלתי תלוי באחרים, ביחס אהבה/שנאה, כך שיש לנו כבר \( 2^{903} \) קבוצות אפשריות. המספר \( 2^{903} \) הוא גדול. ממש, ממש גדול. כמה גדול? גדול להחריד גם בהשוואה למספרים הגדולים שדיברתי עליהם בפוסט הזה. אז חיפוש ממצה הוא כיוון אבוד לחלוטין; הכרחי יהיה לעשות הרבה עבודת הכנה מתמטית תיאורטית כדי שתהיה תקווה להריץ איזה חיפוש מחשב שגם יתן את התוצאה הנכונה. ונניח שנצליח, האתגר הבא יהיה מציאת \( R\left(6,6\right) \). כדי להבין עד כמה הקפיצה הזו בקושי בין \( R\left(5,5\right) \) ו-\( R\left(6,6\right) \) תהיה משמעותית כדאי לתת את הבמה לרגע לג’ואל ספנסר שמצטט את ארדש:

Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5,5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6,6). In that case, he believes, we should attempt to destroy the aliens.

הציטוט הנפלא הזה לבדו שווה את כל הפוסט.