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

מתוך ויקיפדיה, האנציקלופדיה החופשית

ההשראה לעיקרון: יונים בשובכים. כאשר כאן n=7, m=9, ולכן העיקרון לא בא לידי ביטוי
הגדל
ההשראה לעיקרון: יונים בשובכים. כאשר כאן n=7, m=9, ולכן העיקרון לא בא לידי ביטוי

עקרון שובך היונים, או בשמו השני: "עיקרון דיריכלה", הוא עיקרון מתמטי הקובע כי אם יש n שובכים שלתוכם יש להכניס n+1 יונים, קיים בהכרח שובך אחד בו תמצאנה לפחות שתי יונים. לעיקרון טריוויאלי זה יש שימושים רבים בהוכחות בתחום הקומבינטוריקה, וניתן להוכיח באמצעותו תוצאות רבות ומעניינות שאינן טריוויאליות בכלל.

[עריכה] הרחבה לעיקרון

הרחבה ראשונה אומרת כי אם יש n שובכים שלתוכם יש להכניס m יונים, אז בהכרח בשובך אחד יהיו לפחות p יונים או יותר, כאשר p הוא המספר השלם הקרוב (בעיגול כלפי מעלה) למספר: m/n.
הרחבה שנייה אומרת כי אם יש n שובכים שלתוכם יש להכניס kn+1 יונים, אז קיים שובך שבו יש לפחות k+1 יונים.

[עריכה] דוגמאות

דוגמאות נוספות ליישומים של העיקרון:

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

[עריכה] הוכחה

נניח כי לתוך m שובכים אמורים להכניס n יונים, נכניס לכל שובך יונה אחת לכל היותר. קיבלנו כי הכנסנו, במקרה המכסימלי, m יונים, בסתירה לכך ש: n > m.