בתשובה לאלון עמית, 03/08/03 8:15
 |
|
 |
||
|
||||
 |
לא חשבתי לייגע עם עוד נתונים, אבל נראה שיש כמה מתעניינים :-) ערך המשחק עבור מספר כללי של שחורים ואדומים הוא מספר רציונלי, כמובן. לא קשה לשים לב, ועוד יותר קל להוכיח, שאם נכפול ערך זה במקדם בינומי מתאים (מס' הקלפים הכולל מעל מס' האדומים), נקבל תמיד מספר *שלם*. נחמד. המספרים השלמים האלה מקיימים יחס רקורסיה טיפה יותר ידידותי מהערכים הרציונליים המקוריים. למרות זאת עדיין לא הצלחתי לבצע ניתוח אסימפטוטי מדוייק שלהם. לעומת זאת, שלחתי את הערכים האלכסוניים (אלה עבור מספר שווה של שחורים ואדומים, כמו בשאלה המקורית) בתור שאילתא ל-"אנציקלופדיה של סדרות השלמים", וקיבלתי בתור תשובה את יחד עם רפרנס למאמר שעדיין לא השגתי אבל לפי אבסטרקטו הוא דן כנראה בדיוק במשחק המדובר, באופן לא מפתיע. אם יש למישהו גישה לספריה אוניברסיטאית (מה שלי אין לצערי כרגע) אולי נוכל לקבל עוד פרטים. |
 |
 |
 |
|
|
|
||
|
||||
|
קפיצה קטנה לספרייה של הפקולטה למדעי המחשב, והמאמר בידי. הוא אכן עוסק בבעייה הנ"ל (שבמקור נחקרה ע"י Shepp ב-1969). במהלך המאמר מוצגת המשוואה הרקורסיבית שהוזכרה, ומוכחים אי-שיוויונים שונים לגביה. למשל: V(m, p+1) <= V(m,p)+1/(n+1) כאשר V מייצג את תוחלת הרווח עם m כדורים שחורים ו-p אדומים.V(m, p) <= V(m+1,p)+1/(n+1) V(m+1, p+1) > V(m,p) בנוסף, Shepp בעצמו חישב את באופן אסימפטוטי את האסטרטגיה ל"מתי לעצור". (p+a*sqrt(2p) a=0.83992 כש-p שואף לאינסוף אם אתם חייבים לדעת). המאמר מציין שהחישוב הרקורסיבי ייצור שגיאה הולכת וגדלה, ולכן"מעביר את הבעייה לשלמים" ע"י הכפלה ב-(m+p)!, כפי שציין אלון. אחרי קצת עבודה, ועם שימוש בזהויות משולש פסקל, מגיעים לתוצאה הבאה: V(m, p) = (p-m) + m/(p+1) + O(p^-3) עבור m קבוע.תבדקו לראות אם זה יוצא... |
|
|
|
|
|
|
||
|
||||
|
המאמר מציין שעבור ערכים של p (מס' הקלפים ה"טובים") בין 0 ל-100, שווה לקחת עוד קלף אמ"ם מספר הקלפים ה"רעים" קטן מ- p+0.83992sqrt(2p)-0.1427 הם מסבירים שהחישובים שלהם הם עד p=100 מטעמי נוחות בלבד, ולא בגלל קשיים חישוביים ושזמן הריצה של המחשב עלה להם רק 10 דולר.
|
|
|
|
|
|
|
||
|
||||
|
קודם כל - תודה! אני לא בטוח שאני מבין את הנוסחה האחרונה שציטטת. עבור m=p זה יוצא בערך 1, בעוד שערך המשחק בוודאי שואף לאינסוף (כמו שורש n חלקי שתיים, לפי הניחוש שלי). חסר גורם? זה מנורמל אחרת? בכל אופן, תודה שוב על המאמץ. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |