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

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

• שאלה

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

  נושאים:

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

• שאלה

  מישור נצבע בשני צבעים (כלומר, כל נקודת המישור נצבעה באחת משני הצבעים האלה). הוכיחו כי קיימות שתי נקודות במישור במרחק `1` כך ששתיהן באותו צבע.

  נושאים:

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

• שאלה

  במישור נתונה נקודה ו-`12` ישרים שעוברים דרכה. הוכיחו כי יש שניים מתוך הישרים האלה שהזווית בינם פחות מ-`17^@`.

  נושאים:

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

• שאלה

  במישור נתונים `12` ישרים נחתכים. הוכיחו כי כי יש שניים מתוך הישרים האלה שהזווית בינם פחות מ-`17^@`.

  הצגת רמז

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

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

• כדורים בשק

  בשק יש `70` כדורים זהים בצבעים שונים: `20` כחולים, `20` אדומים, `20` צהובים והשאר שחורים ולבנים. מה המספר המינימלי של כדורים שצריך להוציא מהשק בלי להסתכל, כדי שבוודאות יהיו לנו `10` כדורים בצבע זהה?

  נושאים:

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

• המלך והשרים המושחתים

  למלך של הארץ הקסומה יש `100` שרים. ידוע כי בין כל `10` שרים שניקח, יש לפחות שר אחד מושחת. מהו המספר המינימלי האפשרי של שרים מושחתים בארץ הקסומה?

  נושאים:

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

• שאלה

  זר מורכב מ-`7` שושנים, לבנות ואדומות (שני הצבעים נוכחים). ידוע כי מתוך כל שתי שושנים, אחת בהכרח לבנה. כמה שושנים לבנות וכמה שושנים אדומות יש בזר?

  נושאים:

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

• שאלה

  האם תוכלו לחלק `44` כדורים ל-`9` ערימות אם כמות שונה של כדורים?

  נושאים:

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

• שאלה

  מהו המספר המקסימלי של מלכי שח שניתן להציב על לוח `8xx8`, כך שהם לא יאיימו אחד על שני?

  נושאים:

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

• שאלה

  מהו המספר המקסימלי של צריחי שח שניתן להציב על לוח `8xx8`, כך שהם לא יאיימו אחד על שני?

  נושאים:

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