נושאים לתרגול

עקרון שובך היונים - גירסת הדפסה




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


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

נתחיל בדוגמה מובנת מאליה:
בכתה א' יש 13 ילדות. הוכיחי כי יש שתי ילדות שחוגגות יום הולדת באותו חודש.
פתרון: בשאלה זו היונים הם הילדות, ותאי השובך הם חדשי השנה. "יונה" (כלומר ילדה) נכנסת ל"תא" (כלומר חודש) אם היא נולדה בחודש זה. מכיוון שיש 13 יונים ורק 12 תאים נובע מעקרון שובך היונים שיש שתי יונים באותו תא, כלומר שתי ילדות שנולדו באותו חודש.
כנראה שאת השאלה הקודמת לא היינו מתקשות לפתור גם בלי להכיר את עקרון שובך היונים… הבה נתבונן כעת בשאלה נוספת, שבה עצם הידיעה כי מומלץ להשתמש בעקרון שובך היונים מהווה חצי מהדרך אל הפתרון:
הוכיחי כי קיימות שתי חזקות של 2 (כלומר שני מספרים מהצורה 2i ו-2j ) שהפרשן מתחלק ב-37.
פתרון: נגדיר קבוצת "יונים" בתור המספרים {238, … , 22, 21}. תאי השובך יהיו המספרים שהם כל השאריות האפשריות בחלוקה ב-37. נכניס "יונה" ל"תא" נתון אם השארית שלה בחלוקה ב-37 היא המספר המתאים לתא. מכיוון שיש 38 יונים ורק 37 תאים, נובע מעקרון שובך היונים שיש (לפחות) שתי יונים באותו תא. כלומר, מצאנו שתי חזקות של 2 שנותנות אותה שארית בחלוקה ב-37. לפיכך, הפרשן מתחלק ב-37.
לעיתים, נדרשת יותר יצירתיות בהגדרת תאי השובך והיונים. נתבונן למשל בשאלה הבאה
הוכיחי כי אם בוחרים 7 מספרים שונים בין 1 ל-12, בהכרח יהיו שניים מתוכם שסכומם שווה ל-12.
פתרון: נגדיר את תאי השובך להיות 6 הקבוצות הבאות:

היונים יהיו שבעת המספרים שבחרנו. מכיוון שיש 7 יונים ו-6 תאים, נובע מעקרון שובך היונים שיש שתי יונים באותו תא, כלומר שני מספרים מאותה קבוצה. סכומם של שני המספרים הללו הוא 12. (שימי לב כי נתון שהמספרים שבחרנו שונים זה מזה.)

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



עקרון שובך היונים המוכלל קובע כי אם בשובך קיימים n תאים, ואנו מכניסים לתוכו לפחות m יונים ,
הרי שבהכרח קיים תא שבו תהיינה לפחות יונים. (כאשר מסמן עיגול כלפי מעלה).

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

נחלק את המשולש, כמו בשרטוט, לארבעה משולשים שווי צלעות עם אורך צלע 1. היונים יהיו 9 הנקודות, ותאי השובך יהיו ארבעת המשולשים הקטנים. כניסת יונה לשובך, משמעותה שהנקודה המתאימה ליונה נמצאת בתוך המשולש הקטן המתאים לתא השובך. מכיוון שיש 9 יונים ו-4 תאים, נובע מעקרון שובך היונים המוכלל כי קיים תא שבו נמצאות לפחות יונים, כלומר קיים משולש קטן שיש בו לפחות 3 נקודות. המרחק בין כל שתיים מתוך אותן 3 נקודות הוא אכן קטן או שווה אחד (שהרי שלושתן כלואות בתוך משולש שווה צלעות שאורך צלעו 1), ולכן שלוש נקודות אלו יוצרות את המשולש המבוקש בשאלה.



תרגיל 1


א. בציור שלפנייך שריג 3x7.
(נקודות שריג הן נקודות במישור, ששני השיעורים שלהן הם מספרים שלמים. קווי השריג מקבילים לצירים.)


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

התבונני בשורה העליונה והסיקי מעקרון שובך היונים כי יש בה 4 נקודות באותו צבע. המשיכי להתבונן מה קורה בארבע העמודות המתאימות לנקודות הללו.


