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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
ההשראה לעיקרון יונים בשובך. בתמונה זו n=10, m=9, ולכן על שתי יונים לפחות לחלוק תא אחד (m מייצג את מספר התאים בשובך ו-n את מספר היונים).

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

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

הרחבת העקרון[עריכת קוד מקור | עריכה]

אם יש m תאים בשובך שלתוכם יש להכניס n יונים, אז בהכרח בתא אחד יהיו לפחות  p= \lceil n/m \rceil יונים או יותר, (p הוא המספר השלם הקרוב (בעיגול כלפי מעלה) למספר: n/m). כלומר יש תא שמספר היונים בו הוא לפחות כמו הממוצע.

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

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

עיקרון שובך היונים מבטיח לנו שאם יש במגירה גרביים צהובים וכחולים, אז מכל 3 גרביים שנוציא 2 לפחות יהיו באותו צבע.

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

  • בכל קבוצה בת שלושה עשר אנשים, יהיו לפחות שני אנשים שנולדו באותו חודש.
  • יש במדינת ישראל לפחות שני אנשים עם אותו מספר שערות על ראשם; זאת מכיוון שמספר השערות האפשרי על ראשו של אדם מוערך בכמאה אלף, ואילו מספר התושבים במדינת ישראל הוא כמה מיליונים. בדוגמה זו ישנו תא שובך לכל מספר שערות אפשרי, והיונים הם תושבי מדינת ישראל.
  • בכל קבוצה בת שלושה אנשים, יהיו בהכרח שני אנשים בני אותו מין.
  • בכל פאה של קובייה הונגרית בגודל 3X3X3 (או גדול יותר), תמיד יהיה לפחות צבע אחד שמופיע פעמיים. זאת מכיוון שבכל פאה יש תשעה "תאים", ויש שישה צבעים להכניס. אם מכניסים צבע שונה לכל תא נשארים 3 תאים, שבהם מוכרח להיות צבע שכבר הכנסנו. בקובייה בגודל 2X2X2 המצב שונה- כיוון שיש 4 תאים ו-6 צבעים, בכל צד תמיד יהיה צבע שלא מופיע.
  • נניח כי נערכת מסיבה עם כמות כלשהי של מוזמנים. כל אורח לוחץ ידיים פעם אחת לכל אחד ממכריו במסיבה (ייתכן שאורח ילחץ ידיים לחלק, לכל או לאף אחד מהאורחים האחרים). בהכרח יש שני אורחים שלחצו אותו מספר של ידיים. הוכחה: נניח כי במסיבה יש n אורחים. מספר הידיים שכל אורח לוחץ הוא בין 0 ל-n-1 (שכן הוא לא לוחץ ידיים לעצמו). כלומר לאורח יש n אפשרויות שונות למספר הלחיצות. כדי שלא יהיו שני אורחים מבין n האורחים שלחצו אותו מספר של ידיים, בהכרח יש אורח שלחץ 0 ידיים, אורח שלחץ יד אחת, וכן הלאה עד לאורח שלחץ n-1 ידיים. אבל מצב זה אינו ייתכן שכן האורח שלחץ n-1 ידיים בהכרח לחץ את ידייהם של כל שאר האורחים, ולכן לא ייתכן שיהיה אדם שלחץ 0 ידיים. מכאן שיש שני אנשים שלחצו אותו מספר של ידיים.
  • בכל תת-קבוצה של \ n+1 ערכים מתוך הקבוצה \ \left\{1,2,\dots,2n\right\} יש שני ערכים כך שאחד מהם מחלק את השני. כדי לראות זאת, ניתן לכתוב כל מספר בקבוצה בצורה \ 2^k m כש-\ m הוא אי זוגי וקטן מ-\ 2n (\ m מתקבל פשוט על ידי חלוקה חוזרת ונשנית של המספר ב-2 עד שמתקבל ערך אי זוגי). יש רק n מספרים אי-זוגיים בין 1 ל-2n ולכן יש בקבוצה שני ערכים בעלי אותו חלק אי-זוגי m - ואחד מהם (זה שהחזקה של 2 עבורו היא קטנה יותר) בהכרח מחלק את השני.
  • דיריכלה עצמו השתמש בעקרון כדי להוכיח כי כל מספר אי-רציונלי ניתן לקירוב דיופנטי מסדר שני (הוכחה).
  • משפט ארדש-סקרש

הוכחת העקרון[עריכת קוד מקור | עריכה]

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

עקב פשטות ההוכחה של הטענה נעשה בה שימוש רב במחקר העוסק בסיבוכיות של מערכות הוכחה (Proof Complexity).

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

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Martin Aigner, Günter M. Ziegler, Proofs from THE BOOK, Springer, 1998.
  • Alexander Razborov, Proof Complexity of Pigeonhole Principles, Proceedings of the 5th DLT, Lecture Notes in Computer Science, vol. 2295, 2002, pages 100-116