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

מאת: עודד לבנה

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

העקרון עצמו אינטואיטיבי מאד. אתחיל בדוגמא ואמשיך בדיאלוג עד שאגיע לניסוח מדוייק של
העקרון:
אם יש שובך עם 100 תאים וצריך לשבץ בו מאה ואחת יונים,
אז אי אפשר להקצות לכל יונה תא נפרד.
נתחיל לגבש את העיקרון, בלי לפחד לטעות, בשיחה בין סוקרטס (אשר מנסה לגבש
את העיקרון) לדיריכלה (אשר מוצא את השגיאות וההחסרות של סוקרטס) :

סוקרטס:ברור שאם יש מאה ואחת יונים ובשובך יש מאה תאים , ואם נכניס את כל היונים
לתאים, אז יהיו שתים באותו תא.
דיריכלה: לא נכון.
סוקרטס: איך לא?
דיריכלה: יכול להיות שיש בתא אחד שלוש, בתא אחד אפס ובשאר התאים אחת.
סוקרטס: נו?
דיריכלה: אז אין אף תא עם שתים. אתה יכול גם לשים את כל היונים בתא אחד, אם התאים
מספיק גדולים (או היונים מספיק קטנות)
סוקרטס: נכון, אבל יש תא עם לפחות שתי יונים.
דיריכלה: זה נכון.
סוקרטס: אני מבין, חשוב להבדיל בין בדיוק שתי יונים לבין לפחות שתי יונים. אז הניסוח צריך
להיות:
אם משבצים מאה ואחת יונים לתוך מאה תאים, אז יש תא אחד שיש בו שתי
יונים לפחות.
דיריכלה: זה עדיין לא מדוייק.
סוקרטס: למה?
דיריכלה: מה קורה אם אתה שם בתא אחד חמישים יונים, בתא אחר חמישים ואחת, ובכל
השאר אפס?
סוקרטס: אז עדיין יש תא עם לפחות שתי יונים. יש אפילו שני תאים כאלה.
דיריכלה: שני תאים זה לא תא אחד.
סוקרטס: אני מבין, חשוב להבדיל בין בדיוק שני תאים לבין לפחות שני תאים. אז הניסוח צריך
להיות:
אם משבצים מאה ואחת יונים לתוך מאה תאים, אז יש לפחות תא אחד שיש בו
לפחות שתי יונים.
דיריכלה: כן, עכשיו זה כבר נכון, אבל בכל זאת כדאי לשנות.
סוקרטס: למה?
דיריכלה: כי המשפט נכון לא רק ליונים ולתאים. הוא נכון גם לגרביים ולמגרות. הוא נכון באופן
כללי למחלקות ולעצמים.
סוקרטס: טוב, אז אתה רוצה שאני אנסח:
אם משבצים מאה ואחד עצמים לתוך מאה מחלקות, אז יש לפחות מחלקה אחת
שיש בה לפחות שני עצמים.
דיריכלה: זה יותר טוב, אבל האם זה נכון רק לגבי מאה ואחד עצמים?
סוקרטס: לא. ברור שאם יש עוד עצמים, המשפט עדיין נכון.
דיריכלה: אז איך תנסח עכשיו?
סוקרטס: הניסוח הנכון צריך להיות:
אם משבצים יותר ממאה עצמים לתוך מאה מחלקות, אז יש לפחות מחלקה אחת
שיש בה לפחות שני עצמים.
דיריכלה: והאם זה נכון רק לגבי 100, או לעוד מספרים?
סוקרטס: זה נכון לכל מספר של מחלקות. מספר המחלקות (אם יש מחלקות) הוא תמיד מספר
שלם וחיובי.
דיריכלה: ואנחנו מדברים רק על מספר סופי של מחלקות. מספר שלם וחיובי נקרא גם
מספר טבעי,
ונהוג לסמן אותו ב-n או ב-N, כקיצור למלה האנגלית natural.
סוקרטס: טוב אז אתה רוצה שאני אשנה את הניסוח למשהו כמו:
אם משבצים יותר מאשר N עצמים לתוך N מחלקות, אז יש לפחות מחלקה אחת
שיש בה לפחות שני עצמים.
דיריכלה: עכשיו תגיד לי, סוקרטס, מה קורה אם יש לך חמש פגישות בשבועיים?
סוקרטס: אז יהיו לי לפחות שלוש פגישות באותו שבוע.
דיריכלה: ואם יש לך עשרה אנשים המצביעים לשלוש מפלגות?
סוקרטס: אז לפחות למפלגה אחת יצביעו לפחות ארבעה אנשים.
דיריכלה: אתה יכול להתאים את עקרון שובך היונים למצבים שבהם רוצים להסיק
יותר מאשר שני עצמים במחלקה?
סוקרטס: כן, אתה מתכוון שאני אנסח כך:
אם N הוא מספר של מחלקות
ואם K הוא מספר טבעי אחר
ואם צריך לשבץ יותר מאשר N כפול K עצמים לתוך N מחלקות,
אז תהיה לפחות מחלקה אחת
אשר יהיו בה יותר מאשר K עצמים.
דיריכלה: בדיוק. זה עקרון שובך היונים.
סוקרטס: אז לכמה אנשים יש אותו מספר של שערות?
דיריכלה: תנסה לענות לבד.

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


חידות שובך לפותרים "כלים;"
<
רמה 1: במגרה יש גרבים כחולים, לבנים ואדומים. מכל צבע יש עם פסים ועם נקודות.
כמה גרבים יש להוציא עד שמקבלים זוג תואם?
רמה 1: בבית ספר יש 800 תלמידים. הוכח כי יש שלושה שנולדו באותו תאריך.
רמה 2: כמה צריחים, לכל היותר, אפשר להציב על לוח שחמט כך שאף צריח לא יאיים
על אף צריח אחר? הוכח שאי אפשר יותר.
רמה 3: וכמה מלכים?
רמה 3: וכמה רצים? (אני מכיר 4 פתרונות שונים)
רמה 5: הוכח שהדרך היחידה לשים את המספר המרבי של רצים על לוח שחמט בלי שאף אחד
יאים על אף אחד אחר היא כאשר כל הרצים נמצאים על ההקף.
רמה 5: (רצוי רקע אקדמי במתמטיקה) בעיית מציאת הצינור: צינור ישר אינסופי עובר מתחת
לאדמה וחותך עיגול יחידה נתון. יש למצוא את הצינור בחפירה חד ממדית קצרה ככל האפשר.
החפירה יכולה להיות עקומה ואיננה חייבת להיות קשירה. שאלת האורך המזערי פתוחה עדיין.
ידוע פתרון קטן מ-.8.4 מצא חסם תחתון לפתרון.

הפעם החידות שחיברתי כוללות גם חידות קשות במיוחד, ולכן לא אוסיף פרק נפרד של
חידות קשות.
המעוניינים בחידות נוספות (בכל הרמות) יוכלו למצוא אותן במקומות רבים, וביניהן:
org/dedel * באתר הבית שלי (בשלבי בניה מתקדמים):.ootips.wwwhttp://
* בספרו המצויין של בנו ארבל "אסטרטגיות לפתרון בעיות מתמטיות;",
בפרק 6.28) 5 חידות שובך).
* ברבעון אתגר- גליונות מתמטיקה, המוצא לאור על ידי הפקולטה למתמטיקה של הטכניון
והיחידה לפעולות נוער של מכון וייצמן. בגליונות ישנים היו מאמרים שלמים שהוקדשו
לחידות שובך, ובגליונות חדשים בדרך כלל יש כמה חידות שובך.


אתר הבית של עודד לבנה