חידה קשה במיוחד

[כלמנ]

חידה קשה במיוחד

למעשה היא כה קשה, שבעצם היא קצת לא מתאימה לפורום כזה, אבל אני מבטיח שיש לה פתרון יפה ומובן. אז ככה: יש לי עשרה מטבעות ואני מסדר אותם בערימות, נניח 3,3,3,1 התהליך הוא כזה: אני לוקח מכל ערימה מטבע אחד ויוצר ערימה חדשה. את זה אני עושה שוב ושוב: 3,3,3,1 2,2,2,4 (הערימה של ה 1 נעלמה, ונוספה ערימה של 4) 1,1,1,3,4 2,3,5 (הערימות עם ה 1 נעלמו, ונוספה ערימה של 5) 1,2,4,3 1,3,2,4 2,1,3,4 1,2,3,4 1,2,3,4 כפי שרואים בסוף מגיעים למצב יציב של 1,2,3,4 צריך להראות: לא משנה מה הסידור ההתחלתי, בסופו של דבר מגיעים לסידור של 1,2,3,4 את אותה חידה ניתן לשאול על 15 מטבעות, 21,28 .... בהצלחה.

 

[Crurifragium]

נראה די ברור

לכל סדרת "ערימות" עם N אברים יהיה רק סידור אחד שהוא יציב במובן שמתקבלת בדיוק אותה סדרה. הסידור הזה הוא מ 1 עד N, כשכל איבר גדול באחד מהקודם. סידור כזה הוא תמיד יציב כי כשוברים לסיבוב הבא אז הראשון נעלם, כל האחרים יורדים באחד (כל שיש שוב סדרה מ 1 ועד N-1 ) ומתווסף איבר חדש שהוא N. כל סידור אחר לא יהיה יציב בפני עצמו בסבב אחד. המספרים ההתחלתיים (כמות המטבעות) שמקיימים את זה הם כל אלו שהם סכום כזה מ1 עד N. 10,15,21,28,36,45,55... מה שנשאר להראות זה רק שאין שום סידור אחר שיוצר יציבות מחזורית. אם אין כזה, אז גם ברור שבסוף נתכנס למספר היציב. בסופו של דבר בכל מקרה נתכנס לסדרת אברים בגודל N, שלא תגדל או תקטן יותר, וסדרה כזו תמיד תכלול את כל הערכים בין 1 ל N : אם יש כמה ערכים זהים אז האורך ישתנה (יגדל אם הם גדולים מ 1 ואין 1 אחר, או יקטן אם הם 1). אם הם גדולים, אחרי כמה סבבים כולם יגיעו ל1 ויעלמו במכה. ואז הכמות תהיה קטנה מN, ותמשיך לגדול/לקטון לפי אותה חוקיות. אם היו כמה סטים של מספרים עם ערכים זהים, אחרי כמות סיבובים מספיקה כולם יעלמו, כי הערכים החדשים הם תמיד מספר האברים האחרון. כל הערכים הגדולים ממספר האברים יעלמו עם הזמן כי לא יהיו להם ערכים כפולים חדשים. וכאשר כולם יותר קטנים ממספר האברים אז יהיו כמה 1ים שיעלמו למספר אברים קטן עוד יותר. בסוף הערך הכי גבוה יהיה N, ולא יהיו כפולים. (לא הוכחה פורמלית, אבל אני די בטוח שאפשר להגיע מכאן למשהו יותר מסודר אם זה נחוץ) בשלב הזה יש N אברים, עם מחזוריות ברורה שבה המספר האחרון/חדש הוא תמיד N, ויש רק מספר אחד לכל ערך בין 1 ל N. מכאן בכל שלב האבר האחרון קטן ב1, ואחריו מתווסף חדש בערך N, כאשר אבר אחר איפשהו לפניו נעלם. אחרי N סבבים הוא הופך ל1 ויש סדרה מ 1 ל N, שהיא כאמור היציבה.

 

[כלמנ]

התחלה טובה, אבל לא מספיקה

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

 

[Crurifragium]

חשבתי שזה מה שעשיתי

הסברתי למה בסוף האורך של הסדרה יתכנס לסדרה עם N אברים באורך שלא ישתנה יותר, למה סדרה כזאת תהיה עם אברים שכולם שונים, ולמה סדרה כזאת תמיד תתכנס ל...1,2,3,4. על איזה משלושת אלו צריך לפרט יותר, או יותר מסודר, לדעתך? (אם אף אחד אחר לא ינסה לעשות את זה בינתיים אז יהיה לי זמן מחר)

 

[guysoffer]

אפשרי רמז או כיוון ? אין לי אפילו התחלה.

 

[כלמנ]

כמובן

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

 

[guysoffer]

זה היה הכיוון שלי גם

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