High School Coalitions
קואליציות בתיכון נוגה אלון, אוניברסיטת פרינסטון ואוניברסיטת תל אביב הבעיה פרופסור שי מורן הציג בפניי לפני כמה ימים, שאלה שהועלתה על ידי אישה בשם רותי שחם, לקבוצת פייסבוק המתמקדת בנושאים מתמטיים. היא כתבה שהבן שלה שסיים לא מזמן את בית הספר היסודי, עולה עתה לתיכון. כאשר עוברים לתיכון מבית הספר היסודי על כל תלמיד לבחור שלושה חברים שאיתם ירצה להיות באותה כיתה, והחלוקה לכיתות מתבצעת בצורה כזאת שלכל תלמיד יהיה לפחות את אחד משלושת החברים שמנה. רותי כותבת בהמשך הפוסט שהבן שלה שמע מחמישה מחבריו ללימודים, שהם יכולים לבצע את הבחירות שלהם כך שכל החמישה ישובצו באותה כיתה. רותי ניסתה על ידי דף ועיפרון, לבדוק האם היא תוכל או לא להגיע לפתרון הבעיה, אבל היא חוששת שפתרון הבעיה בלתי אפשרית . היא שואלת אם זה אכן המקרה, ואם כן האם קבוצה גדולה יותר של ילדים תוכל ליצור קואליציה (שותפות) שתוודא את שיבוצם לאותה כיתה באופן וודאי. במסמך הקצר הזה אני אראה שרותי אכן צודקת, אין שום קואליציה של חמישה ילדים שתוכל להבטיח שכולם ישובצו באותה הכיתה. ויותר מכך אין קואליציה בכל גודל אחר שתוכל להבטיח את שיבוצם באותה הכיתה. באופן משעשע, הנושא קשור לבעיות ידועות ותוצאות בקומבינטוריקה ותורת הגרפים תאוריה 1.1 ל k ≤ 2 וכל מספר שלם r > 1, כל סט R בעלת גודל r יכולה ליצור קואליציה מוצלחת. לכל k ≥ 3 ולכל r > 1 אין סט בגודל r שיכולה ליצור קואליציה מוצלחת. 2- הוכחות לפני שאציג את ההוכחה הכללית, הנה טיעון קצר שמראה שבעבור k = 3 קואליציה מוצלחת בגודל 5 אינה אפשרית.