הצגת המקור של הדף "פורטל:מתמטיקה/חידה/16/פתרון בונוס"

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

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

===מעבר אינדוקציה===
[[הוכחה בדרך השלילה|נניח בשלילה]] שיש לנו כיתה בגודל <math>n</math> שאינה ניתנת לפיצול. נניח גם באינדוקציה, שכל כיתה קטנה יותר ניתנת לפיצול. כל הטענות מעתה יהיו תחת הנחת השלילה והנחת האינדוקציה.

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

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

{{עוגן|למה 1}}
[[קובץ:Lema1.svg|שמאל|ממוזער|150px|אין שני קודקודים בגרף המצביעים זה על זה.]]
'''למה 1:''' אין בכיתה שני תלמידים שכל אחד מהם רשם את השני.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
נניח שיש 2 תלמידים כאלה (נקרא להם א' וב'). בכזה מקרה  ניתן לפצל את הכיתה בקלות: שמים את א' וב' בכיתה אחת (נקרא לה <math>A</math>) ואת כל השאר בכתה אחרת (נקרא לה <math>B</math>). הפיצול הזה הוא תקין כי:
* אחת הבחירות של א' (תלמיד ב') נמצאת בכיתה שלו (כיתה <math>A</math>)
* אחת הבחירות של ב' (תלמיד א') נמצאת בכיתה שלו (כיתה <math>A</math>)
* לפי [[עיקרון שובך היונים]], כל תלמיד שנמצא בכיתה <math>B</math> בחר לפחות תלמיד אחד שאינו בכיתה <math>A</math> (במילים אחרות תלמיד שנמצא בכיתה <math>B</math>).
}}

{{עוגן|למה 2}}
[[קובץ:Lema2.svg|שמאל|ממוזער|150px|אל כל קודקוד בגרף (בתמונה צבוע באדום) מצביע קודקוד אחר.]]
'''למה 2:''' כל תלמיד נרשם לפחות על ידי תלמיד אחד אחר.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
[[הוכחה בדרך השלילה|נניח בשלילה]], שיש תלמיד שלא נרשם על ידי אף אחד. בכזה מקרה ניתן, לפי [[#הנחת האינדוקציה|הנחת האינדוקציה]], לפצל את הכיתה בלעדיו, ואז לצרפו לקבוצה בה יש תלמיד שהוא רשם. זה נותן פיצול של הכיתה, בסתירה להנחה שהכיתה לא ניתנת לפיצול.
}}

{{עוגן|למה 3}}

[[קובץ:Lema3.png|שמאל|ממוזער|150px|כל חץ בגרף (בתמונה צבוע באדום) נמצא בתוך משולש כמו בתמונה.]]
'''למה 3:''' אם תלמיד אחד רשם תלמיד אחר, אז קיים תלמיד שלישי שרשם את שניהם.

{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
[[הוכחה בדרך השלילה|נניח בשלילה]], שתלמיד א' רשם את תלמיד ב', אבל אין אף תלמיד שרשם את שניהם. נוציא לרגע את תלמיד א' מהכיתה. נקבל כיתה קטנה יותר. לפי [[#למה 2|למה 2]], תלמיד ב' לא רשם את תלמיד א', לכן הרשימה שלו עדיין תקינה בכיתה הקטנה יותר. נעבור על הרשימות של כל התלמידים שרשמו את תלמיד א',  ונחליף  את שמו של תלמיד א' בשמו של תלמיד ב'. מכיוון שאיש לא רשם גם את א' וגם את ב' נקבל שעדיין בכל רשימה מופיעים 3 תלמידים שונים. לכן, לפי הנחת האינדוקצה אפשר לפצל את הכיתה הקטנה יותר. נפצל אותה ונוסיף את תלמיד א' לקבוצה בה נמצא תלמיד ב'. קל לראות שכל תלמיד קיבל את אחד משלושת התלמידים שהוא רשם. זה נותן פיצול של הכיתה, בסתירה להנחה שהיא לא ניתנת לפיצול.
}}

