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

הוכיחו כי בין כל שישה מספרים שלמים תמיד נוכל למצוא שני מספרים שההפרש ביניהם יתחלק ב-5 ללא שארית. האם הטענה תישאר נכונה עבור סכום?
אני די בטוח שצריך להשתמש בעקרון שובך היונים אבל לא בטוח כיצד.
אשמח לעזרה עם השאלה הנ"ל :slight_smile:

נדמיין שיש לפנינו את ישר המספרים השלמים.
הגדרה: בהנתן מספר שלם 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:

\begin{align*} &a_{i}=5\cdot k_{1}+r_{1},\,\,\,(0\leq r_{1}\leq4)\\&a_{j}=5\cdot k_{2}+r_{2},\,\,\,(0\leq r_{2}\leq4)\\&a_{i}\ne a_{j} \end{align*}

נתבונן בהפרש בין המספרים:

\begin{align*} a_{i}-a_{j}&=(5\cdot k_{1}+r_{1})-(5\cdot k_{2}+r_{2})\\&=5\cdot(k_{1}-k_{2})+(r_{1}-r_{2}) \end{align*}

מאחר ומתקיים r_{1}\neq r_{2}, אז ברור כי r_{1}-r_{2}\neq0. לכן, נוכל להסיק כי ההפרש בין כל שני מספרים כאלה לא מתחלק ב-5, בסתירה לנתון.

ב. נוכיח כי אם לכל המספרים אותה שארית בחלוקה ב-5 אז ההפרש בין כל שני מספרים מתחלק ב-5. נסמן את המספרים הבאים:

\begin{align*} &a_{1}=5\cdot k_{1}+r\\&a_{2}=5\cdot k_{2}+r\\&\vdots\\&a_{n}=5\cdot k_{n}+r \end{align*}

ואז ההפרש בין כל שני מספרים יהיה:

\begin{align*} a_{i}-a_{j}&=(5\cdot k_{i}+r)-(5\cdot k_{j}+r)\\&=5\cdot(k_{i}-k_{j}) \end{align*}

לכן, נוכל להסיק כי 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.