קפוץ, גמל, קפוץ!

[jaXon]

חידה

זו נראית לי חידה קשה. לא הצלחתי להגיע עדיין למשהו משביע רצון ולכן אני פונה לפורום לשמוע הצעות. גמל צריך לעבור מרחק D, וברשותו 10000 ק"ג קש. לכל ק"מ שהוא עובר הוא צורך ק"ג אחד של קש. הקיבולת של הגמל היא 1000 ק"ג. המטרה היא להעביר כמה שיותר קש לנקודת היעד. כמובן שהגמל לא יכול לנוע אם אין עליו קש בכלל. כל מה שהוא יכול לעשות זה לנוע (קדימה/אחורה), ולהשאיר/לאסוף קש בדרך. יש למצוא את השיטה להעביר כמות מקסימלית של קש לנקודת הסיום. אני מחפש גם הוכחה לאופטימליות של הפתרון.

 

[freedom rider]

../images/Emo58.gif פתרון חידת הגמל ../images/Emo58.gif

חשבתי על זה כל הערב אתמול.... אתייחס תחילה למקרה הפרטי בו D שווה ל-1000. ברור שאם הגמל לוקח 1000 ק"ג קש ועובר את כל המרחק, לא יצליח להעביר ליעד אף לא ק"ג אחד של קש. כמו כן, ברור שאם עבר כבר 500 ק"מ, יש בפניו 2 אפשרויות: להמשיך עד הסוף (ואז לא העביר כלום) אן לחזור להתחלה, ואז למעשה בזבז 1000 ק"ג קש בלי לקדם את מטרתו. לכן על הגמל, לקחת 1000 ק"ג קש, לצעוד X ק"מ, להשאיר בנקודה אליה הגיע 1000-2X ק"ג קש, ולחזור להתחלה. בצורה זו הצליח להעביר 1000-2X ק"ג קש למרחק X ק"מ בעלות של 2X ק"ג. עבור X=100 למשל, יעביר 800 ק"ג קש למרחק 100 ק"מ בעלות של 200 ק"ג קש. ככל ש-X יקטן, יעביר יותר קש בפחות עלות, לכן, בהנחה ש-X חייב להיות שלם, עליו לקחת 1000 ק"ג קש, להניח 998 ק"ג במרחק ק"מ מנקודת ההתחלה, לחזור להתחלה, לקחת עוד 1000 ק"ג קש וכן הלאה. לאחר 9.5 נגלות, הוא יהיה במרחק 999 ק"מ מהיעד, ולרשותו 9981 ק"ג קש. והכל מהתחלה... תמורת 19 ק"ג קש נוספים ישנע 9962 ק"ג קש למרחק ק"מ נוסף, וכן הלאה. כשיגיע לק"מ ה-53 ישארו לו 8993 ק"ג קש (כי 1007=19*53) ולכן המשך השינוע לק"מ הבא יעלה לו 17 ק"ג בלבד, וכן הלאה. כמה ק"ג יישאר לו בסוף? אני משאיר את החישוב למישהו אחר (יש לי גם עבודה

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

 

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

האם אתה יכול להביא דוגמה

לכך, שבכלל קיימות אפשרויות שונות? נגיד שהגמל הולך 10 פעמים הלוך ושוב, אולי בפעם האחרונה לא חוזר (האם הוא חייב לחזור בסוף?), כלומר "מבזבז 20D (או 19D) ק"ג, ומעביר את השאר. האם אפשר להביא דוגמה כלשהי של שיפור התוצאה?

 

[its moi]

ונניח

שהוא ילך כל פעם 2 ק"מ? אז כל פעם הוא יניח 996 וסה"כ אחרי נגלה אחת יהיו לו 9962 במרחק 998. אותו דבר.

 

[freedom rider]

אכן נכון

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

 

[jaXon]

בהמשך לזאת...