[[קובץ:Lema4.svg|שמאל|ממוזער|250px|כל קודוקוד בגרף (בתמונה צבוע באדום) נמצא בתוך תת-גרף כמו בתמונה.]]
{{עוגן|למה 4}}
'''למה 4:''' עבור כל תלמיד קיים מספר <math>n\geq 3</math> ו- <math>n</math> תלמידים שבחרו בו כך שניתן להושיבם במעגל כך שכל אחד בחר בתלמיד שלימינו.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
נקבע תלמיד ונקרא לו א'. נסמן ב - <math>A</math> את קבוצת התלמידים שרשמו אותו. לפי [[#למה 2|למה 2]] קבוצה זאת איננה ריקה. לפי [[#למה 3|למה 3]], עבור כל תלמיד ב - <math>A</math> קיים תלמיד אחר ב - <math>A</math> שרשם אותו. נקח תלמיד ב - <math>A</math> נעמיד אותו ונקרא לו <math>x_1</math>. נקח תלמיד אחר ב - <math>A</math> שרשם את <math>x_1</math> נעמיד אותו לשמאלו של <math>x_1</math> ונקרא לו <math>x_2</math>, נמשיך הלאה כך שבכל שלב אנו בוחרים תלמיד ב - <math>A</math> שעדיין יושב ובחר בתלמיד האחרון שהעמדנו. בשלב מסוים לא נוכל לעשות זאת כי התלמיד ב - <math>A</math> שבחר בתלמיד האחרון שהעמדנו כבר עומד בשורה. נשתמש בתלמיד זה כדי לסגור מעגל כפי שנדרש. לפי [[#למה 1|למה 1]] המעגל חייב להיות לפחות באורך 3.
}}

