משפט רמזי

משפט 1 בין כל שישה אנשים קיימים שלושה שכולם חברים איש של רעהו, או שלושה שכולם לא חברים זה של זה.

(זהו “או” מתמטי – אפשר גם וגם).

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

ההבחנה הזאת היא מקרה פרטי של משפט שהוכח בשנות העשרים של המאה ה-\({20}\) על ידי מתמטיקאי אנגלי בשם רמזי \({(Frank~~Ramsey,~~ 1903-1930)}\). רמזי היה גאון רב תחומי, ומותו בגיל צעיר ממחלת כבד היה אובדן גדול למדע. הוא תרם ללוגיקה המתמטית ולתורת הכלכלה, ומצא גם זמן לעסוק בפילוסופיה. הוא אבי תורה שאומרת שמושג ה”אמת” מיותר – לומר שהמשפט “החתול שלי שחור” אמיתי לא אומר שום דבר נוסף על כך שהחתול שלי שחור. אפשר להסתדר בלי מושג ה”אמת”. לא צריך להתייחס ברצינות לתורה הזאת (להגיד שהמשפט החתול שלי שחור אמיתי מדבר על המשפט, ולא על החתול, וצריך לומר משהו גם על משפטים, לא רק על חתולים), אבל בואו נניח לפילוסופים לעסוק במלאכתם, ונחזור לענייננו – הצד המתמטי של מחקרו של רמזי.

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

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

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

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

ramzi

בצביעה הזאת של כל הקווים בין  \({5}\) נקודות אין משולש אדום וגם אין משולש כחול. המסקנה היא ש- \({R(3,3)>5}\)

מדוע עם שישה אנשים זה כן עובד? בואו נעשה זאת שוב בגרף – “אדום” ו”כחול” הם מונחים נוחים לתפיסה. ניקח נקודה, נקרא לה א’. נניח תחילה שבין \({5}\) הנקודות האחרות יש \({3}\) שהיא מחוברת אליהן באדום, נאמר ב’,ג’ ו-ד’. אם יש בין ב’,ג’ ו-ד’ זוג שמחובר באדום הרי יחד עם א’ נוצר משולש אדום.

לכן מותר להניח שכל זוג נקודות בין ב’, ג’ ו-ג’ מחובר בקו בצבע כחול. אבל אז יש לנו משולש כחול – ושוב הצלחנו.

נימוק דומה עובד אם א’ מחוברת לשלוש נקודות בכחול.

ומה קורה אם מ-א’ יוצאים לכל היותר שני קווים אדומים ושני קווים כחולים? ובכן, זה לא ייתכן. במקרה כזה היו יוצאים מ-א’ יחד לכל היותר \({2+2=4}\) קווים – אבל יוצאים ממנה \({5}\) קווים!

בעצם, השתמשנו כאן בעקרון שובך היונים: אם צובעים \({5}\) עצמים באדום ובכחול, נמצא לפחות \({3}\) עצמים שצבועים באותו צבע.

התרגיל הבא בתור הוא להראות שאם יש \({9}\) אנשים, אז מובטח שתהיה שלישיית שונאים או רביעיית אוהבים (או לחילופין, תהיה שלישיית אוהבים או רביעיית שונאים – הסבירו לעצמכם למה זה לא אותו דבר כמו לומר שתהיה רביעיית אוהבים או רביעיית שונאים, מה שדורש כבר \({18}\) אנשים).

הנה התחלה של ההוכחה – שוב בלשון של גרף עם קווים צבועים באדום ובכחול. כאמור, צובעים את כל הקווים בין \({9}\) נקודות באדום ובכחול, ורוצים להראות שאו שיש משולש אדום, או שיש \({4}\) נקודות שכל \({6}\) הצלעות ביניהן צבועות בכחול.

ניקח בנקודה כלשהי. כמקרה ראשון, נסתכל במקרה שבו יוצאים מ-א’ (לפחות) \({6}\) קווים כחולים, כלומר יש \({6}\) נקודות שמחוברות ל-א’ בכחול. על פי משפט 1, בין \({6}\) הנקודות האלה אפשר למצוא משולש אדום או משולש כחול. אם יש משולש אדום – ניצחנו, הרי רצינו להראות יש משולש אדום. אם יש משולש כחול, אז יחד עם א’ מתקבלות \({4}\) נקודות שכולן מחוברות בכחול.

מקרה שני הוא שמ-א’ יוצאים \({4}\) קווים אדומים. אם בין ארבע הנקודות המחוברות ל-א’ באדום יש צלע אדומה – קיבלנו משולש אדום. אם כל הצלעות בין \({4}\) הנקודות האלה כחולות, קיבלנו \({4}\) נקודות שכל הצלעות ביניהן כחולות, ושוב ניצחנו.

