חזור לתיקייה: 02340141 - קומבינטוריקה למדעי המחשב

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

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • כללי
  • עקרון שובך היונים ל-\infty

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

02340141

קומבינטוריקה למדעי המחשב

רשימות הרצאה לקריאה בשבת

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

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

זהו כלי שאנו נשתמש בו הרבה בפתרון בעיות קומבינטוריות.

משפט (עקרון שובך היונים)

אם יש בשובך nnn תאים ובהם שוכנות n+1n+1n+1 יונים, קיים בהכרח תא (אחד לפחות) שבו שוכנות שתי יונים לפחות.

הוכחה:
נניח בשלילה שכל שובך הוא ריק או עם יונה אחת ⇐ מספר היונים הוא לכל היותר nnn. סתירה לכך שיש לנו n+1n+1n+1 יונים.
∎

משפט (הכללת העקרון)

אם מחלקים mmm כדורים ל-nnn תאים אז קיים תא עם ⌈mn⌉\left\lceil \frac{m}{n}\right\rceil⌈nm​⌉ כדורים לפחות.

הוכחה:
נניח בשלילה שכל תא מכיל לכל היותר ⌈mn⌉−1\lceil \frac{m}{n}\rceil-1⌈nm​⌉−1 כדורים. אזי, מספר הכדורים הוא לכל היותר:

(⌈mn⌉−1)n<mn⋅n=m\left( \left\lceil \frac{m}{n}\right\rceil-1 \right)n< \frac{m}{n}\cdot n=m(⌈nm​⌉−1)n<nm​⋅n=m

ולכן סתירה
∎

טענה

בכל קבוצה של שישה אנשים קיימים לפחות שניים המכירים אותו מספר של אנשים.
(מניחים שאם AAA מכיר את BBB אז BBB מכיר את AAA)

הערה (ענן המחשבות)

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

למה

הסדרה x1,x2,x3,x4,x5,x6x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}x1​,x2​,x3​,x4​,x5​,x6​ איננה יכולה להכיל גם את 000 וגם את 555. בפרט, היא מכילה לכל היותר 5 מספרים שונים.

הוכחה:
אחרת, היה קיים מישהו שמכיר את כולם ומישהו שלא מכיר אף אחד. - סתירה.
∎
לכן, למעשה מכניסיפ 6 יונים רק ל-5 תאים.

דוגמה

נתונה הקבוצה: {0,1,…,9}\left\{ 0,1,\dots,9 \right\}{0,1,…,9}. נדרש להוכיח כי אם נבחר 6 מספרים מהקבוצה, יהיו זוג מספרים שסכומם 9.

הוכחה:
הקבוצה בנויה מזוגות שסכומם 9 והם: 0−92−75−41−83−6\begin{matrix}0&-&9&&2&-&7&&5&-&4\\1&-&8&&3&-&6\end{matrix}01​−−​98​​23​−−​76​5−4.
נקצה שובך לכל זוג. לכל מספר, ישנו שובך יחיד שהוא שייך אליו. (לדוגמה 2 שייך ל-2−72-72−7). אם נקח שישה מספרים ונשים כל מספר בשובך שמתאים לו ⇐ לפי עקרון שובך היונים, מובטח שישנו שובך שבו נמצאים שני איבריו. סכומם 999 כנדרש.
∎

דוגמה

טענה

בכל קבוצה של 121212 מספרים שונים דו-ספרתיים קיימים לפחות שניים שהפרשם נותן מספר דו-ספרתי בעל ספרות זהות.

נניח עבור 10,84,11,23,19,20,35,47,59,45,60,7210,84,11,23,19,20,35,47,59,45,60,7210,84,11,23,19,20,35,47,59,45,60,72. נסתכל על שארית החלוקה ב-111111. אם יש 2 שיש להם שארית חלוקה זהה, אזי הפרשם יהיה בעל אותן ספרות. (למה? דנה נמה)
ואז, מכיוון שיש 12 מספרים אותם אנו מכניסים ל-11 תאים, לפי עקרון שובך היונים, יהיו זוג מספרים שכזה. - כנדרש.

עקרון שובך היונים ל-∞\infty∞

אם מחלקים ∞\infty∞ כדורים ל-nnn תאים אזי קיים תא עם ∞\infty∞ כדורים. אך אם מחלקים ∞\infty∞ כדורים ל-nnn תאים אזי לא קיים תא אחד בלבד עם ∞\infty∞ כדורים.
בנוסף, אם מחלקים ∞\infty∞ כדורים ל-∞\infty∞ תאים אזי לא קיים תא עם ∞\infty∞ כדורים.