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