[[קובץ:Lema5.svg|שמאל|ממוזער|150px|כל קודוקוד בגרף (בתמונה צבוע באדום) נמצא בתוך תת-גרף כמו בתמונה.]]
{{עוגן|למה 5}}
'''למה 5:''' כל תלמיד נבחר בדיוק על ידי 3 תלמידים אחרים. כמו כן, ניתן להושיב את שלושת תלמידים אלו במעגל כך שכל אחד בחר בתלמיד שלימינו.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
נשתמש ב[[ספירה כפולה]]. מכיוון שכל תלמיד רשם  3 תלמידים, המספר הכולל של שמות התלמידים שנרשמו הוא <math>3n</math>. לכן מספר התלמידים שבחרו בתלמיד נתון הוא 3 בממוצע. מצד שני, לפי [[#למה 4|הלמה הקודמת]] מספר התלמידים המינימלי שבחרו תלמיד אחד הוא לפחות 3. לכן מספר זה הוא 3 עבור כל תלמיד.

העובדה שאפשר להושיב את התלמידם שבחרו תלמיד נתון במעגל כנידרש נובעת מ[[#למה 4|הלמה הקודמת]].
}}

[[קובץ:Lema6.png|שמאל|ממוזער|150px|שלושת הבחירות של כל קודוקוד בגרף (בתמונה צבועות באדום) מחוברות זו לזו. בשלב זה איננו יודעים מה כיוון החצים ביניהן.]]
{{עוגן|למה 6}}
'''למה 6:''' עבור כל 2 תלמידים שנבחרו על ידי תלמיד נתון, אחד מהם בחר את השני.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
נרשום את כל זוגות התלמידים שבהם הראשון בחר בשני. מכיוון שכל תלמיד בחר 3 תלמידים, מספר הזוגות שרשמנו הוא <math>3n</math>. ליד כל זוג נרשום בצבע כחול תלמיד שבחר את שני התלמידים בזוג (זה אפשרי לפי [[#למה 3|למה 3]]). סך-הכל רשמנו <math>3n</math> תלמידים בכחול. מכאן שבממוצע כל תלמיד מופיע 3 פעמים בכחול. מצד שני, תלמיד לא יכול להופיע יותר מ-3 פעמים בכחול, מכיוון שכל תלמיד בחר רק 3 תלמידים ומ-3 תלמידים אפשר להרכיב רק 3 זוגות (לא סדורים) וכל זוג יכול להופע רק פעם אחת ברשימה בגלל [[#למה 1|למה 1]]. מכאן שכל תלמיד מופיע בצבע כחול 3 פעמים בידיוק. כך שעבור כל זוג מבין שלושת התלמידים שהוא בחר, אחד בחר את השני.
}}
[[קובץ:Lema7.png|שמאל|ממוזער|150px|שלושת הבחירות של כל קודוקוד בגרף (בתמונה צבועות באדום) יוצרות מעגל כמו בתמונה.]]
{{עוגן|למה 7}}
'''למה 7:''' בהינתן תלמיד, ניתן להושיב את שלושת התלמידים שהוא בחר במעגל כך שכל אחד בחר בתלמיד שלימינו.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
[[קובץ:Lema7_proof.png|שמאל|ממוזער|300px|לפי [[#למה 6|הלמה הקודמת]], ישנן שתי תצורות אפשריות. לפי [[#למה 5|למה 5]] ו[[#למה 1|למה 1]], תצורה ב' אינה אפשרית. מכאן שתצורה א' בהכרח מתקיימת.]]
[[הוכחה בדרך  השלילה|נניח בשלילה]] שקיים תלמיד (נקרא לו א')  שבחר שלושה תלמידים (נקרא להם ב', ג' וד') שלא ניתן להושיבם במעגל, כך שכל אחד מהם בחר את זה שלימינו. לפי [[#למה 6|הלמה הקודמת]], בכל זוג מבין התלמידים ב', ג' וד' אחד בחר את השני. 

'''טענה:''' יש תלמיד אחד מבין ב', ג' וד' שנבחר על ידי השניים האחרים.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
[[ללא הגבלת הכלליות|בה"כ]] נניח שב' בחר את ג'. אם ד' בחר את ג' אז סיימנו. אחרת ג' בחר את ד'. אם א' בחר את ד' אז סיימנו. אחרת קיבלנו מעגל, [[סתירה (לוגיקה)|בסתירה]] להנחת השלילה.
}}
כעת [[ללא הגבלת הכלליות|בה"כ]] נניח שב' נבחר על ידי ג' וד'. אם כך, שלושת התלמידים שבחרו בב' הם א', ג' וד'. לפי [[#למה 5|למה 5]], אפשר להושיב אותם במעגל כך שכל אחד בחר את זה שלימינו. זה אומר שא' נבחר על ידי אחד מהשניים האחרים, זה, יחד עם [[#למה 1|למה 1]], [[סתירה (לוגיקה)|סותר]] את העובדה שא' בחר את ג' וד'.
}}
{{עוגן|למה 8}}
'''למה 8:''' קיימות 2 קבוצות זרות לא ריקות של תלמידים <math>A</math> ו - <math>B</math> כך שכל תלמיד מכל אחת מהקבוצות בחר לפחות תלמיד אחד בקבוצה שלו.
{{טבלה מוסתרת|עיצוב=|עיצוב כותרת=|כותרת='''הוכחה'''|תוכן=
[[קובץ:Lema8 poof.svg|שמאל|ממוזער|200px|]]
נבחר תלמיד. נסמן ב - <math>A</math> את קבוצת התלמידים שהוא בחר וב - <math>B</math> את קבוצת התלמידים שבחרו אותו.
* לפי [[#למה 1|למה 1]] קבוצות אלו זרות. 
* לפי [[#למה 2|למה 2]] הקבוצה  <math>B</math> איננה ריקה. 
* לפי תנאי הבעיה הקבוצה <math>A</math> איננה ריקה.
* לפי [[#למה 5|למה 5]] כל תלמיד ב - <math>B</math> בחר לפחות תלמיד אחד ב - <math>B</math>. 
*  לפי [[#למה 7|למה 7]] כל תלמיד ב - <math>A</math> בחר לפחות תלמיד אחד ב - <math>A</math>.
}}

כעת נראה איך מפצלים את הכיתה: נבחר <math>A</math> ו - <math>B</math> כמו [[#למה 8|בלמה האחרונה]]. אנחנו נוסיף תלמידים שלב אחר שלב ל-<math>A</math> ול - <math>B</math> עד אשר יתקבל פיצול של הכיתה. בכל שלב יש 2 אפשרוית:
# '''קיים תלמיד שעדיין לא נמצא באף אחת מהקבוצות אך אחד התלמידים שהוא בחר נמצא באחת מהקבוצות.''' בכזה מקרה נוסיף תלמיד זה לקבוצה שבה נמצא התלמיד שהוא בחר.
# '''האפשרות הראשונה לא מתקיימת.''' בכזה מקרה נוסיף את כל התלמידים שעדיין לא נמצאים באף אחת מהקבוצת לקבוצה <math>A</math>.

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

==הערה==
הכללה של הבעיה ופתרונה, תוארה על ידי [[נגה אלון]].{{הערה|[https://www.tau.ac.il/~nogaa/PDFS/coalition.pdf High School Coalitions]}} הפתרון שם כללי יותר ומתבסס על מקרה פרטי של [[משפט תומאסן|משפט]] של [[קרסטן תומאסן]].{{הערה| C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983), 393-396.
}} משפט זה משחק תפקיד דומה לזה של [[#למה 8|למה 8]] בהוכחה כאן. המשפט אומר שבכל [[גרף מכוון]] ש[[דרגה (תורת הגרפים)#דרגת יציאה|דרגת היציאה]] של כל קודקוד בו היא לפחת 3 קיימים שני מעגלים (מכוונים) שקבוצות קוקודיהם זרות.

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

במאמרו, תומאסן דן בקריטריונים לכך שבגרף יהיו מספר מעגלים זרים בקודקודיהם במונחים של דרגת היציאה המינימלית. במאמר אחר{{הערה| N. Alon, Disjoint directed cycles, J. Combinatorial Theory, Ser. B 68 (1996), 167-178}} אלון מקבל תוצאה הדוקה יותר לגבי שאלה זאת.

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}