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

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

• שאלה

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

  א. להרכיב בוודאות זוג גרביים כלשהו,

  ב. להרכיב בוודאות זוג גרביים שחורים?

  נושאים:

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

• שאלה

  טבלה `N×N` ממולאת במספרים כך שכל השורות נבדלות (לפחות במקום אחד). הוכח/י כי אפשר למחוק עמודה כלשהי כך שבטבלה שתישאר גם כל השורות יהיו שונות.
  א. אנג'אנס

  נושאים:

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

• שאלה

  במרחב נתונים 30 וקטורים לא מנוונים. הוכח כי יש לפחות 2 שהזווית ביניהם היא לא גדולה מ- 45 מעלות. 
  א. טולפיגו

  נושאים:

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

• שאלה

  בחברה עובדים `30` אנשים. הצעיר מביניהם הוא בן `20`, והמבוגר – בן `45`. האם נכון שבחברה הזאת בהכרח יש אנשים בני אותו גיל?

  הצגת רמז

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

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

• שאלה

  בבית ספר לומדים `400` תלמידים. הוכיחו כי קיימים שני תלמידים שחוגגים יום הולדת באותו תאריך בשנה.

  נושאים:

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

• שאלה

  עש עשה `15` חורים נקודתיים בשטיח שגודלו `4xx4` מטרים. האם תמיד ניתן לגזור מהשטיח המקורי שטיחון בגודל `1xx1` מטר כך שלא יהיה בו חורים?

  הצגת רמז

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

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

• שאלה

  האם תוכלו למלא טבלה בגודל `5xx5` על ידי

  א. מספרים שלמים,

  ב. מספרים ממשיים,

   כך שהסכום בכל שורה יהיה זוגי, והסכום בכל עמודה יהיה אי זוגי?

  הצגת רמז

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

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

• שאלה

  במדינה קסומה יש מטבעות של `1`, `2`, `3` ו-`5` לירות. ליוסי יש `25` מטבעות של המדינה הקסומה.

  האם בהכרח יש בין המטבעות האלו `7` מטבעות בעלות ערך זהה?

  נושאים:

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

• שאלה

  בכיתה `38` תלמידים. הוכיחו כי יש ארבעה תלמידים בכיתה שחוגגים יום הולדת באותו חודש.

  נושאים:

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

• שאלה

  הוכיחו כי קיימות שתי חזקות של `2` שהפרש שלהן מתחלק ב-`2017`.

  נושאים:

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