פורטל:מתמטיקה/חידה/16/פתרון בונוס

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

ההוכחה

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

בסיס האינדוקציה

הכיתה הקטנה ביותר הרלוונטית היא כיתה בת 4 תלמידים. בכיתה כזאת כל תלמיד חייב לרשום את שלושת האחרים. לכן, את הכיתה הזאת ניתן לפצל לשתי כיתות בנות 2 תלמידים כל אחת.

מעבר אינדוקציה

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

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

נזדקק למספר למות:

אין שני קודקודים בגרף המצביעים זה על זה.

למה 1: אין בכיתה שני תלמידים שכל אחד מהם רשם את השני.

הוכחה
נניח שיש 2 תלמידים כאלה (נקרא להם א' וב'). בכזה מקרה ניתן לפצל את הכיתה בקלות: שמים את א' וב' בכיתה אחת (נקרא לה $A$ ) ואת כל השאר בכתה אחרת (נקרא לה $B$ ). הפיצול הזה הוא תקין כי: אחת הבחירות של א' (תלמיד ב') נמצאת בכיתה שלו (כיתה $A$ ) אחת הבחירות של ב' (תלמיד א') נמצאת בכיתה שלו (כיתה $A$ ) לפי עיקרון שובך היונים, כל תלמיד שנמצא בכיתה $B$ בחר לפחות תלמיד אחד שאינו בכיתה $A$ (במילים אחרות תלמיד שנמצא בכיתה $B$ ).

אל כל קודקוד בגרף (בתמונה צבוע באדום) מצביע קודקוד אחר.

למה 2: כל תלמיד נרשם לפחות על ידי תלמיד אחד אחר.

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

כל חץ בגרף (בתמונה צבוע באדום) נמצא בתוך משולש כמו בתמונה.

למה 3: אם תלמיד אחד רשם תלמיד אחר, אז קיים תלמיד שלישי שרשם את שניהם.

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

כל קודוקוד בגרף (בתמונה צבוע באדום) נמצא בתוך תת-גרף כמו בתמונה.

למה 4: עבור כל תלמיד קיים מספר $n\geq 3$ ו- $n$ תלמידים שבחרו בו כך שניתן להושיבם במעגל כך שכל אחד בחר בתלמיד שלימינו.

הוכחה
נקבע תלמיד ונקרא לו א'. נסמן ב - $A$ את קבוצת התלמידים שרשמו אותו. לפי למה 2 קבוצה זאת איננה ריקה. לפי למה 3, עבור כל תלמיד ב - $A$ קיים תלמיד אחר ב - $A$ שרשם אותו. נקח תלמיד ב - $A$ נעמיד אותו ונקרא לו $x_{1}$ . נקח תלמיד אחר ב - $A$ שרשם את $x_{1}$ נעמיד אותו לשמאלו של $x_{1}$ ונקרא לו $x_{2}$ , נמשיך הלאה כך שבכל שלב אנו בוחרים תלמיד ב - $A$ שעדיין יושב ובחר בתלמיד האחרון שהעמדנו. בשלב מסוים לא נוכל לעשות זאת כי התלמיד ב - $A$ שבחר בתלמיד האחרון שהעמדנו כבר עומד בשורה. נשתמש בתלמיד זה כדי לסגור מעגל כפי שנדרש. לפי למה 1 המעגל חייב להיות לפחות באורך 3.

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

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

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

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

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

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

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

הוכחה

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

טענה: יש תלמיד אחד מבין ב', ג' וד' שנבחר על ידי השניים האחרים.

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

כעת בה"כ נניח שב' נבחר על ידי ג' וד'. אם כך, שלושת התלמידים שבחרו בב' הם א', ג' וד'. לפי למה 5, אפשר להושיב אותם במעגל כך שכל אחד בחר את זה שלימינו. זה אומר שא' נבחר על ידי אחד מהשניים האחרים, זה, יחד עם למה 1, סותר את העובדה שא' בחר את ג' וד'.

למה 8: קיימות 2 קבוצות זרות לא ריקות של תלמידים $A$ ו - $B$ כך שכל תלמיד מכל אחת מהקבוצות בחר לפחות תלמיד אחד בקבוצה שלו.

הוכחה
נבחר תלמיד. נסמן ב - $A$ את קבוצת התלמידים שהוא בחר וב - $B$ את קבוצת התלמידים שבחרו אותו. לפי למה 1 קבוצות אלו זרות. לפי למה 2 הקבוצה $B$ איננה ריקה. לפי תנאי הבעיה הקבוצה $A$ איננה ריקה. לפי למה 5 כל תלמיד ב - $B$ בחר לפחות תלמיד אחד ב - $B$ . לפי למה 7 כל תלמיד ב - $A$ בחר לפחות תלמיד אחד ב - $A$ .

כעת נראה איך מפצלים את הכיתה: נבחר $A$ ו - $B$ כמו בלמה האחרונה. אנחנו נוסיף תלמידים שלב אחר שלב ל- $A$ ול - $B$ עד אשר יתקבל פיצול של הכיתה. בכל שלב יש 2 אפשרוית:

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

ממשיכים בתהליך עד אשר כל התלמידים משויכים לאחת הקבוצות. קל לראת שהתקבל פיצול תקין של הכיתה.

הערה

הכללה של הבעיה ופתרונה, תוארה על ידי נגה אלון.^[1] הפתרון שם כללי יותר ומתבסס על מקרה פרטי של משפט של קרסטן תומאסן.^[2] משפט זה משחק תפקיד דומה לזה של למה 8 בהוכחה כאן. המשפט אומר שבכל גרף מכוון שדרגת היציאה של כל קודקוד בו היא לפחת 3 קיימים שני מעגלים (מכוונים) שקבוצות קוקודיהם זרות.

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

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

הערות שוליים

^ High School Coalitions
^ C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983), 393-396.
^ N. Alon, Disjoint directed cycles, J. Combinatorial Theory, Ser. B 68 (1996), 167-178

[1] High School Coalitions

[2] C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983), 393-396.

[3] N. Alon, Disjoint directed cycles, J. Combinatorial Theory, Ser. B 68 (1996), 167-178

[1]

[2]

[3]