עקרון שובך היונים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תיקון טייפו. |
ביטול גרסה 31252112 של 2A02:14C:20A5:C400:6106:F860:C77C:F531 (שיחה) |
||
שורה 2:
'''עקרון שובך היונים''' הוא עיקרון [[מתמטיקה|מתמטי]] הקובע כי אם יש m תאים ב[[שובך]] שלתוכם יש להכניס m+1 [[יונה|יונים]], קיים בהכרח תא אחד שבו תימצאנה לפחות שתי יונים. עיקרון זה ככל הנראה נוסח לראשונה באופן פורמלי על ידי [[יוהאן פטר גוסטב לז'ן דיריכלה| יוהאן דיריכלה]] בשנת [[1834]], ומכאן שמו הנוסף '''עקרון דיריכלה'''.
לעיקרון טריוויאלי זה יש שימושים רבים בהוכחות ב[[קומבינטוריקה]] ו[[מדעי המחשב]] ועל אף פשטותו, ניתן
מוכר גם כעקרון ש"י.
==הרחבת העקרון==
אם יש m תאים בשובך שלתוכם יש להכניס n יונים, אז בהכרח בתא אחד יהיו לפחות <math> p= \lceil n/m \rceil</math> יונים או יותר, (p הוא המספר השלם הקרוב (ב[[פונקציית תקרה|עיגול כלפי מעלה]]) למספר: n/m). כלומר יש תא שמספר היונים בו הוא לפחות כמו הממוצע.
הרחבה למקרה ה[[אינסוף|אינסופי]]: אם יש אינסוף יונים, ומספר סופי של תאים בשובך לתוכם יש להכניס את אינסוף היונים, בהכרח בתא אחד לפחות יהיו אינסוף יונים.
הרחבה מקובלת נוספת: אם יש m תאים בשובך שלתוכם יש להכניס m-1 יונים, אז בהכרח יישאר תא ריק אחד לפחות.
==דוגמאות==
שורה 37:
*Martin Aigner, Günter M. Ziegler, '''Proofs from THE BOOK''', Springer, 1998.
*Alexander Razborov, [http://www.mi.ras.ru/~razborov/php_survey.ps Proof Complexity of Pigeonhole Principles], Proceedings of the 5th DLT, Lecture Notes in Computer Science, vol. 2295, 2002, pages 100-116
</div>
==קישורים חיצוניים==
| |||