פתרנו שני מקרים. האם הם מכסים את כל האפשרויות? לאו דווקא. מ-א’ יוצאים \({8}\) קווים. ייתכן בהחלט ש-\({3}\) מהם אדומים, ו-\({5}\) כחולים. אבל זוהי האפשרות היחידה שבה אף אחד מן המקרים האמורים לא מתקיים. וכאן באה הבחנה: זה חייב לקרות בכל נקודה. הרי א’ היא נקודה שרירותית. לכל נקודה, אם יוצאים ממנה \({4}\) קווים אדומים או \({6}\) קווים כחולים המשפט הוכח.

וזה כבר לא ייתכן. מדוע? אם מכל אחת מ-\({9}\) הנקודות יוצאים \({3}\) קווים אדומים, אז מספר הקצוות של קווים אדומים הוא \({9 \times 3}\), כלומר \({27}\). זה לא אפשרי בעליל: לכל קו (כמו לכל מקל) יש שני קצוות, ולכן מספר הקצוות של הקווים האדומים צריך להיות זוגי.

משפט רמזי הוא הכללה של שתי הטענות האלה.

משפט 2 לכל \({r}\) ו-\({s}\) קיים מספר \({N}\) שבהינתן \({N}\) אנשים, יש ביניהם \({r}\) אנשים שכולם חברים זה של זה, או קבוצה של \({s}\) אנשיעם שכולם אינם חברים זה של זה.

לאותו \({N}\) שבמשפט, אם נתונים יותר מ-\({N}\) אנשים ברור שהתנאי מתקיים (אומרים שהתנאי “מונוטוני ב-\({N}\)”) – הסבירו לעצמכם מדוע (למשל, מדוע משפט 1 נכון ל-\({7}\) אנשים). לכן מעניין לשאול על הערך הקטן ביותר של \({N}\) שמקיים את התנאי. הוא מסומן ב-\({R\left(r,s\right)}\) (עוד יותר ממשפט שקרוי על שמך, מכובד שיהיה סימון שנבחר על פי שמך!). בסימון הזה, משפט 1, בצירוף הדוגמה שהראתה ש-\({5}\) אנשים לא מספיקים, אומרים ש-\({R\left(3,3\right)=6}\).

תרגיל 1 הראו ש-\({R(3,4)=9}\).

(רמז: הנימוק שאמרנו לעיל מראה רק ש-\({R(3,4)\le 9}\). הראו ש-\({R(3,4)>8}\) – לשם כך דרושה דוגמה. של מה? ועוד רמז: בניות מוצלחות הן פעמים רבות סימטריות).

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

ראשית שמים לב לכך שלכל \({r}\) ו-\({s}\) מתקיים \({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(r-1,s\right)}\) חברים, סיימנו – בקבוצה הזו או שיש \({s}\) אויבים (ואז סיימנו) או שיש בה \({r-1}\) חברים ואז יחד עם א’ נקבל קבוצה של \({r}\) חברים וסיימנו. בדומה, אם יש לו לפחות \({R\left(r,s-1\right)}\) אויבים סיימנו באותו האופן. למה לא ייתכן שאין לו לא מספיק חברים ולא מספיק אויבים?

כדי לא להתבלבל נכניס עוד כמה סימונים למשחק. \({A}\) יהיה מספר החברים של א’, \({B}\) יהיה מספר האויבים שלו, וראינו ש-

\(\displaystyle 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}\) נקודות, ונבדוק לכל אחת אם יש בה \({5}\) איברים שכל הקווים המחברים נקודות בתוכה הם מאותו צבע. ובכן, קל יותר לומר זאת מאשר לעשות. אפילו למחשב. יש \({903}\) קווים בין \({43}\) נקודות, ולכל קו יש שתי אפשרויות צביעה, ולכן מספר הצביעות האפשריות הוא \({\frac{43\cdot42}{2}=903}\). זהו מספר מאוד גדול. לשם השוואה, מספר האטומים ביקום מוערך ב-\({2^{250}}\). פירוש הדבר הוא שחיפוש ממצה אינו מעשי וגם לא יהיה מעשי בעתיד הנראה לעין. הכרחי יהיה לעשות הרבה עבודת הכנה מתמטית תיאורטית כדי שתהיה תקווה להריץ איזה חיפוש מחשב שגם יתן את התוצאה הנכונה. ואם נצליח, זו תהיה רק תחילת הדרך. מציאת \({R\left(6,6\right)}\) תהיה בהרבה סדרי גודל קשה יותר.