אל תנסו לעבור על כל האפשרויות. בין שישה אנשים יש 15 זוגות, ולכל זוג שתי אפשרויות - כלומר 32,768 מסיבות שונות. זה לא מסלול מעשי.

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

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

נניח שאורי מכיר לפחות שלושה מהאורחים. עכשיו שאלו שתי שאלות בלבד: מה קורה אם שניים מהשלושה האלה מכירים זה את זה? ומה קורה אם אף זוג ביניהם אינו מכיר?

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

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

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

שלב ב - שתי אפשרויות, ואין שלישית.

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

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

אפשרות שלישית אין, ולכן הטענה נכונה בכל מסיבה של שישה.

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

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

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

שלושה זרים? קשרי ה"לא מכיר" יוצרים בעצמם מעגל בן חמישה - הכוכב המחומש שבתוך המחומש - ומאותו נימוק גם בו אין משולש.

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

קצת רקע

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

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