שאלה מעניינת

אידיוט

New member
שאלה מעניינת

המחלקים החיוביים של n הינם d1<d2<d3...<dk כאשר d1 = 1 ו-dk = n D = d1*d2+d2*d3+...+dk-1*dk הוכח שD<n^2 וכן מצא כל n שעבורו D מחלק את n^2 ללא שארית. זה מאולימפיאדה עולמית למתימטיקה ולקח לי אישית די הרבה זמן לפתור אז תהנו...
 

yak141

New member
שאלה חמודה

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

Colomonimbus

New member
ניסיון

dk-1 הוא במקסימום n/2 וdk-2 הוא במקסימום n/3 וכך הלאה כלומר האיבר האחרון (dk*dk-1) הוא n^2/2 האיבר לפניו הוא n^2/6 ולפניו הוא n^2/12 כלומר הוא אף פעם לא מגיע ל-n^2 נכון?
 

yak141

New member
זה מה שאני הלכתי עליו

סכום הטור (אם מוציאים n^2 מחוץ לסוגריים) עבור t איברים הוא
1-1/t​
ולכן הא"ש תמיד מתקיים אם כי אולי הייתי מחליף את הסימן מחזק לחלש למקרה שמדובר במקרה של n=1.
 

אידיוט

New member
כן, אבל למה?

נכון, אבל למה שסכום שיש בו יותר מהרכיב הראשון לא יחלק את n^2?
 
ממממ...

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

אידיוט

New member
בערך

זה פחות או יותר נכון אך החור בהסבר שלך שהוא לא ממש שולל איזשהי קומבינציה שבה לD יותר מרכיב אחד, הנה הפתרון שלי: המחלק הכי קטן של n (חוץ מאחד) הוא בוודאי המחלק הכי קטן של n^2. בואו נקרא לו dk. המחלק הכי גדול של n פרט ל n עצמו הינו n/dk. המחלק הכי גדול של n^2 הוא (n*(n/dk - שהוא למעשה הרכיב האחרון בD ולכן כיוון שD קטן מn^2 אז כדי שיוכל לחלק אותו לא יכולים להיות לו עוד רכיבים מעבר לאחרון כי אז יוצא מצב שהוא בין המחלק הכי גדול למספר עצמו ולכן לD חייב להיות רק רכיב אחד.
 

אידיוט

New member
טוב אני אנסה

סדרת מחלקים של כל מספר היא כל הקובינציות של הגורמים הראשוניים שלו, כאשר הקומבינציה הקטנה ביותר מעל 1 היא פשוט הגורם הראשוני הקטן ביותר והקומבינציה הגדולה ביותר מתחת למספר עצמו היא מכפלה של כל הגורמים הראשוניים פרט לקטן ביותר. קבוצת הגורמים הראשוניים של N^2 היא פשוט קבוצת הגורמים הראשוניים של N מוכפלת (כל איבר מופיע פעמיים בקובוצה החדשה על כל פעם שהוא הופיע בקבוצה המקורית). ז"א שמחלק הקטן ביותר של שניהם הוא אותו דבר כלומר הגורם הראשוני הקטן ביותר בקבוצה, וז"א שהמחלק הכי גדול של N^2 זה N^2 חלקי הגורם הזה. בחזרה לעניינו - הרכיב האחרון של D הוא N כפול המחלק הגדול ביותר של N כלומר N חלקי הגורם הכי קטן והתוצאה של זה היא המחלק הגדול ביותר של N^2. כיוון ש-D קטן מN^2 ועתה הוכחנו שהוא גדול שווה למחלק הכי גדול של N^2 אז אם יש בD משהו מעבר לרכיב האחרון - אז הוא בין מחלקים , כלומר לא מחלק. לכן יש בD רק רכיב אחד ולכן N ראשוני. מקווה שהשכלת והבנת :)
 
ממממ

אמרת שיש לD מן עוד משהו ש"הורס לו" את החלוקה..כדי שההוכחה שלך תהיה באמת שלמה נראה לי שצריך להוכיח שה"משהו" הזה לא מתחלק בעצמו ב n^2. בנוסף, אני לא מבין מה הבעיה בהוכחה שלי...היא אמנם לא פורמלית בטירוף אבל היא מכסה את כל האפשרויות.
 

אידיוט

New member
תשמע

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