ראשית, כפי שאני מבין את החידה אין אילוץ לעבוד רק עם מספרים שלמים. בהנחה שההמסע מנקודת המוצא לנקודת היעד נעשה בקטעים באורך קבוע, כפי שאתה מתאר, ניתן להגיע לנוסחת הנסיגה הבאה : S - amount in iteration n. S[0] = 10000 d = length of each segment S(n+1) = s - d ( 2[s/1000] - 1) where [x] is the integer ceil of the real number x. (זה מתיישב עם הערכים שהצגת כאשר d=1, למשל) למעשה מה שמעניין אותנו הוא ערכו של (s(1000/d כי זה מה שנשאר אחרי האיטרציה האחרונה. לא ידעתי איך לנתח נוסחת נסיגה זו, אז פשוט ניסיתי במחשב, כדי לקבל רושם על התנהגותה... נדמה שכאשר d שואף ל 0 הכמות המועברת שואפת ל 1400. ואגב, לא תמיד מתקיים ש d קטן יותר מניב תוצאה טובה יותר. למשל : עם d=25 תקבל 1350 ועם d=20 תקבל 1320. אבל אסימפטוטית ישנה עלייה. יש למישהו רעיון איך מנתחים אלגברית נוסחת נסיגה שכזו עבור d נתון ?

 

[freedom rider]

אני אחזור אליך...

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

 

[freedom rider]

פתרון מלא

הקטנת המרווחים לא תעזור להגדיל את הכמות המרבית שהגמל יעבור. אם לגמל יש יותר מ-9000 ק"ג בנקודת ההתחלה, הוא יעשה בסך הכל 19 הליכות מנקודת ההתחלה לנקודה אליה יעביר את הקש בפעם הראשונה. אם נקודה זו נמצאת במרחק X מההתחלה, אז לאחר 9 הליכות יהיו לו שם 10000-19X ק"ג קש. ה-X הטוב ביותר הוא זה שיביא את כמות הקש ל-9000 ולכן 52.63=1000/19=X. אותה תוצאה תתקבל אם יעביר כל פעם את הקש למרחק ק"מ אחד בכל פעם. לאחר הק"מ ה-52 אכן יעמוד בפני מצב בו לא כדאי לא להעביר את הקש למרחק ק"מ שלם. לאחר העברת הקש למרחק 52.63 ק"מ יישארו לו כאמור 9000 ק"ג קש. להעברתם יידרש ל-17 מסעות בסה"כ, והמרחק אליו כדאי לו להעביר את הקש הוא 1000/17=58.82 ק"מ. נקודת המעבר הבאה היא במרחק 1000/15=66.66 ק"מ, ואז יהיה במרחק 874.51 ק"מ מהמטרה עם 7000 ק"ג קש, וכן הלאה. ההעברות הבאות יהיו למרחק 76.92 ק"מ, 90.909 ק"מ, 111.11 ק"מ, 142.857 ק"מ, ו-200 ק"מ. אז יהיה במרחק 252.71 ק"מ מהמטרה עם 2000 ק"ג קש, והוא יידרש לעוד 3 הליכות בהן יצרוך עוד 758.13 ק"ג קש, ובסיום המסע יישארו לו בסה"כ 1241.87 ק"ג קש.

 

[jaXon]

ממממ....

1)למה "ה-X הטוב ביותר הוא זה שיביא את כמות הקש ל-9000 " ? מה הצעדים שקבעת הם כך שבסוף כל צעד יש דווקא 1000 פחות? 2) האם אתה טוען ש 1241.87 זה המקסימום? הרי חישבתי (באמצעות נוסחת הנסיגה) שבצעדים קבועים של ק"מ (כפי שהצעת בהתחלה) ניתן להגיע לבדיוק 1398 ק"ג קש בנקודת היעד.

 

[jaXon]

תיקון: "מה הצעדים" --> "למה הצעדים"

 

[freedom rider]

תשובה

בקשר ל-(1): ה-X-ים נקבעו בדיוק בנקודות שבהן הערך של "מספר הנגלות" שהוא

[S/1000]​

(בנוסחת הנסיגה שלך) משתנה. כפי שציין its moi קודם, לא משנה גודל הצעד עצמו, אלא מספר הנגלות. כלומר אם מתחילים עם 10000 ק"ג ומתקדמים כל פעם ק"מ, אז אחרי 52 ק"מ יש לגמל 9012 ק"ג קש, וזה בדיוק מה שיהיה לו אם יתחיל לשנע מייד את הקש למרחק 52 ק"מ. כעת, נניח שהוא אכן נמצא בנקודה כלשהי עם 9012 ק"ג קש. אם ישנע את הקש למרחק ק"מ נוסף, שוב ידרשו לו 19 מסעות שעלותם 19 ק"ג קש, ואז יישארו לו 8993 ק"ג קש. אם לעומת זאת ישנע את הקש למרחק 0.63 ק"מ נוספים, אז עלות השינוע תהיה 12 ק"ג (והגעתי ל-0.63 ע"י חלוקת 12 ב-19). עכשיו יש לו בדיוק 8000 ק"ג קש, אותם ניתן לשנע הלאה ב-17 הליכות בלבד. באשר לתשובה הסופית - ייתכן וטעיתי בחישוב. אבדוק שוב.

 

[freedom rider]

אוקיי ../images/Emo45.gif

אכן טעיתי בחישוב (לא ממש מפתיע

). הנוסחה שלך נכונה, כמובן, וגם התוצאה. ערכתי את החישוב שלי מחדש ואכן קיבלתי s=1399.76

 

[freedom rider]

קפוץ, גמל, קפוץ!