הוכיחו כי בין כל שישה מספרים שלמים תמיד נוכל למצוא שני מספרים שההפרש ביניהם יתחלק ב-5 ללא שארית. האם הטענה תישאר נכונה עבור סכום?
אני די בטוח שצריך להשתמש בעקרון שובך היונים אבל לא בטוח כיצד.
אשמח לעזרה עם השאלה הנ"ל
נדמיין שיש לפנינו את ישר המספרים השלמים.
הגדרה: בהנתן מספר שלם i נסמן ב-[i]_5 את קבוצת כל המספרים שאם הם יהיו חלק מהשישייה, אזי הפרש בינם ובין i יותיר כפולה של 5. נשים לב שמתקיים [i]_5=\{i+5k \ | \ k\in \mathbb{Z}\}.
לדוגמא עבור i=1 נקבל שכל אחד מהמספרים 1,6,11,16,21,... וכמובן גם -4,-9,-14,... הם מספרים שאם יהיו חלק מהשישייה יהיה לנו הפרש כנ"ל.
נשים לב, המספרים האלה בעלי מכנה משותף, כולם שווים ל-1 מודולו 5. זו למעשה מחלקת שקילות מודולו 5. אם יהיו לנו שני מספרים מהשישייה השייכים למחלקת השקילות הזו, ההפרש יתחלק ב-5 כצפוי.
כעת, אנחנו יודעים שיחס השקילות מודולו 5 מחלק את השלמים ל-5 מחלקות שקילות – המחלקות של שארית 0,1,2,3 ו-4 מודולו 5. אנחנו יודעים שיש לנו שישה מספרים, שניים חייבים ליפול באותה מחלקת שקילות.
אשמח להוסיף נקודת מחשבה טיפה שונה לפתרון (המעולה) של @lambda.
לפני שניגש אל השאלה, נוכיח טענה עזר אשר תעזור לנו בפתירתה:
טענה עזר: עבור המספרים a_{1},...,a_{n} - ההפרש בין כל שניים, מתחלק ב-5 אם"ם לכל המספרים אותה שארית בחלוקה ב-5.
הוכחה - נפריד לכיוונים:
א. נוכיח כי אם ההפרש בין כל שני מספרים, מתחלק ב-5 אז לכל המספרים אותה שארית בחלוקה ב-5.
נניח בשלילה כי בין כל המספרים קיימים שניים אשר להם שארית שונה בחלוקה ב-5:
נתבונן בהפרש בין המספרים:
מאחר ומתקיים r_{1}\neq r_{2}, אז ברור כי r_{1}-r_{2}\neq0. לכן, נוכל להסיק כי ההפרש בין כל שני מספרים כאלה לא מתחלק ב-5, בסתירה לנתון.
ב. נוכיח כי אם לכל המספרים אותה שארית בחלוקה ב-5 אז ההפרש בין כל שני מספרים מתחלק ב-5. נסמן את המספרים הבאים:
ואז ההפרש בין כל שני מספרים יהיה:
לכן, נוכל להסיק כי a_{i}-a_{j} אכן מתחלק ב-5.
הצלחנו להוכיח את טענת העזר.
עתה נחזור לשאלה עצמה. נסמן ב-x_{i}\in\mathbb{Z} את ששת המספרים השונים (כאשר 1\leq i\leq6). משתמש בטענת העזר שהוכחנו - הפרש בין כל זוג מספרים, מתחלק ב-5 אם"ם שני המספרים בעלי אותה שארית בחלוקה ב-5. נסמן את המספרים כשיונים ואת שארית החלוקה ב-5 כשובכים. לכן ע"פ עקרון שובך היונים המוכלל נקבל כי לפחות \lceil\frac{6}{5}\rceil=2 מספרים עם אותה שארית. כלומר לפחות 2 מספרים שההפרש ביניהם מתחלק ב-5 ללא שארית.
הטענה לא נכונה עבור סכום של שני מספרים. לדוגמא אם שארית החלוקה של כל אחד מששת המספרים, ב-5, היא 1, אז שארית החלוקה של סכום כל שניים מהם ב-5 היא 2.