תחילה נתבונן בשורה העליונה ונרצה להראות כי יש בה (לפחות) ארבע נקודות הצבועות באותו צבע. ואכן, נגדיר את תאי השובך להיות הצבעים כחול ואדום, והיונים תהיינה שבע הנקודות שבשורה העליונה. כניסה של יונה לתא מסויים בשובך משמעותה שהנקודה המתאימה ליונה צבועה בצבעו של התא. לפי עקרון שובך היונים המוכלל קיים תא המכיל לפחות 4= יונים, כלומר יש לפחות 4 נקודות הצבועות באותו צבע. נוכל להניח בלי הגבלת הכלליות (בה"כ)* כי צבע זה הינו האדום.
*המושג "בלי הגבלת הכלליות" או בקיצור "בה"כ", שימושי מאד בניסוח הוכחות מתמטיות, במקרים שבהם קיימות לכאורה מספר אפשרויות שיש לנתח כל אחת מהן בנפרד, אולם למעשה מספיק לבחור שרירותית רק אפשרות אחת ולנתח רק אותה, מכיוון שכל יתר המקרים בעצם זהים לאותו מקרה שנבחר, בשינוי שמות. לדוגמה, אצלנו הגענו למסקנה כי יש בשורה העליונה ארבע נקודות הצבועות באותו צבע. אנחנו יכולים להניח בה"כ כי צבע זה הוא אדום ולהמשיך מכאן ואילך את ההוכחה תחת ההנחה הזו. לכאורה היה עלינו לבדוק עוד מקרה – אילו הצבע המופיע ארבע פעמים הוא כחול, ולהמשיך שוב את ההוכחה תחת ההנחה הזו, אבל ברור ששתי השיטות יתנו את אותה הוכחה אם נחליף כל מופע של המילה "אדום" ב"כחול" ולהיפך. לפיכך ההנחה כי כל ארבע הנקודות שוות הצבע הן דווקא אדומות אינה מגבילה את כלליות ההוכחה והיא מותרת.

נקודה למחשבה: האם לאחר שהנחנו בלי הגבלת הכלליות כי יש בשורה העליונה ארבע נקודות אדומות, נוכל באותו אופן להניח בה"כ כי גם בשורה האמצעית יש ארבע נקודות אדומות?
התשובה היא לא. לא נוכל בשלב זה להניח בנוסף כי גם בשורה השניה יש ארבע נקודות אדומות. אמנם, מאותו שיקול שהפעלנו בשורה העליונה, יש בשורה השניה ארבע נקודות שוות צבע, אולם כרגע ההנחה כי צבע זה הוא דווקא אדום תגביל את הכלליות: אם נניח הנחה נוספת זו, ונמשיך את הפתרון בשני אופנים – פעם בהנחה שהצבע בשורה השניה הוא כחול ופעם בהנחה שהצבע בשורה השניה הוא אדום, שני הפתרונות לא יהיו "העתק הדבק" של אותה הוכחה בהחלפת שמות הצבעים, מכיוון שאלו שני מקרים שונים- בפעם האחת יש בשתי השורות יחד 8 קדקודים מאותו צבע, ובפעם השניה יש 4 מצבע אחד ו-4 מצבע אחר... הסכמנו בינתיים כי בשורה העליונה יש ארבעה קדקודים אדומים. מכאן ואילך נתבונן רק בארבע העמודות המתאימות לאותם קדקודים. אם בשורה השניה או השלישית יש בשתיים מתוך ארבע העמודות הללו קדקודים אדומים נקבל מלבן אדום וסיימנו. אחרת, באותן 4 עמודות יש גם בשורה השניה וגם בשלישית לפחות שלושה קדקודים כחולים. במקרה זה נקבל מלבן כחול. (כי בשורה השניה יש מתוך ארבע העמודות רק אחת ש(אולי) לא מופיע בה כחול, וכן בשורה השלישית, ולכן בכל מקרה נשארו לנו לפחות שתי עמודות שבהן גם בשורה השניה וגם בשורה השלישית מופיע צבע כחול וכך נוצר מלבן כחול).

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



ב. בציור שלפנייך שריג 4x6. גם את נקודות שריג זה צובעים בשני צבעים, כחול או אדום. האם בכל צביעה כזו מובטח מלבן שכל קדקודיו שווי צבע? אם התשובה חיובית, ספקי הוכחה. אם התשובה שלילית, תני דוגמה לצביעה מתאימה של 24 נקודות השריג, שבה אין מלבן שכל קדקודיו צבועים באותו צבע.


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


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

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

נתבונן בשורה העליונה וננחש כי שלושת הכחולים הם שלושת הימניים. [גם עם ניחושים אחרים ניתן להתקדם באופן דומה, אולם, כזכור, אנחנו מחפשים כאן רק דוגמה אחת מני רבות.] בשום שורה אחרת לא ייתכן כעת ששלושת הכחולים הם שלושת השמאליים. (שהרי במקרה כזה נתבונן בשורה הנותרת, ובה יהיו או שני כחולים בשלוש העמודות הימניות ("בחצי הימני"), או שני כחולים בשלוש העמודות השמאליות ("בחצי השמאלי") ואז ייווצר מלבן כחול).

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

קל לבדוק שבדוגמא שקיבלנו אכן אין מלבן חד צבעי.


תרגיל 2


א. נתון לוח משבצות מלבני, ונתונות אבני דומינו 2x1, שכל אחת מהן מכסה בדיוק שתיים משבצות סמוכות על הלוח. כיסוי של הלוח הוא הנחת אבני הדומינו כך שכל משבצת מכוסה על ידי אבן דומינו אחת בדיוק ואבני הדומינו אינן חורגות מהלוח. בסרטוט שלפנייך מתואר כיסוי של לוח 3x4. ומתחתיו לוח זהה שבו מסורטטים קטעים מתאימים המחליפים את אבני הדומינו.



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

א. הראי שכל כיסוי של לוח 3x4 ניתן לפיצול לשני לוחות מלבניים.

לסעיף זה אפשר לתת פתרון או על-ידי בניה ישירה וחלוקה למקרים, או על-ידי שיקול יצירתי קצת יותר (ובתמורה גם יותר קצר). נציג כאן את שני הפתרונות.
נתבונן בשורה העליונה של כיסוי כלשהו של 3x4.

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


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


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

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

א. אבן מאוזנת בקצה:



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

ב. אבן מאוזנת במרכז


במקרה זה חייבות שתי המשבצות שמתחת לאבן המאוזנת להיות מכוסות על ידי אבן מאוזנת נוספת (אחרת תיוותרנה בשורה התחתונה משבצות בודדות שאינן מכוסות), ושוב פיצלנו את שתי השורות העליונות מן התחתונה.


נניח שהצלחנו ליצור כיסוי שאינו ניתן לפיצול. מכאן אפשר להסיק כי כל קו אורך פנימי של הלוח, מופרד באחת משורותיו על ידי אבן מאוזנת. היות ושיש שלושה קווי אורך, מספר האבנים המאוזנות הוא לפחות 3. מצד שני לו הייתה שורה שמכוסה רק על ידי אבנים מאוזנות, הלוח היה מפוצל. אם כך אנחנו במצב שבכל שורה יש אבן מאוזנת ושתי אבנים מאונכות. האבנים המאונכות שבשורה התחתונה שונות בהכרח מהאבנים המאונכות בשורה העליונה. לכן חייבות להיות לפחות 4 אבנים מאונכות. ובסך הכול לפחות 7 אבנים שונות. אך 7 אבנים מכסות 14 משבצות בה בשעה שבלוח זה 12 משבצות בלבד.
אפשר לנסח את הטיעון האחרון כשיקול שובך יונים:
תאי השובך יהיו 12 המשבצות בלוח והיונים תהיינה כל משבצת שאבן כלשהי מכסה (כלומר – היונים מגיעות בזוגות, כל אבן דומינו מייצגת שתי יונים). יש לנו 14 יונים המגיעות משבע אבני דומינו. מכיוון שיש 14 יונים ורק 12 תאים בשובך נובע שיהיה תא ובו שתי יונים בסתירה לכלל הכיסוי הנתון בשאלה.


ב. הוכיחי כי כל כיסוי של לוח 6x6 ניתן לפיצול.
נתבונן בלוח 6x6: נניח שמצאנו כיסוי שלו שלא ניתן להפרדה, ונתבונן בשורה העליונה של אותו כיסוי. חלק מהאבנים באותה שורה הן מאוזנות, וחלק מאונכות. אם כולן מאוזנות, הרי לכם הפרדה של השורה הראשונה מכלל הלוח - בסתירה, אם כולן מאונכות זו תהיה הפרדה של שתי השורות הראשונות מכלל הלוח, שוב בסתירה. לפיכך חלק מהאבנים הן מאוזנות, וחלק- מאונכות. מספר המאונכות הוא זוגי, כי לאחר כיסוי על ידי המאוזנות, נותר מספר זוגי של משבצות לא מכוסות. כלומר מהשורה הראשונה יוצאות לפחות שתי אבנים מאונכות.
נתבונן עתה בשורה השנייה. שוב לא ייתכן שהמשבצות שעדיין אינן מכוסות בה תכוסינה רק על ידי אבנים מאוזנות- כי ככה תהיינה מופרדות שתי השורות העליונות מהיתר. לפיכך גם ממנה יוצאות אבנים מאונכות כלפי מטה, מספרן זוגי ולפיכך הוא לפחות שתיים.
נמשיך הלאה באתו אופן ונקבל כי מכל אחת מחמש השורות העליונות חייבות לצאת לפחות שתי אבנים מאונכות כלפי מטה. לכן מספר האבנים המאונכות הוא לפחות 2x5=10.
משיקול סימטרי – אם מתבוננים בעמודות, מספר האבנים המאוזנות (שהן המאונכות כשהעמודות הופכות לשורות) גם הוא לפחות 10. כלומר כדי שהלוח יהיה לא ניתן להפרדה, נזדקק לכל הפחות ל- 20 אבנים. אבל לוח 6x6 מכוסה כולו על ידי 18 אבנים בלבד!
גם כאן אפשר לנסח את הטיעון האחרון כשיקול שובך יונים:
תאי השובך יהיו 36 המשבצות בלוח והיונים תהיינה כל משבצת שאבן כלשהי מכסה (כלומר – היונים מגיעות בזוגות, כל אבן דומינו מייצגת שתי יונים). יש לנו 20 יונים המגיעות מאבנים מאוזנות ו-20 יונים המגיעות מאבנים מאונכות, ובסה"כ 40 יונים.
מכיוון שיש 40 יונים ורק 36 תאים בשובך נובע שיהיה תא ובו שתי יונים בסתירה לכלל הכיסוי הנתון בשאלה.


ג. לפנייך לוח מלבני 8x6, ציירי כיסוי שלו שלא ניתן לפיצול.




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

הערה: לאור ההוכחה של סעיף ב', אנו יודעים כי בכיסוי שלא ניתן לפיצוי יש צורך בלפחות 7x2 אבנים מאונכות (להפריד את שבעת הקווים המאוזנים הפנימיים) ולפחות 5x2 אבנים מאוזנות (להפריד את חמשת הקווים המאונכים הפנימיים) כלומר יש צורך בלפחות 24 אבני דומינו. כדי לכסות לוח 6x8 יש צורך ב-24 אבני דומינו בדיוק. לכן, בכיסוי שלא ניתן לפיצול, חייב כל קו מאוזן להיחתך בדיוק על ידי שתי אבנים מאונכות, וכל קו מאונך בדיוק על ידי שתי אבנים מאוזנות. תובנה זו מסייעת לבנות דוגמאות.


תרגיל 3


א. הוכיחי כי לכל בחירה של 50 מספרים שלמים שונים בין 1 ל- 99, קיימים שניים מתוכם הזרים זה לזה (שני מספרים ע שלמים הם זרים, אם אין להם גורם משותף הגדול מ-1).
טפלי במספר 1 בנפרד, וביחס לכל יתר המספרים נסי למצוא שיקול שובך יונים.


אם בין 50 המספרים בחרנו את המספר 1, סיימנו - כי 1 זר לכל המספרים. נמשיך בהנחה ש-1 לא נבחר, ונחלק את 98 המספרים שבין 2 ל-99 לארבעים ותשע קבוצות: בקבוצה הראשונה המספרים 2 ו- 3, בקבוצה השנייה המספרים 4 ו- 5, וכן הלאה. בסה"כ נקבל 49 קבוצות שהן תאי השובך, ואילו היונים תהיינה 50 המספרים שאנו בוחרים. מעקרון שובך היונים קיים תא ובו שתי יונים – כלומר יש קבוצה שממנה נבחרו שני מספרים. שני מספרים אלו הם שונים (לפי כלל הבחירה הנתון בשאלה) ומהיותם באותה קבוצה נובע שהם עוקבים, ומספרים עוקבים הם תמיד זרים זה לזה.


ב. תני דוגמה ל- 50 מספרים שלמים שונים בין 1 ל- 100, כך שלכל שניים מתוכם יש גורם משותף גדול מ-1. הראי ח כי זו הדוגמה היחידה הקיימת.
נחלק את המספרים 1 – 100 לחמישים זוגות: הזוג הראשון יכיל את המספרים 1 ו-2, הזוג השני את 3 ו- 4 וכו'. כדי שלא יהיו בתוך חמישים המספרים שניים זרים, יש לבחור בדיוק אחד מכל זוג. את המספר 1 אי אפשר לבחור בהיותו זר לכל מספר אחר, לכן בהכרח מהזוג הראשון נבחר את 2. משבחרנו את 2, אי אפשר לבחור את 3 העוקב לו, וצריך מהזוג השני לבחור דווקא את 4, וכך הלאה. כך בעצם מאלצת אותנו המגבלה לבחור את קבוצת חמישים הזוגיים.


ג. וכיחי כי בכל בחירה של 50 מספרים שלמים שונים בין 1 ל- 98, קיימים שניים מתוכם כך שהאחד מחלק את האחר.
נסי קודם לפתור את סעיף ד (הקל יותר) ואולי בהשראתו תקבלי רעיון…


נגדיר את תאי השובך בתור הזוגות (x,2x) כאשר . היונים יהיו 50 המספרים הנבחרים. יונה נכנסת לתא מסויים אם היא אחד משני המספרים בזוג שהתא מייצג. (נשים לב כי כאן יונה אחת יכולה להיכנס לשני תאים אבל זה לא מפריע לפעולתו של עקרון שובך היונים. אפשר לחילופין להחליט שבמידה ויונה שייכת לשני תאים היא תיכנס רק לאחד מהם על-ידי בחירה שרירותית.) מכיוון שיש 50 יונים ורק 49 תאים נובע שיש תא המכיל (לפחות) שתי יונים. היונים הללו מייצגות מספרים שונים (כי לפי נתוני השאלה המספרים הנבחרים שונים זה מזה) ולכן אחד מהם הוא כפולת 2 של השני.


ד.האם בכל בחירה של 50 מספרים שלמים שונים בין 1 ל- 99, יש בהכרח שני מספרים, שאחד מהם מחלק את האחר? אם כן - הוכיחי, אם לא - תני דוגמא נגדית מפורשת.
לא, כי אפשר לקחת את כל המספרים מ-50 עד 99. אף אחד איננו כפולת 2 של האחר, ובוודאי לא כפולה שאל האחר במספר גדול מ-2.
הערה: פתרון זה מהווה השראה לפתרון סעיף ג', מכיוון שהוא רומז שאם ניקח אפילו מספר אחד יותר (כלומר 50 מספרים במקום 49) כבר יהיו בקבוצה שני מספרים שהאחד הוא כפולת 2 של השני.


תרגיל 4


נתון לוח שח רגיל. רושמים בכל אחת מ- 64 המשבצות שלו את אחד המספרים 0 או 1. אחר כך מסכמים את המספרים בכל שורה, בכל עמודה ובשני האלכסונים הראשיים. מתקבלת רשימה של 18 מספרים.
הוכיחי כי ברשימה זו, יש מספר החוזר לפחות שלוש פעמים.
נסי להתחיל בהפעלת עקרון שובך היונים. אמנם הוא לא יספק תשובה מיידית, אך תוכלי לקבל באמצעותו תובנות שיאפשרו לצמצם את הפתרון לבחינת מספר לא גדול של מקרים.


נפעיל תחילה את עקרון שובך היונים. תאי השובך יהיו הסכומים האפשריים בשורה / עמודה / אלכסון, והיונים תהיינה השורות, העמודות והאלכסונים. יש לנו 9 תאים ו-18 יונים אבל כאן עקרון שובך היונים מאפשר לנו רק להסיק שיש שובך עם 2 יונים כלומר סכום שמופיע פעמיים.

נשים לב שהמקרה היחיד אותו עלינו לבחון הוא המקרה שבו כל סכום מופיע בדיוק פעמיים, כלומר שבכל תא יש בדיוק 2 יונים. (שהרי בכל מקרה אחר יהיה תא עם לפחות 3 יונים וזה כבר יסיים את פתרון השאלה). מכאן ואילך נניח שבכל תא יש בדיוק 2 יונים, כלומר שכל סכום מופיע בדיוק פעמיים. נרצה להראות שאפשרות זו לא תיתכן.

נשים לב לשני ערכים מיוחדים של סכומים: 0 ו-8. הסכום 0 יכול להתקבל רק כסכום של שמונה אפסים, והסכום 8 רק כסכום של שמונה 1-ים. הסכום 0 לא יכול להופיע בשום אלכסון (שהרי אז הסכום 8 לא יופיע בשום שורה ובשום עמודה, אולי רק באלכסון השני, אבל הרי הוא צריך להופיע פעמיים!...) ומסיבה דומה גם הסכום 8 לא יופיע בשום אלכסון.
בנוסף, נשים לב שאם הסכום 0 מתקבל באיזו שורה, אז הסכום 8 לא יתקבל בשום עמודה. לכן נניח בלי הגבלת הכלליות (בה"כ)* כי הסכום 0 מתקבל בשורה, לכן שני סכומי ה-8 מתקבלים גם-כן בשורה, ולפיכך סכום האפס השני מתקבל גם הוא בשורה.
*המושג "בלי הגבלת הכלליות" או בקיצור "בה"כ", שימושי מאד בניסוח הוכחות מתמטיות, במקרים שבהם קיימות לכאורה מספר אפשרויות שיש לנתח כל אחת מהן בנפרד, אולם למעשה מספיק לבחור שרירותית רק אפשרות אחת ולנתח רק אותה, מכיוון שכל יתר המקרים בעצם זהים לאותו מקרה שנבחר, בשינוי שמות. לדוגמה, אצלנו הגענו למסקנה כי יש בשורה העליונה ארבע נקודות הצבועות באותו צבע. אנחנו יכולים להניח בה"כ כי צבע זה הוא אדום ולהמשיך מכאן ואילך את ההוכחה תחת ההנחה הזו. לכאורה היה עלינו לבדוק עוד מקרה – אילו הצבע המופיע ארבע פעמים הוא כחול, ולהמשיך שוב את ההוכחה תחת ההנחה הזו, אבל ברור ששתי השיטות יתנו את אותה הוכחה אם נחליף כל מופע של המילה "אדום" ב"כחול" ולהיפך. לפיכך ההנחה כי כל ארבע הנקודות שוות הצבע הן דווקא אדומות אינה מגבילה את כלליות ההוכחה והיא מותרת.
עד כה הסקנו שיש שתי שורות מלאות אפסים ושתי שורות מלאות אחדות.

כעת, הערכים 1 ו-7 לא יכולים להתקבל בשום עמודה (כי בכל עמודה כבר יש שני 0-ים ושני 1-ים). לכן יש עוד שתי שורות שסכומן 7 ושתי שורות שסכומן 1. בכל אחת מהשורות הללו יש שבעה מקומות זהים ושני מקומות "יוצאי דופן". המקומות של יוצאי הדופן בכל ארבע השורות יחד תופסים לכל היותר 4 עמודות. לכן 4 העמודות האחרות הן זהות לחלוטין. כלומר – קיבלנו שיש 4 עמודות זהות, דהיינו סכום שמופיע 4 פעמים, בסתירה להנחה שכל סכום מופיע בדיוק פעמיים.

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

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


תרגיל 5


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


המספרים הטבעיים מתחלקים לשלוש מחלקות לפי השארית שהם נותנים בחלוקה ב-3. אם בוחרים חמישה מספרים ישנן שתי אפשרויות:
1. בכל מחלקת שארית יש לפחות איבר אחד של הקבוצה - ניקח מספר אחד מכל מחלקה ונקבל שלושה מספרים שסכומם מתחלק ב-3. (שהרי סכום השאריות של שלושת המספרים הוא 3 ולכן סכום שלושת המספרים עצמם מתחלק ב-3).

2. יש מחלקה שאף מספר בקבוצה אינו נמצא בתוכה. לכן חמשת המספרים מתחלקים בין שתי מחלקות. לפיכך, אם שתי המחלקות הן תאי השובך והמספרים הנבחרים הם היונים (יונה נכנסת לתא אם המספר המתאים ליונה שייך למחלקת השארית המתאימה לתא), הרי שמעקרון שובך היונים המוכלל נובע שיש מחלקה שבה יש לפחות מספרים. סכומם של מספרים אלו מתחלק ב-3. (כי סכום השאריות שלהם בחלוקה ב-3 הוא 0+0+0 או 1+1+1 או 2+2+2.)
ג. תני דוגמה לקבוצה של ארבעה מספרים טבעיים, כך שסכום של כל שלושה מהם אינו מתחלק ב-3.
היעזרי בדרך הפתרון של סעיף ב'.


כפי שפירטנו בסעיף ב', אילו בין ארבעת המספרים הנבחרים היה נציג מכל מחלקת שארית, הרי שהיו שלושה שסכומם מתחלק ב-3. כמו-כן, אילו היו שלושה מספרים נבחרים באותה מחלקת שארית, הרי שגם אז סכום שלושתם היה מתחלק ב-3. לפיכך, עלינו לבחור שני מספרים ממחלקה אחת ושני מספרים ממחלקה אחרת. (למעשה כל בחירה כזו תהיה טובה). לדוגמה: 0,3,1,4.
ד. הסיקי מהסעיפים הקודמים, כי בכל בחירה של 11 מספרים טבעיים, יש תמיד שישה מתוכם, שסכומם מתחלק ב- 6.
בפתרון סעיף זה יש להיעזר בטענות שהוכחת בסעיפים א-ב.


על פי סעיף ב' בכל קבוצה בת 11 מספרים יש שלושה מתוכם שסכומם מתחלק ב-3. נשים אותם בצד, נשארה קבוצה בת 8 מספרים טבעיים, ושוב על פי ב', יש שלושה מתוכם שסכומם מתחלק ב-3. נשים גם קבוצה זו בצד. נותרו חמישה מספרים, ושוב - יש שלושה מתוכם שסכומם מתחלק ב-3. קיבלנו שלוש קבוצות בנות שלושה מספרים, שסכום המספרים בכל אחת מהן מתחלק ב-3. מתוך שלושה סכומים אלו, יש (על פי סעיף א') שניים מאותה זוגיות. בשתי הקבוצות המתאימות גם יחד יש שישה מספרים, וסכומם מתחלק ב-3 וב-2, לכן מתחלק ב-6.
ה. השלימי את הניסוח הבא (ללא הוכחה): בכל בחירה של 2n-1 מספרים, יש n מתוכם שסכומם מתחלק ב-n.
מסעיפים א', ב', ד' נוכל לנחש כי: בכל בחירה של 2n-1 מספרים, יש n מתוכם שסכומם מתחלק ב-n. (הוכחת טענה זו קשה משמעותית מההוכחות של המקרים הפרטיים בסעיפים הקודמים ולא נציג אותה פה. זהו, למעשה, משפט מתימטי ידוע – משפט ארדש גינזבורג-זיו, וניתן לעיין בהוכחתו בקישור הבא: https://uniformlyatrandom.wordpress.com/2009/01/25/the-erdos-ginzburg-ziv-theorem/)
ו. השלימי את הניסוח הבא (ללא הוכחה): בכל בחירה של 2n-1 מספרים, יש n מתוכם שסכומם מתחלק ב-n.
לכל n ניקח קבוצה אחת של n-1 מספרים המתחלקים ב-n, וקבוצה שניה של n-1 מספרים הנותנים שארית 1 בחלוקה ב-n. בכל בחירה של n מתוכם יש בין 1 ל n-1 מספרים מהקבוצה האחת ובין 1 ל n-1 מספרים מהקבוצה השניה. השארית של סכום כל המספרים בחלוקה ב-n היא בדיוק כמות המספרים השייכים לקבוצה השניה (כי כל אחד מהם "תורם" שארית 1 ואילו כל מספר מהקבוצה הראשונה "תורם" שארית 0). לפיכך השארית של סכום המספרים בחלוקה ב-n היא בין 1 ל-n-1, ובפרט אינה מתחלקת ב-n.


מערכת האולפניאדה - החוג למתמטיקה ת.ד. 16078, בית וגן ירושלים, 91160 טלפון: 02-6750949 פקס: 02-6750950 דוא"ל: ulpaniada@michlalah.edu