בעיית המסיבה של רמזי - למה בכל מפגש של שישה אנשים תמיד יש שלישייה של מכרים או שלישייה של זרים

קבוצת חברים יושבים יחד סביב מדורה בשטח פתוח

צילום: Phil Coffman, Unsplash דרך Wikimedia Commons (CC0)

נכנסים לחדר שישה אנשים. כל שני אנשים בחדר נמצאים באחד משני מצבים בלבד: או שהם מכירים זה את זה, או שהם זרים גמורים. אין מצב ביניים, וההיכרות היא תמיד הדדית.

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

ובכל זאת, הטענה הבאה נכונה תמיד, לכל חבורה אפשרית של שישה:

יש בחדר שלושה אנשים שכולם מכירים זה את זה, או שלושה אנשים שאף אחד מהם אינו מכיר את השניים האחרים.

וכשמנסים את אותו הדבר עם חמישה אנשים בלבד - הטענה כבר אינה נכונה.

השאלה: איך מוכיחים שאצל שישה זה תמיד קורה - ואיך בונים דוגמה נגדית לחמישה?

+ - רמז דק Click to collapse

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

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

מה מבטיח לנו עקרון שובך היונים על חמישה דברים שמחולקים לשתי קבוצות?

+ - רמז עבה Click to collapse

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

נניח שאלה שלושה שא מכיר. עכשיו הסתכלו רק עליהם, ושאלו: מה קורה אם שניים מתוכם מכירים זה את זה? ומה קורה אם אף שניים מהם אינם מכירים?

+ - פתרון Click to collapse

ההוכחה - בשני צעדים בלבד

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

צעד שני: בדיקת השלישייה. נניח בלי הגבלת הכלליות שיש שלושה שא מכיר, ונקרא להם ב, ג, ד.

אם שניים כלשהם מתוך ב, ג, ד מכירים זה את זה - נניח ב וג - אז ב, ג וא הם שלושה שכולם מכירים זה את זה, ומצאנו את מה שחיפשנו.

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

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

ולמה חמישה לא מספיקים

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

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

מי עומד מאחורי זה

החידה היא המקרה הפרטי המפורסם ביותר של משפט שניסח המתמטיקאי והפילוסוף הבריטי פרנק רמזי במאמר משנת 1930, שנה לפני מותו בגיל 26.

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

וכמה קשה זה נעשה? R(4,4) שווה 18, וכבר את R(5,5) איש אינו יודע לחשב עד היום. פאול ארדש נהג לומר שאם יצורים מחוזרים ידרשו מאיתנו את R(5,5) - כדאי שנרתום את כל מחשבי העולם; ואם ידרשו את R(6,6), עדיף פשוט לתקוף אותם.