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

עֶקרון שובך היונים או עֶקרון דיריכלה הוא כלל מתמטי פשוט אך חשוב. הוא קובע שאם מפזרים n פריטים בין m תאים, אז גם אם מנסים לחלק שווה, לפחות בתא אחד יהיו לפחות ⌈n/m⌉ פריטים. הסימון ⌈n/m⌉ מציין את הערך של n/m מעוגל מעלה.

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

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

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

העיקרון מופיע בכמה הוכחות פשוטות ומתקדמות. דוגמת ה-10 וה-9 ממחישה את הרעיון בלי חישובים מורכבים.

נניח בשלילה שכל התאים מכילים לכל היותר ⌈n/m⌉−1 פריטים. אז המספר הכולל של הפריטים בכל התאים הוא לכל היותר m(⌈n/m⌉−1). ביטוי זה קטן מ-n, ולכן יש סתירה. לכן חייב להיות תא עם לפחות ⌈n/m⌉ פריטים.

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

עֶקרון שובך היונים אומר דבר פשוט. אם שמים יותר יונים מתאים, לפחות תא אחד יקבל יותר מיונה אחת.

דוגמה קטנה: 10 יונים בתוך 9 תאים. מבין זה שי צריך להיות תא עם שתי יונים לפחות.

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

אם נניח שכל תא מכיל פחות מדי יונים, אז בסך הכל יהיו פחות יונים ממה שיש באמת. זה סותר את המספר האמיתי, ולכן יש תא עם יותר יונים.

העיקרון עוזר לפתור חידות ובעיות בלימודי המתמטיקה והמדע.