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

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

• תפוחים ואגסים

  ישנו סל בו `30` פירות. ידוע כי בין `12` פירות כלשהם שניקח מהסל, יש בהכרח לפחות תפוח אחד, ובין כל `20` פירות יש בהכרח אגס אחד. כמה תפוחים וכמה אגסים יש בסל?

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים אלגברה -> אי שוויונים לוגיקה -> הגיון
  מקורות:
  • אתר האינטרנט problems.ru

• שאלה

  בקודקודים של קובייה רשומים המספרים `1`, `2`, `3`, ..., `8`. הוכיחו כי קיים מקצוע של הקובייה שההפרש בין המספרים שעומדים בקצותיו לפחות `3`.

  נושאים:

  גאומטריה -> גאומטריה במרחב קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> תורת הגרפים לוגיקה -> הגיון הוכחה ודוגמה -> הוכחה בשלילה

• ערימת דפים

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

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> גאומטריה קומבינטורית גאומטריה -> חשבון שטחים גאומטריה -> גאומטריה במישור -> סימטריה

• שאלה

  הוכיחו שלכל פאון יש שתי פאות עם כמות זהה של מקצועות.

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים קומבינטוריקה -> תורת הגרפים גאומטריה -> גאומטריה במרחב -> פאונים

• אבירי השולחן העגול

  סביב שולחן עגול יושבים 12 אבירים, שכל אחד מהם או אֶלְף או גמד. ידוע כי מספר האֶלפים גדול יותר ממספר הגמדים.  הוכיחו כי ישנם שני אֶלפים שיושבים אחד מול השני.

  האם זה ימשיך להיות נכון אם המספר הכולל של האבירים יהיה 120?

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים לוגיקה -> הגיון הוכחה ודוגמה -> הוכחה בשלילה

• שאלה

  הוכיחו כי מבין חמישה מספרים שלמים ניתן לבחור שניים שהפרש שלהם מתחלק ב-`4`.

  נושאים:

  תורת המספרים -> חשבון השאריות קומבינטוריקה -> עקרון שובך היונים תורת המספרים -> חלוקה -> זוגיות אריתמטיקה -> חילוק עם שארית

• שאלה

  א. הוכיחו כי  בין `11` מספרים טבעיים תמיד אפשר לבחור שניים שספרות האחדות שלהם זהות.

  ב. הוכיחו כי  בין `11` מספרים טבעיים תמיד אפשר לבחור שניים שהפרש שלהם מתחלק ב-`10`.

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים תורת המספרים -> חשבון השאריות -> סימני חלוקה -> סימני חלוקה ב-5 וב-25

• שאלה

  ל-`21` ילדים יש סך הכל `200` אגוזים. הוכיחו כי קיימים שני ילדים שיש להם אותה כמות של אגוזים.

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים הוכחה ודוגמה -> הוכחה בשלילה בעיות מינימום ומקסימום

• שאלה

  בכיתה לומדים `30` תלמידים. במהלך מבחן פנחס עשה `13` טעויות, והשאר עשו פחות טעויות. הוכיחו שיש שלושה תלמידים שעשו כמויות זהות של טעויות.

  נושאים:

  קומבינטוריקה -> עקרון שובך היונים לוגיקה -> הגיון הוכחה ודוגמה -> הוכחה בשלילה בעיות מינימום ומקסימום

• שאלה

  המספרים מ-`1` עד `2n` רשומים בשורה בסדר כלשהו. מוסיפים לכל מספר את אינדקס המקום עליו הוא עומד. הוכיחו כי בין `2n` הסכומים שקיבלנו יש שניים שהפרש שלהם מתחלק ב-`2n`.

  נושאים:

  תורת המספרים -> חשבון השאריות קומבינטוריקה -> עקרון שובך היונים הוכחה ודוגמה -> הוכחה בשלילה