Loading AI tools
עקרון במתמטיקה ומדעי המחשב מוויקיפדיה, האנציקלופדיה החופשית
עֶקרון שובך היונים או עֶקרון דיריכלה הוא עיקרון מתמטי הקובע כי אם פריטים מפוזרים בין תאים, אז בהכרח ישנו תא אחד לפחות המכיל יותר מפריט אחד. באופן כללי יותר, כלל זה קובע כי לכל פריטים המפוזרים בין תאים כך ש, אז בהכרח בלפחות תא אחד יימצאו לפחות פריטים, כלומר קיים תא שמספר הפריטים בו הוא לפחות כמו הממוצע.
עיקרון זה נוסח ככל הנראה לראשונה בצורה רשמית בשנת 1834 בידי המתמטיקאי הגרמני יוהאן דיריכלה.
לעיקרון טריוויאלי זה יש שימושים רבים בהוכחות בקומבינטוריקה ומדעי המחשב, ועל אף פשטותו, ניתן להוכיח באמצעותו תוצאות רבות, מעניינות ובלתי טריוויאליות כלל.
הרחבה למקרה האינסופי: אם יש אינסוף יונים, ומספר סופי של תאים בשובך לתוכם יש להכניס את אינסוף היונים, בהכרח בתא אחד לפחות יהיו אינסוף יונים.
הרחבה מקובלת נוספת: אם יש תאים בשובך שלתוכם יש להכניס יונים, אז בהכרח יישאר תא ריק אחד לפחות.
דוגמאות נוספות ליישומים של העיקרון:
נניח בשלילה כי חולקו פריטים בין תאים ושבכל התאים ישנם לכל היותר פריטים. בעקבות הנחה זו, מספר הפריטים הכולל בתאים הוא לכל היותר . סכום זה קטן מ- ולכן נגיע לסתירה.
עקב פשטותה של ההוכחה נעשה בה שימוש רב במחקר העוסק בסיבוכיות של מערכות הוכחה (Proof Complexity).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.