High School Coalitions

קואליציות בתיכון

נוגה אלון, אוניברסיטת פרינסטון ואוניברסיטת תל אביב

הבעיה

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

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

תאוריה 1.1  

1. ל k ≤ 2 וכל מספר שלם r > 1, כל סט R בעלת גודל r יכולה ליצור קואליציה מוצלחת.
2. לכל k ≥ 3 ולכל r > 1 אין סט בגודל r שיכולה ליצור קואליציה מוצלחת.  

2- הוכחות

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

טענה: 

נניח ש n ≥ 5 , N = {1,2,…,n}, R = {1,2,…,5},ותהא S1,…,S5 תת קבוצות של N , כאשר כל אחד בגודל 3 ,כך ש i̸∈Si לכל 1≤i≤5. אז יהיו תתי קבוצות Sj ⊂N , עבור 5≤j≤n וישנה חלוקה P (S1, . . . , Sn) של N לשני קבוצות זרות N1, N2 , אשר מקיימת (1) כך ש R חותך את N1 ו N2.  

הוכחה :

צבע באופן רנדומלי את האלמנטים של  N   בכחול ואדום , שבו כל i ∈ N באופן רנדומלי ובלתי תלוי הוא אדום בהסתברות של ½ וכחול בהסתברות של ½. ההסתברות שלכל האיברים של R יהיה את אותו הצבע הוא 1/16. לכל נקודה קבועה i ≤ 5 , ההסתברות שהצבע של i שונה מהצבע של כל האלמנטים בSi היא  1/8. לכן, עם הסתברות של לפחות   1 − 1/16 − 5/8 > 0  אין אף אחד מהאירועים האלה שמתרחשים. מכאן נובע שישנו צביעה שבו R מכיל אלמנטים אדומים וכחולים, ושלכל i ∈ R יש לפחות חבר קבוצה אחד עם אותו צבע כמו של i. תקן את הצביעה הזאת. מבלי איבוד ההכללה 1 צבועה באדום ו 2 צבועה בכחול. נניח ש N1  הוא הסט של כל האלמנטים הצבועים באדום ושN2  הוא הסט של כל האלמנטים הצבועים בכחול. לכל j∈N1−R,   Sj תכיל 1 ולכל  ,j∈N2−R Sj תכיל 2. קל לראות שהחלוקה N = N1 ∪ N2 מקיימת (1) אבל R חותך את N1 ואת N2 , עד כאן ההוכחה.