השערת החלוקה הלא ידידותית

הנה משפט קל וחביב. אני ממליץ לנסות להוכיח אותו עצמאית לפני שתקראו את ההוכחה.

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

חלוקה כזאת נקראת “לא ידידותית”.

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

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

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

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

והיכן כאן ההשערה? גם זה פשוט: המקרה האינסופי.

השערה – משפט 1 נכון גם כאשר יש אינסוף אנשים.

הדרישה במקרה האינסופי היא שאם מישהו חבר של מספר סופי \({n}\) של אנשים בצד שלו, הוא צריך להיות חבר של לפחות \({n}\) אנשים בצד האחר, ואם הוא חבר של אינסוף אנשים בצד שלו הוא גם חבר של אינסוף אנשים בצד האחר.

ההשערה הזאת, שנוסחה בידי מתמטיקאי אמריקני בשם \({Cowan}\), פתוחה מאז שנות ה-\({70}\) של המאה העשרים, כלומר יותר מ-\({40}\) שנים, ורבים וטובים ניסו בה את כוחם. אתם מוזמנים!

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

3 תגובות על השערת החלוקה הלא ידידותית