שובך היונים

white shadow 3

New member
שובך היונים

הי, אחר הצהריים טובים.
שאלה שלדעתי הופיע באחת האולימפיאדות למתמטיקה...

לפוליטיקאי נותרו 50 ימים עד לבחירות. הוא מתכנן בכל יום לבצע לפחות נאום אחד, ולא יותר מ-75 נאומים בסה"כ.
הוכח כי קיימת סדרה של ימים בהם נאם בדיוק 24 נאומים.

אז ממה שיצא לי להבין:
מגדירים yi = מספר הנאומים שנאם עד היום ה-i.
בונים סדרה 1:
1<=y(1)<y(2)<y(3)<...<y(50)
וסדרה שניה:
y(1)+24<y(2)+24<...<y(50)+24

בסדרה הראשונה אנחנו יכולים לקבל מספרים מ-1 עד 75 בכל אחד מה-yi-ים
בסדרה השניה אנחנו יכולים לקבל מספרים מ-25 עד 99 בכל אחד מה-yi-ים
לכן אם נפזר 100 יונים (כל ה-yi-ים) ל-99 מספרים אפשרים נקבל שיש לפחות 2 באותו תא.
עכשיו, ברור שלא יתכן כי 2 היונים האלה הם מאותה סדרה בגלל אי השיוויון החזק בין האיברים, ולכן איבר אחד הוא מהסדרה הראשונה והאיבר השני הוא מהסדרה השניה, כלומר עבור i כלשהוא ו-j כלשהוא שעבורם
j<i
ו-
zz y(i)=y(j)+24 zz

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

עריסטו

Active member
הסבר

אם y(i)=y(j)+24 אז בסדרת הימים שמתחילה ביום j+1 ומסתיימת ביום i הפוליטיקאי נאם 24 נאומים.
 

white shadow 3

New member
הבנתי, תודה רבה. שאלה קטנה נוספת

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

* יש להוכיח כי קיים מספר N המורכב אך ורק מספרות של 1, ומתחלק ללא שארית ב-n טבעי שאינו מתחלק ב-5 והוא אי זוגי

מה שהם עשו זה לקחת סדרה של n+1 איברים:
zz 1,11,111,1111,...,,,,11111..11111 zz
ואז אם נחלק n+1 מספרים ל-n תאי שאריות שמתקבלות בחלוקה ב-n, אז נקבל לפחות 2 מספרים עם אותה שארית.
מכאן שאם נחסר בין 2 המספרים האלה נקבל מספר שמתחלק ב-n ללא שארית
מה שלא הבנתי זה את ההמשך:,
נניח כי המספר הראשון הוא עם n אחדות, והמספר השני עם k אחדות, כך שנניח n קטן מ-k.
אם נחסר בניהם נקבל מספר מהצורה:
zz 111...111100..0000 zz כך שיש לנו n-k אחדות ו-k אפסים.

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

(שלא נדבר על המקרה בו N=1 ו-n=1 ואז N מתחלק ב-n ללא שארית, ו-n אי זוגי ולא מתחלק ב-5..והוכחנו כי קיים N המקיים את התנאים..)
תודה!
 

עריסטו

Active member
למה אתה עוצר באמצע ההוכחה?

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

white shadow 3

New member
כי לא כתוב על זה בהמשך..ההמשך הוא 2-3 שורות שמתחילות ב:

"נשים לב כי החלק הזה (ומסומן בעיגול החלק של 000....10000) לא מתחלק ב-10" (שזה ניסוח קצת מוזר..)
יכול להיות שניסוח יותר טוב היה אולי "נשים לב כי במספר שנקבל החלק הזה *לא יכול* להתחלק ב-10 כי אז היה צריך להתחלק גם ב-5 וגם ב-2, ונתון שהוא לא מתחלק ב-5 (וגם אי זוגי)
אגב, שורה אחר כך מגיעים למסקנה ש-n זר ל-10 וזהו..אין המשך..
עדיין לא ברור לי איך מגיעים מהמסקנות שהגענו אליהן דרך שימוש בשובך היונים ומציאת מספר מהצורה:
zz 111...1000..000 zz
להוכחה כי קיים מספר שמורכב מ-11111...1111 שמתחלק ב-n אי זוגי שאינו מתחלק ב-5,
&nbsp
&nbsp
 

עריסטו

Active member
אז ככה

ההוכחה היא כזו:
הוכחנו שקיים מספר מהצורה
111...111000...000
(a אחדות ואחריהן b אפסים) שמקיים את הדרוש. אפשר לכתוב את המספר הזה גם כך:
111...111 * 1000...000
כאשר בגורם הראשון יש a אחדות ובגורם השני יש b אפסים. הגורם השני זר ל-n. יש משפט בתורת המספרים שלפיו אם מכפלה של שני מספרים שלמים מתחלקת ב-n (כאשר n שלם) ואחד הגורמים זר ל-n אז הגורם האחר מתחלק ב-n. לכן 111...111 מתחלק ב-n.
 
למעלה