עקרון שובך היונים
מתוך ויקיפדיה, האנציקלופדיה החופשית
עקרון שובך היונים, או בשמו השני: "עיקרון דיריכלה", הוא עיקרון מתמטי הקובע כי אם יש n שובכים שלתוכם יש להכניס n+1 יונים, קיים בהכרח שובך אחד בו תמצאנה לפחות שתי יונים. לעיקרון טריוויאלי זה יש שימושים רבים בהוכחות בתחום הקומבינטוריקה, וניתן להוכיח באמצעותו תוצאות רבות ומעניינות שאינן טריוויאליות בכלל.
[עריכה] הרחבה לעיקרון
הרחבה ראשונה אומרת כי אם יש n שובכים שלתוכם יש להכניס m יונים, אז בהכרח בשובך אחד יהיו לפחות p יונים או יותר, כאשר p הוא המספר השלם הקרוב (בעיגול כלפי מעלה) למספר: m/n.
הרחבה שנייה אומרת כי אם יש n שובכים שלתוכם יש להכניס kn+1 יונים, אז קיים שובך שבו יש לפחות k+1 יונים.
[עריכה] דוגמאות
דוגמאות נוספות ליישומים של העיקרון:
- בכל קבוצה של שלושה עשר אנשים, יהיו לפחות שני אנשים שנולדו באותו חודש.
- בכל קבוצה של שלושה אנשים, בהכרח יהיו שני אנשים בני אותו מין.
- הרחבה למקרה האינסופי: אם יש אינסוף יונים, ומספר סופי של שובכים לתוכם יש להכניס את אינסוף היונים, בהכרח בשובך אחד לפחות יהיו אינסוף יונים.
[עריכה] הוכחה
נניח כי לתוך m שובכים אמורים להכניס n יונים, נכניס לכל שובך יונה אחת לכל היותר. קיבלנו כי הכנסנו, במקרה המכסימלי, m יונים, בסתירה לכך ש: n > m.

