בעיות מתימטיות

[יאיר של תמר]

נראה פשוט...

בטח פיספתי משהו .... 3999*20 = 79980 ???

 

[עריסטו]

אכן פיספסת משהו

התשובה ודאי אינה גדולה מ- 240.

 

[יאיר של תמר]

אה...פיספסתי שניתן לשאול..

*כל* שאלה...

 

[עריסטו]

אני חושב

שהפתרון הוא 180 שקלים. אם זה נכון (וזה בטח לא...) אתן נימוק.

 

[DadleFish]

../images/Emo45.gif ועכשיו לנימוק ../images/Emo13.gif

 

[עריסטו]

הדרכה

בכל שאלה יש לשואל הסתברות מסויימת לקבל "כן" והסתברות מסויימת לקבל "לא". מה צריכות להיות ההסתברויות האלה כדי לקבל פתרון אופטימלי (עלות מינימלית)?

 

[DadleFish]

הפתרון שיש לי לא מסתמך על זה דווקא

 

[Abbe Faria]

נימוק...

גם לי יצא 180, בשיטה הבאה... ב20 ש"ח אפשר לגלות את המספר מתוך 2 מספרים ("האם זה מספר א" - אם כן זה עלה 10 ש"ח לגלות, אם לא זה עלה 20 ש"ח לגלות שזה מספר ב) ב30 ש"ח, אפשר לגלות את המספר מתוך 3 (נניח שהם 1-2-3, "האם המספר גדול מ1" במידה ולא זה 1, במידה וכן, אז זה עלה לנו 10 ש"ח להגיע שוב ל2 מספרים) ב40 ש"ח, אפשר לגלות את המספר מתוך 5 ("האם הוא גדול מ2" אם כן, אז זה שוב לגלות את המספר מתוך 3 ב30, אם לא, אז זה לגלות את המספר מתוך 2 ב20) מפה והלאה, צריך למצוא מקדם שיתן מצב שבו כמות המספרים שתרד לנו בשאלה "האם המספר קטן מm" יהיה כמה שיותר שווה עבור כן או לא באותו מחיר, ז"א שפעמיים "כן" ישאיר אותנו עם אותה כמות מספרים כמו פעם אחת "לא"... למצוא את המספר הזה: zzz 1-x=x^2 zzz ולכן x=0.618... ולכן אם נשאר לנו רצף של n מספרים (בשאלות של גדול/קטן זה תמיד ישאר רצף) השאלה תמיד תהיה "האם המספר קטן מ zzz 0.618*n+c zzz (כאשר c+1 הוא המספר הנמוך ביותר ברצף) עכשיו אני מתחיל ב5, וכל פעם מחלק ב0.618 (לאחר כל פעם כזאת מקצץ את המספרים שאחרי הנקודה, מאחר ואנחנו הולכים על "המקרה הגרוע ביותר")... אחרי 14 פעמים כאלה, התוצאה היא 5779 (אחרי 13 זה עדיין 3572) לכן אפשר להגיע מ4000 מספרים ל5 במקסימום 14 שאלות (שהתשובה עליהן היא כן, כל שאלה שהתשובה היא לא שווה ל2 שאלות שהתשובה היא כן) (במידה ובשלב של 6-8 מספרים שנותרו, על השאלה "האם המספר גדול מ3" התשובה היא לא, אז כבר הגענו להוצאה של 150 ש"ח, אבל נשארו רק 3 מספרים ולא 5 אז עדיין אפשר ב180)

 

[DadleFish]

../images/Emo45.gif זה פתרון אחד,

היחס שעלית עליו הוא נכון, אבל יש תשובה הרבה יותר אלגנטית, פשוטה וחכמה. תסתכל על שלוש השורות הראשונות שלך ותמשיך ל-50 ול-60 וכנראה שתגלה למה אני מתכוון.

 

[Abbe Faria]

../images/Emo62.gif

FiboFuckiiNacci!

מצטער, כשעניתי על זה זה היה אחרי 18 שעות שהייתי ער... עכשיו אני כבר ער 27 שעות רצוף והמוח עובד הרבה הרבה יותר טוב

 

[Abbe Faria]

והאמת

כבר אתמול הייתי צריך לשים לב ל0.618... הרי מוסיפים 1 (או מחלקים את 1 בו) ומקבלים את 1.618... My bad

 

[DadleFish]

../images/Emo45.gif ויפה מאוד ../images/Emo13.gif

 

[Alkhimey]

אולי

20 כפול לוג 2 של 4000

 

[DadleFish]

למה?

 

[Alkhimey]

-<

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

 

[DadleFish]

נכון,

חיפוש בינרי לא מספיק טוב. Abbe Faria עלה על היחס האיכותי, 0.618, לחלוקת המרחב.

 

[בינארית]

חיפוש בינארי?

מתחילים מהאמצע (מהמספר 2000). השאלה הנשאלת האם הוא גדול ממנו? אם לא נשארים אם החלק השמאלי (כל המספרים הקטנים מ200), ואם כן עם הימני (כל המספרים הגדולים מ2000). ושוב חוזר חלילה, לוקחים את החצי. אם נבחור גדול מ2000 שואלים האם גדול מ 3000. אם כן לוקחים את החלק הימני (כל המספרים הגדולים מ-300). אם לא לוקחים את החלק השמאלי (כל המספרים הקטנים מ3000 וגדולים מ2000) וכן האלה... לכל שאלה לוקחים בחשבון 20 שקלים. סכ"ה LOG4000 אשרויות אם זכרתי נכון. (לא בדקתי אם זה יוצא כמו שחברי אמרו לפניי...)

 

[DadleFish]

../images/Emo31.gif

 

[DevilGirl92]

אי אפשר לנסות ככה-

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