חידה

[טלמון סילבר]

התכוונתי n ראשוני.

 

[1אברהם]

../images/Emo62.gif ניסיון

מספר האיברים( מספרים שלמים) בקבוצה הוא 2N-1 וצ"ל שיש קבוצה של N איברים שסכומם מתחלק ב N . מניחים שאם N ראשוני אז זה נכון. אם N לא ראשוני הוא ניתן לפירוק יחיד למספרים ראשוניים מהצורה: N=a1*a2*a3*...ak נסמן B=a2*a3*a3...*ak , אז N=a1*B נוציא קבוצה של 2a1-1 אברים שמתוכה נוציא a1 אברים שסכומם מתחלק ל a1 ( זה אפשרי כי a1 ראשוני ). את שאר a-1 האיברים "נחזיר" לקבוצה ושוב נחזור על התהליך , מהקבוצה האחרונה של 2a1-1 האברים נוציא עוד a1 אברים שסכומם מתחלק ל a1 ונישאר עם a1-1 אברים שבעצם אין לנו מה לעשות איתם. אז כמה תת קבוצות m שמכילות a1 אברים (וכאמור סכום כל תת קבוצה מתחלק ל a1) קיבלנו?

m=(2a1*B-1 -(a1-1) )/a1=(2a1B-1-a1+1)/a1=(2a1B-a1)/a1=2B-1​

נסתכל על קבוצה חדשה של 2B-1 אברים שכל איבר הוא סכום של התת קבוצות בעלות a1 אברים, וכל איבר כבר מתחלק ב a1 . אם B הוא מספר ראשוני ( כלומר N=a1*B=a1*a2 ) אז כל שנותר לנו זה להוציא את B האיברים מתוך 2B-1 איברים כך שסכומם מתחלק ב B וכיוון שכל איבר כבר מתחלק ב a1 אז כל הסכום מתחלק ל N=a1*B ומספר האיברים הכולל מהקבוצה הראשונית של 2N-1 האיברים הוא גם N=a1*B. אם B אינו ראשוני נחזור שוב על התהליך שעשינו עם הקבוצה של 2N-1 האיברים לקבוצה החדשה של 2B-1 האיברים כאשר הפעם נחלק לקבוצות של a2 אברים שכל אחת מהם מתחלקת ל a2 והפעם נקבל 2C-1 תת קבוצות ( C=a3*a4*...ak ) שסכומן מתחלק ל a2 ( וכמובן גם ל a1 ) ומכילות a1*a2 אברים מהקבוצה הראשונית. וכך הלאה עד שנגיע לכופל האחרון ak

 

[טלמון סילבר]

../images/Emo127.gif יפה! אוסיף מספר מילים כשאשוב

מהים.

 

[טלמון סילבר]

ניסוח אחר. סוג מיוחד של אינדוקציה.

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

 

[טלמון סילבר]

../images/Emo62.gif פתרון.

נתונים n מספרים שלמים כלשהם. נמספר אותם: (a(1), a(2), a(3), ..., a(n צריך להוכיח שקיים רצף כלשהו שלהם (בהתאם למספריהם), שסכומו מתחלק ל-n. נבחן את המספרים הבאים:

S(1) = a(1) S(2) = a(1) + a(2) S(3) = a(1) + a(2) + a(3) . . . S = a(1) + a(2) + a(3) + . . . + a​

לכל אחד מהם יש שארית מסויימת מחילוק ל-n. השאריות האפשריות הן מ-0 עד n-1. אם כל שאריות שלהם שונות, אז לאחד מהם השארית שווה 0, כלומר הוא מתחלק ל-n. אם לשניים מהם יֶשנה אותה שארית, אז הפרשם מתחלק ל-n. מאידך, אם ניזכר ממה הורכבו מספרים אלה, ניראה שגם ההפרש מורכב למעשה מסכום של רצף של המספרים המקוריים. נניח, למשל, שהמספרים הם (S(3 ו-(S(7. אז ההפרש ביניהם הוא הרצף:

S(7) - S(3) = a(4) + a(5) + a(6) + a(7)​

 

[snogal]

../images/Emo127.gif יפה מאד . הוכחה משולמת.

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

 

[טלמון סילבר]

בעניין 2n-1

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

 

[טלמון סילבר]

הערה חשובה: להבדיל מהחידה שלך,

כאן המספרים אינם ממוספרים, ולא מדובר על רצף כלשהו. אבל מספר האברים מקובע: n מתוך 2n-1.

 

[רותם ע]

אוי ואבוי, איך שאני לא...../images/Emo176.gif

מבינה פה כלום בגרוש...

 

[טלמון סילבר]

רוצה להבין? נסביר במילים פשוטות.