קומבינטוריקה, עקרון שובך היונים

עקרון שובך היונים קובע שאם `n` פריטים מוכנסים ל-`m` תאים, כאשר `n > m`, אז לפחות תא אחד חייב להכיל יותר מפריט אחד. שאלות כוללות יישום עיקרון זה (והכללותיו) להוכחת קיום או קביעת חסמים בתרחישים שונים.

• צייד ביער הקסום

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

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים
  מקורות:
  • האולימפיאדה לצעירים, תש"פ, גמר, כיתות ה-ו שאלה 4

• רחוב צבעוני

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

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים לוגיקה -> הגיון קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • האולימפיאדה לצעירים, תשפ"א, שלב א, כיתות ג-ד שאלה 6

• רחוב צבעוני 2

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

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים הוכחה ודוגמה -> בניית דוגמה קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • האולימפיאדה לצעירים, תשפ"א, שלב א, כיתות ה-ו שאלה 5
  • האולימפיאדה לצעירים, תשפ"א, שלב א, כיתות ז-ח שאלה 6

• טורניר טניס

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

  קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> ספירה כפולה
  מקורות:
  • שעשועונים במתמטיקה, הנרי ארנסט דודני שאלה 266

• קוביות האותיות - שלושים ושש

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

  קומבינטוריקה -> עקרון שובך היונים לוגיקה -> הגיון קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • שעשועונים במתמטיקה, הנרי ארנסט דודני שאלה 305

• לוח השחמט הצפוף

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

  קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> בדיקת מקרים -> תהליכים
  מקורות:
  • שעשועונים במתמטיקה, הנרי ארנסט דודני שאלה 306