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

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

• שאלה

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

  נושאים:

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

• שאלה

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

  נושאים:

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

• שאלה

  המספרים `1`, `2`, `3`, ..., `9` מחלוקים ל-`3` קבוצות. הוכיחו כי ישנה קבוצה בה מכפלת המספרים גדולה או שווה ל-`72`.

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

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

• שאלה

  נתונים `50` מספרים טבעיים שונים בין `1` ל-`100`. ידוע כי אין בינם שני מספרים שסכומם שווה ל-`100`. האם נכון שאחד מהמספרים האלה חייב להיות ריבוע שלם?

  נושאים:

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

• שאלה

  בפנים של ריבוע עם צלע 1 סומנו `n>=101` נקודות, כך שאף שלוש לא על ישר. משולש יקרא מסומן אם קודקודיו הם נקודות מסומנות הוכיחו כי שטחו של אחד המשולשים המסומנים קטן מ- `1/100`

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

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

• שאלה

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

  הצגת רמז

  התחברו כאן לאתר על מנת לקבל את הרמז
  נושאים:

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

• צעצועים

  ליונתן יש אוסף של צעצועי עץ. חלקם קוביות וחלקם כדורים, חלקם אדומים וחלקם כחולים.

  ידוע שיש יותר כדורים מאשר קוביות, וידוע שיש יותר צעצועים כחולים מאשר צעצועים אדומים.

  הוכיחו כי יש ליונתן כדור כחול.

  נושאים:

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

• בוחן

  בכיתה של 25 תלמידים התקיים בוחן המורכב מ-7 שאלות. הוכיחו כי לפחות אחד משני המשפטים הבאים נכון:

  1. יש ילד שפתר מספר אי זוגי של שאלות
  2. יש שאלה שפתרו אותה מספר זוגי של ילדים
  נושאים:

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

• השולחן העגול

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

  נושאים:

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

• לוח ציור

  לצייר יש לוח משבצות `10 times 10`. בכל פעם הצייר בוחר שורה או עמודה וצובע את כולה בצבע לבחירתו.
  אם הוא עובר עם צבע חדש על משבצת שכבר נצבעה, הצבע החדש מכסה את הצבע הישן במלואו,
  כלומר, צבע המשבצת מתחלף.
  מהו המספר הגדול ביותר של צבעים שנוכל לראות על הלוח הזה?

  נושאים:

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