בתשובה להקשה המקשה, 07/08/03 22:10
תשובת תם 162281
בהחלט! יפה מאוד. ממש ממש לא צריך מטלב בשביל לראות שזה (הרבה) יותר משתיים בחזקת חמישים - אבל האינטואיציה של הרבה אנשים מוליכה אותם להרבה פעמים שתיים.

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

נניח שנתונה לנו סדרת טבעיים שסכומם מאה, ונתבונן באבר x כלשהו בסדרה.

אם x הוא זוגי, מה יקרה אם נחליף בסדרה את x בפעמיים x/2 ? כדי שזה "ישתלם", אנחנו צריכים שיתקיים

x < (x/2)^2

דהיינו: x > 4. לכן, אין טעם שבסדרת המסוכמים יהיו מספרים זוגיים הגדולים מ- 4.

אם x הוא אי-זוגי, מה יקרה אם נחליף בסדרה את x ב- (x+1) חלקי 2 ו- (x-1) חלקי 2?

עכשיו צריך שיתקיים

x < (x^2 - 1)/4

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

ממה שקבלנו עד עכשיו נובע שסדרה אופטימלית מורכבת בהכרח מהמספרים 2, 3 ו- 4 (ברור ש- 1 לא עוזר). היות ש- 2+2=4 וגם 2 כפול 2 זה ארבע, אפשר תמיד להחליף ארבע בפעמיים שתיים, כך שנשארנו רק עם המספרים 2 ו- 3.

כל שלושה מופעים של 2 אפשר להחליף בשני מופעים של 3, ולקבל במכפלה 9 במקום 8. לכן, אסור שיופיעו יותר משני מופעים של 2 בתשובה.

מסקנה סופית: שלושים ושניים מופעים של 3, ושניים של 2. (כמובן שאפשר להחליף פעמיים 2 ב- 4).
תשובת תם 162285
נכון מאוד, אבל אפשר טיפה לקצר - כדאי להחליף כל m>3 ב-‏2 ו-(m-2), אין צורך להפריד לזוגיים ואי-זוגיים.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים