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

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

ההוכחה

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

תבנית:עוגן למה 7: בהינתן תלמיד, ניתן להושיב את שלושת התלמידים שהוא בחר במעגל כך שכל אחד בחר בתלמיד שלימינו. תבנית:טבלה מוסתרת תבנית:עוגן למה 8: קיימות 2 קבוצות זרות לא ריקות של תלמידים $A$ ו - $B$ כך שכל תלמיד מכל אחת מהקבוצות בחר לפחות תלמיד אחד בקבוצה שלו. תבנית:טבלה מוסתרת

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

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

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

הערה

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

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

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