 |
|
 |
||
|
||||
 |
מאחר והטריוויה שלי הייתה קלה מידי, ודי הרסתי את זו של רון, אז הרי חידה ששמעתי לא מזמן כפיצוי: על השולחן לפניך מונחת חבילת קלפים הפוכה (בלי ג'וקרים). אתה יכול לבחור אם למשוך קלף או לא. היה ומשכת, והקלף אדום - הרווחת שקל. שחור - הפסדת אחד (ואין בעייה להכנס לאוברדפט). לא משכת - המשחק נגמר, ואתה הולך עם הכסף. השאלה היא - מה אסטרטגיית המשיכה האופטימלית? מתי לעצור כך שתרוויח מקסימום כסף? |
 |
 |
 |
|
|
|
||
|
||||
|
האם המשחק נגמר גם אם נגמרו כל הקלפים בחפיסה? | |
|
|
|
|
|
||
|
||||
|
וודאי. איך תשחק בלי קלפים? | |
|
|
|
|
|
||
|
||||
|
אני מציע: להפסיק בפעם הראשונה שהמאזן חיובי (אם זה קורה). אף פעם לא מרוויחים ככה יותר משקל, אבל אף פעם לא יוצאים עם פחות משקל במשחק שיש סיכוי להרוויח בו משהו. האם אתה יודע מה האסטרטגיה המיטבית? |
|
|
|
|
|
|
||
|
||||
|
אני לא חושב שזו האסטרטגייה הטובה ביותר. הסיבה שאני מסייג זה כי אני יודע את התשובה רק נומרית - סימלצתי הכל במטלב, וראיתי מה הכי הרבה רווח שאפשר להוציא בסיכוי טוב. אשמח לפתרון יותר אינטליגנטי. |
|
|
|
|
|
|
||
|
||||
|
האסטרטגיה הטובה ביותר היא זו עם תוחלת הרווח הגדולה ביותר, כן? אני מבין שאינך יודע מה האסטרטגיה המיטבית אולם יש לך אסטרטגיה שתוחלת הרווח שלה גדולה משל האסטרטגיה שהצעתי, אבל גם בכך אינך משוכנע כי הסימולציה שלך לא כללה את כל ה-52 מעל 26 אפשרויות. נכון? האם ניסית לבדוק אותה במלואה על חפיסה בת 8 קלפים, למשל? | |
|
|
|
|
|
||
|
||||
|
כל סדרה סופית של משחקים עם תוחלת 0 תניב תוחלת 0. אם המטרה היא אחרת, נא לציין זאת בחידה. |
|
|
|
|
|
|
||
|
||||
|
אנו דנים בתוחלת הרווח של אסטרטגיות שונות במשחק הנתון. לי (וכנראה גם לגלעד) אסטרטגיות שתוחלת הרווח שלהן חיובית, ובפרט אינה 0. החידה היא מהי האסטרטגיה שתוחלת הרווח שלה היא המירבית. כל אסטרטגיה שתוצג תקבע חסם מלרע על התוחלת (וכאמור אנו כבר יודעים שהחסם הוא חיובי). גם הצגת חסם מלעיל לא-טריוויאלי תבורך, במיוחד אם החסם זהה לחסם מלרע שהוצג. | |
|
|
|
|
|
||
|
||||
|
התוחלת היא אפס רק במשיכה הראשונה - אחר כך יש שוני במספר הקלפים השחורים והאדומים שנשארו בחפיסה. התוחלת של המשחק כולו היא בברור חיובית - הרי אם תמשוך את כל הקלפים, תצא על אפס, אז אם תפסיק ברגע שמשכת 26 אדומים, ונארו עוד קלפים בחבילה, הרווחת. (לא האסטרטגיה המיטבית). |
|
|
|
|
|
|
||
|
||||
|
אבל איך זה יעזור לי? אז אני אקבל את התוחלת למשחק של 8 קלפים. יש. הסימולציה שלי אומרת לי כרגע "אם יש לך בקופה X שקלים, הפסק למשוך" (לגלות את X?), ודי סביר שזה נכון, אבל א. - מי אמר שזה נכון, אפילו אם אני אריץ על כל האפשרויות למשחק של 8 קלפים וב. - זה לא כל כך מעניין. אני רוצה לדעת למה, לא רק כמה. | |
|
|
|
|
|
||
|
||||
|
אתה לא יכול להתאים את X למקרה של 8 קלפים? הרי בטח הגעת ל-X דרך 52. או שבדקת רק אסטרטגיות מסוג "אם יש לך בקופה X שקלים, הפסק למשוך", ומבין אלה, עבור מדגם של חפיסות 52 קלפים ועבור מדגם של Xים גילית שיש ערך X שונה מ-1 המביא לתוחלת גבוהה מ- 26/27 ? א. מה זה "זה"? שהאסטרטגיה המיטבית היא מסוג "אם יש לך בקופה X שקלים, הפסק"? |
|
|
|
|
|
|
||
|
||||
|
רבע דף A4 הספיק לניתוח המשחק בן 4 קלפים (כלומר לבחינת *כל* האסטרטגיות). במקרה זה, האסטרטגיה המיטבית אינה מטיפוס "אם יש לך בקופה X שקלים, הפסק למשוך", ותוחלת הרווח שלה היא 7/8. לכן קשה לי להאמין שבמקרה המורכב יותר של 52 קלפים, האסטרטגיה המיטבית תהייה מהטיפוס הנ"ל. (עם זאת, מבין האסטרטגיות הנ"ל, עבור 4 קלפים המנצחת היא כמובן X=1 ). אני חושש שאין לי די נייר וסבלנות לניתוח המשחק בן 6 הקלפים. | |
|
|
|
|
|
||
|
||||
|
בשלב כלשהו במשחק, יש לפנינו n קלפים אדומים ו-k קלפים שחורים. עלינו לקבל החלטה: האם למשוך קלף, או לעצור? ההחלטה תלויה אך ורק במספרים n ו-k, ולא במה שהרווחנו עד כה. אם קביעה זו טעונה הסבר, אשמח להסביר. איך לקבל את ההחלטה? נניח שלצדנו פיה טובה היודעת להשיב על השאלה הבאה: מהי תוחלת הרווח ממשחק עם n אדומים ו-k שחורים, אם נשחק בצורה מיטבית? הפיה איננה אומרת איך יש לשחק, רק מהי תוחלת הרווח אם משחקים נכון. אם נעצור, נקבל בדיוק 0 (נוסף כמובן על מה שכבר הרווחנו או הפסדנו עד כה). אם נמשוך, יקרה אחד מהשניים: (+) נמשוך קלף אדום, נרוויח שקל, ונגיע למצב שבו לפנינו n-1 קלפים אדומים ו-k שחורים. (-) נמשוך קלף שחור, נפסיד שקל, ונגיע למצב שבו לפנינו n קלפים אדומים ו- k-1 שחורים. הסיכויים לכל אחת מהאפשרויות קלים לחישוב. כעת נברר, באמצעות הפיה, מהי תוחלת הרווח במשחקים שאליהם אנו עשויים להגיע, כלומר המשחק עם פחות קלף אדום או פחות קלף שחור. בהינתן שני מספרים אלה, והסיכויים ל-(+) ול-(-), נקבל מיד את תוחלת הרווח אם נחליט למשוך. עכשיו זה קל: אם תוחלת זו חיובית, יש למשוך. אם היא שלילית, יש לעצור ולהסתפק ב-0. טוב, אבל מה עם הפיה? כפי שבוודאי הבנתם, אין בה צורך, מפני שהניתוח הפשוט לעיל מורה את הדרך לחישוב תשובתה של הפיה בצורה נסיגתית: תשובת הפיה למצב נתון ניתנת לחישוב מתשובותיה למצבים פשוטים יותר. כמובן שאשמח לפרט אם דרושים יותר רמזים. בינתיים רק אציין כמה עובדות פשוטות כדי שמי שמנסה לפתור יוכל להשוות תוצאותיו לשלי: אם יש רק קלף אחד אדום וקלף אחד שחור, תוחלת הרווח היא מחצית השקל. במשחק עם ארבעה קלפים שחורים וארבעה אדומים, תוחלת הרווח היא בדיוק שקל! בקרוב אנסה לרשום במפורט את האסטרטגיה למקרה זה כדי שייקל לוודא זאת. במשחק עם 8 אדומים ו-8 שחורים, תוחלת הרווח היא 1.43411. לפטופי האומלל עדייו טוחן את המשחקים הסבוכים יותר. בכל אופן, אם כלל העצירה המיטבי תלוי רק במה שהרווחנו עד כה זה יפתיע אותי מאוד. מצד שני, כיוון שראינו שכלל זה תלוי רק בכמות השחורים והאדומים שנותרו, ברור שניתן לנסחו ככלל שתלוי רק במה שהרווחנו עד כה *וגם* בכמות הקלפים שכבר משכנו. ייתכן שהחמצתי איזו סימטריה מעניינת ואכן הנתון השני אינו חשוב - אבדוק זאת ואשוב אליכם. - אלון |
|
|
|
|
|
|
||
|
||||
|
טוב, העובדה שקיימת אסטרטגיה מיטבית ברורה, וכך גם העובדה שניתן לחשב אותה כפי שהצעת. מניתוח המשחק ה-4-קלפי כבר עולה שהאסטרטגיה המיטבית אינה כלל התלוי רק במה שהרווחנו עד כה, כך שאתה לא צפוי להפתעות. השאלה המעניינת היא מה הנוסחא לתוחלת המירבית במשחק עם 2n קלפים. | |
|
|
|
|
|
||
|
||||
|
התוחלת במשחק בן ארבעת הקלפים היא 5/6. במשחק עם שישה קלפים, 19/20. | |
|
|
|
|
|
||
|
||||
|
אתה בטוח? לדעתי, התוחלת במשחק עם ארבעה קלפים (שני אדומים, שני שחורים) היא 2/3. הבה נראה: האם אתה מסכים שהמצב (אדום, שני שחורים) שווה 0? ושהמצב (שחור, שני אדומים) שווה 4/3? נוסחה כללית "מפורשת" למשחק עם N קלפים אין, לדעתי. נוסחה רקורסיבית יש ויש, והיא לא מאוד קשה לחישוב. |
|
|
|
|
|
|
||
|
||||
|
טוב, על זה כבר אמר מיודענו ירדן ניר תגובה 83059. אתה צודק, מה שאומר שגם החישוב שלי עבור שישה קלפים שגוי. | |
|
|
|
|
|
||
|
||||
|
טוב, אז הנה המצב לאשורו, אם אינני טועה. ובהחלט יכול להיות שאני טועה. האסטרטגיה האופטימלית איננה יפה במיוחד. יש להמשיך כל עוד עודף מספר הקלפים השחורים על פני האדומים שנותרו בחבילה איננו "גבוה מדי", וכדי לפרש מהו "גבוה מדי" יש להיעזר בטבלה. למשל, אם נותרו 10 קלפים אדומים ו-13 שחורים כדאי להמשיך, אבל עם 10 אדומים ו-14 שחורים יש לעצור. את הטבלה המלאה ארשום בסוף התגובה. ערך המשחק, כלומר תוחלת הרווח אם משחקים היטב, הוא קצת יותר משני שקלים וששים ושתיים אגורות. עוד נתון טריוויה משעשע: אם שיחק מזלכם ומשכתם מיד בהתחלה 5 קלפים אדומים, יש להמשיך! תוחלת הסכום שתוכלו עוד להרוויח (נוסף על חמשת השקלים בכיס) היא קצת מעל 5 אגורות. למי שרוצה להשתכנע שאכן יש מצבים שבהם יש יותר קלפים שחורים מאדומים בחבילה ולמרות זאת כדאי לשחק - המצב הפשוט ביותר מהסוג הזה הוא: שני אדומים, שלושה שחורים. שווה להשקיע כל סכום נמוך מעשרים אגורות כדי להשתתף במשחק כזה. אשמח אם מישהו יבדוק את טענותי. ושאלה לגלעד - אתה יודע מניין הבעייה הזו? להלן האסטרטגיה: כל עוד נותרו 21 קלפים אדומים או יותר, יש להמשיך. אם נותרו 20 אדומים ו-26 שחורים, יש לעצור. אם נותרו 19 אדומים ו-25 שחורים או יותר, יש לעצור. אם נותרו 18 אדומים ו-23 שחורים או יותר, יש לעצור. וכן הלאה: 17 22 16 21 15 20 14 19 13 18 12 16 11 15 10 14 9 13 8 12 7 10 6 9 5 8 4 7 3 5 2 4 1 2 ערך המשחק המדוייק: 41984711742427/15997372030584 לבריאות! |
|
|
|
|
|
|
||
|
||||
|
אלון, יצאו לי אותם המספרים שיצאו לך, גם לגבי תוחלת הרווח וגם בכלל העצירה. את נוסחת הנסיגה של תוחלת הרווח לא קשה לכתוב, אבל פתרון סגור (נוסחה) לכל n ו- k לא מצאתי. |
|
|
|
|
|
|
||
|
||||
|
תודה על האישור! נוסחה סגורה סביר שאין פה. | |
|
|
|
|
|
||
|
||||
|
כמה זמן לקחה לך הריצה במחשב? לפי החישוב שלי (לא בדקתי מעשית) זה אמור לצאת סדר גודל של מילישניות לכל היותר. | |
|
|
|
|
|
||
|
||||
|
אכן, איו פה שום בעיית מהירות - מילישניות אם לא פחות. גם באופן תאורטי האלגוריתם הוא כמובן מאוד מהיר (פולינומיאלי, פרופורציוני ל-n*k עבור n קלפים אדומים ו-k שחורים). אני מימשתי את זה בכמה שורות Mathematica. | |
|
|
|
|
|
||
|
||||
|
הרצתי את זה על 200 קלפים מכל סוג (וכמובן כתוצר לוואי קיבלתי את כל התוצאות הנמוכות יותר), נראה שהתוצאה כפונקציה של מספר הקלפים מאוד מאוד קרובה (לפחות עבור התחום הזה) לפונקצית שורש ריבועי. ריצה על מספר קלפים גדול יותר גירדה את תחתית מחסנית הרקורסיה שלי (אני צריך לשכתב את העסק לעומק סופי) אבל זה מעניין כי שום דבר (בערך) לא מתנהג כמו שורש ריבועי חוץ, אולי, מהילוך שיכור. | |
|
|
|
|
|
||
|
||||
|
בוא נשאל שאלה אחרת: נגיד שתרוץ כל פעם עד הסוף ותשמור את הערך הכי גבוה שאי פעם התקבל במשחק ( מין ניחוש בדיעבד כזה). באופן טיפוסי הערך הכי גדול יהיה בסביבות שורש מספר הקלפים ( מהלך שיכור וכולי)1. מה שגילית הוא שהאיסטרטגיה האופטימלית ללא ידיעת העתיד מתנהגת באופן דומה. איך מנתהגת נקודת העצירה? כלומר, באופן טיפוסי, אחרי כמה קלפים מפסיקים לשחק? 1 הערכים הם למעשה מהלך אקראי תחת האילוץ שהערך הראשון והאחרון הוא אפס. |
|
|
|
|
|
|
||
|
||||
|
למעשה "גיליתי" זאת רק עבור מספר ערכים קטנים. במשך היום חשבתי שיהיה נחמד גם לחסום את העסק מלמעלה ומלמטה ולהראות שההתנהגות היא תמיד שורש. אתה תיארת חסם מלעיל (צריך רק לראות בדיוק כמה הוא יוצא מספרית), עכשיו רק צריך חסם מלרע וסיימנו לתת second best לא רע בכלל לנוסחה סגורה. מה לגבי האסטרטגיה "עצור כאשר אתה מגיע לרווח x" כאשר x ליניארי בשורש n? מה התוחלת כאן? |
|
|
|
|
|
|
||
|
||||
|
הילוך השיכור כאן הוא מאוד לא סטנדרטי - ההסתברויות הן לא קבועות בזמן ואף תלויות בהיסטוריה, באופן שנוטה ''לרסן'' את ההילוך ולקרבו למרכז - למשל, כפי שציינת, בסוף תמיד חוזרים לאפס. חוץ מזה, כפי שכבר צויין, האסטרטגיה האופטימלית איננה ''חכה עד שהזכייה תהיה...'', ולכן אני לא בטוח שמודל ''ידיעת העתיד'' שופך עליה אור נוסף. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק שזה לא בדיוק הילוך שיכור. בוא ננסה עוד טיעון פשוט: נשאל עבור אילו ערכי רווח הדחיפה הדטרמניסטית לכיוון המרכז הוא באותו סדר גודל כמו ה"רעש" בעקבות המצאות של שחורים ולבנים? כל עוד סטית התקן של הרעש היא יותר גדולה מעוצמת הדחיפה, אפשר להניח שהרווח מבצע מהלך שיכור. ברגע שהרווח חורג מכך, הדחיפה הדטרמנסטית תחזיר אותו. חישוב גס שביצעתי מראה שהדחיפה שווה לסטית התקן כאשר הרווח שווה( בעצם פרופורציוני) ל<מחצית>המרחק מסוף המשחק. כל עוד הרווח קטן "בהרבה" מכך, אפשר להתעלם מהדחיפה ולהתיחס לבעיה כאל מהלך שיכור עם סטית תקן שתלויה בזמן. אבל, התלות היא יחסית חלשה, ולכן אומדן של סתם מהלך שיכור הוא לא רע בתחום הזה. באשר לאיסטרטגיה, מבלי לפגוע באסטרגיה המדויקת (ובשיטה היפה שלך!), הייתי נותן אסטרטגיה מקורבת כזאת: אם הרווח שלך פרופורציוני ( עם קבוע עלום) למרחק עד הקצה - עצור, כי אתה מתקרב לאיזור הדטרמניסטי. האם מישהו יכול לבדוק על הפיתרון המדויק איך נראה קו ה<רווח,מספר קלפים> של האסטרטגיה המדויקת למשחק עם הרבה ( נגיד כמה מאות) קלפים? |
|
|
|
|
|
|
||
|
||||
|
(צר לי על העיכוב, בעיות גישה וזמינות) טוב, זו לא הייתה הגישה שלי - אני פתרתי את המשחק בצורה אמפירית, והגעתי לאסטרטגיה שאומרת "משוך, וכשיש לך 4 שקלים, הפסק". היא לא רעה, אבל המפורטת שלך עדיפה. מאידך גיסא, מאחר וטרחתי על שלי, אני אפרט מה עשיתי: אני הלכתי בגישה של כח טהור: הרצתי את המשחק, ובניתי וקטור של הקופה שלך כל שלב - אז יש לי וקטור של 53 אברים (מתחיל באפס), והמקסימום שלו הייתה האסטרטגיה הנכונה שלך בדיעבד - אם היית בוחר לעצור במקסימום, היית מנצח. עכשיו הרצתי את זה 10000 פעם, וחישבתי ממוצע - יוצא משהו קרוב מאד ל4 (מלמעלה). כ55% מהמשחקים מסתיימים ב4 ומעלה, כך שתוחלת הרווח שלי היא בערך 2.2 - פחות מ 2.6. אגב, גם לעצור ב3 זה לא רע - כ70% מהמשחקים מסתיימים ב3 ומעלה - תוחלת של בערך 2.1. ואת החידה סיפר לי חבר שלי - לא יודע מה המקור. |
|
|
|
|
|
|
||
|
||||
|
בקשר למקור החידה- זה לא פשוט גרסא מנוונת לבלק גק? | |
|
|
|
|
|
||
|
||||
|
לא חשבתי לייגע עם עוד נתונים, אבל נראה שיש כמה מתעניינים :-) ערך המשחק עבור מספר כללי של שחורים ואדומים הוא מספר רציונלי, כמובן. לא קשה לשים לב, ועוד יותר קל להוכיח, שאם נכפול ערך זה במקדם בינומי מתאים (מס' הקלפים הכולל מעל מס' האדומים), נקבל תמיד מספר *שלם*. נחמד. המספרים השלמים האלה מקיימים יחס רקורסיה טיפה יותר ידידותי מהערכים הרציונליים המקוריים. למרות זאת עדיין לא הצלחתי לבצע ניתוח אסימפטוטי מדוייק שלהם. לעומת זאת, שלחתי את הערכים האלכסוניים (אלה עבור מספר שווה של שחורים ואדומים, כמו בשאלה המקורית) בתור שאילתא ל-"אנציקלופדיה של סדרות השלמים", וקיבלתי בתור תשובה את יחד עם רפרנס למאמר שעדיין לא השגתי אבל לפי אבסטרקטו הוא דן כנראה בדיוק במשחק המדובר, באופן לא מפתיע. אם יש למישהו גישה לספריה אוניברסיטאית (מה שלי אין לצערי כרגע) אולי נוכל לקבל עוד פרטים. |
|
|
|
|
|
|
||
|
||||
|
קפיצה קטנה לספרייה של הפקולטה למדעי המחשב, והמאמר בידי. הוא אכן עוסק בבעייה הנ"ל (שבמקור נחקרה ע"י 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 חלקי שתיים, לפי הניחוש שלי). חסר גורם? זה מנורמל אחרת? בכל אופן, תודה שוב על המאמץ. |
|
|
|
|
|
|
||
|
||||
|
והנה וריאציה על החידה של גלעד, שלה דווקא יש פתרון אנליטי קצר ונקי. על השולחן מונחת חפיסת קלפים הפוכים, חציים אדומים וחציים שחורים. שחקן שולף מהחפיסה קלף אחרי קלף, ומתבונן בצבעים המתקבלים; הוא רשאי לעצור את התהליך מתי שירצה. השחקן זוכה במשחק אם הקלף ה*בא* בחפיסה - זה שהיה הופך אלמלא עצר - הוא אדום, ומפסיד אם הוא שחור (אם השחקן מגיע לקלף האחרון, התוצאה נקבעת על פיו). מהי האסטרטגיה שממקסמת את הסתברות הזכייה במשחק? ניתן לפתור את החידה על ידי תכנות דינמי, בצורה דומה לזו שתיאר אלון בתגובה 161200: רושמים את משוואות הנסיגה, מוצאים תנאי שפה, ולמרבה המזל, ניתן אז למצוא (באינדוקציה דו-משתנית) ביטוי סגור ל"ערך" המשחק. לחילופין, אפשר לתת נימוק מילולי פשוט למה האסטרטגיה האופטימלית היא מה שהיא. רעיון, מישהו? |
|
|
|
|
|
|
||
|
||||
|
אולי להפסיק כשיש רק עוד קלף אדום אחד בערימה? | |
|
|
|
|
|
||
|
||||
|
אם זכרוני אינו מטעני דפקת לי טיעון יפה (בענין שמואל זיגלבוים). אנסה להשיב לך כגמולך. אם באיסטרטגיה אופטימלית אינך כולל דרישה למספר מינימלי של צעדים (אז אין סיכוי לעצלני מטלב כמוני) אז השאלה שלך בעצם דומה מאד לחידת שלושת הוילונות שהצליחה לבלבל גם מתמטיקאים מקצועיים. אני מנחש כי האיסטרטגיה האופטימלית היא כפי שהציע המגיב הראשון היא להפוך קלפים עד שמגיעים ל-N-1 אדומים הפוכים או N שחורים, כמובן מה שבא קודם (מתוך סה"כ 2N קלפים). הפכת N שחורים קודם -זכית. מה אם N-1 האדומים הגיעו קודם? נסתכל על המקרה הגרוע ביותר: הפכת N-1 קלפים וכולם אדומים. הקטצ' בחידות מסוג זה הוא שרבים מניחים כי הסיכוי שהקלף הבא יהיה אדום הוא 1 חלקי N+1. ולא היא. הסיכוי הוא חצי. כך שמה שעשינו במשכנו עד N-1 אדומים (ולא N-2 למשל) הוא להגביר את הסיכוי למשוך N שחורים ולזכות ולא הגדלנו את הסיכוי להפסיד במאום. אם תהיה דרישת קהל אשמח לנסות להסביר מילולית מדוע הסיכוי הוא חצי ולא אחרת. |
|
|
|
|
|
|
||
|
||||
|
הסבר. ההסתברות (המותנית, לאחר שהוצאו כבר N-1 אדומים) מן הסתם אינה 1 ל- N+1 , אבל מדוע אינה 1 חלקי מספר הקלפים שעוד נותרו? |
|
|
|
|
|
|
||
|
||||
|
פשוט טעיתי. דברתי על מקרה בו יצאו N-1 אדומים רצופים ואז הסיכוי שהקלף הבא יהיה אדום הוא אכן 1 חלקי N+1 ולא חצי כפי שטענתי בחוצפתי. מה שכנראה הייתי צריך להגיד הוא שהסיכוי שלאחר משיכת N-1 (או כל מספר קבוע אחר) קלפים אדומים בדיוק, יבוא קלף אדום היא חצי. מספר הקלפים שצריך למשוך כדי למשוך בדיוק X אדומים הוא בין X לN+X. ולכן הסיכוי שהקלף הבא יהיה אף הוא אדום זהה לסיכוי שבחירת קלף אקראי בתחום זה תתן קלף אדום (כאמור חצי). הסבר מסודר יותר, אם אני צודק ואם אמצא כזה בהמשך. |
|
|
|
|
|
|
||
|
||||
|
אילו הייתי יודע שתנטור לי טינה בגלל זיגלבוים אולי לא הייתי נענה לאתגר שלך אז... :) אני בכוונה עדיין לא אומר האם האסטרטגיה שק. נבוך ואתה הצעתם היא אופטימלית. כשתנתן התשובה המלאה (והיא עדיין לא ניתנה), יהיה ברור למה. ומשהו אחר: אני חולק על קביעתך שההסתברות לקבל קלף אדום אחרי רצף של N-1 אדומים (ואף שחור) היא חצי ולא 1 חלקי N+1. אני אכן יודע שחידת שלושת הוילונות הצליחה לבלבל גם מתמטיקאים מקצועיים (כולל את ארדוש, אם אני זוכר נכון מהביוגרפיה שלו), אבל בתור מי שסבור שהוא מכיר חידה זו היטב (יצא לי גם ללמד אותה כמתרגל בטכניון בקורס בהסתברות), דומני שהיא לא רלוונטית כאן. למתעניינים: חידת שלושת הוילונות ידוע גם בשמות "הפרדוקס של מונטי הול" ו"עשינו עסק". פרטים ב- http://math.ucsd.edu/~crypto/Monty/Montytitle.html |
|
|
|
|
|
|
||
|
||||
|
על פניו נראה שהסיכוי שהאדום ה-Nי והN-1י יהיו צמודים זהה לסיכוי שהN-2י והN-1י יהיו צמודים וכן הלאה. לכן אין שום יתרון בעצירה בקלף האדום הN-2י אלא רק חסרון של הקטנת הסיכוי להשלים N-יה שלמה של שחורים. דרך אגב, מנין הידע הזיגלבוימי? אני עצמי לא הצלחתי לזכור את השם. |
|
|
|
|
|
|
||
|
||||
|
על זיגלבוים שמעתי במסגרת משלחת תלמידים לפולין בכיתה י"א. ובנוגע לחידה: אולי עדיף לחכות עוד כמה ימים, ואחד מקומץ האיילים שמתעניין בפתיל זה יעלה על התשובה המלאה. |
|
|
|
|
|
|
||
|
||||
|
אנסה להוכיח טענתי הקודמת (הסיכוי שזוג האדומים האחרונים צמוד זהה לסיכוי של כל זוג אדומים עוקבים אחר) בריגורוזית: נניח בנקודה מסויימת חשפנו n אדומים ו-k שחורים (האחרון אדום). הסיכוי שהקלף הבא אדום: (N-n)/(2N-n-k) הסיכוי שזוג הקלפים הבא הוא שחור+אדום:(N-k)/(2N-n-k)*(N-n)/(2N-n-k+1) הסיכוי שזוג הקלפים הבא הוא אדום+אדום:(N-n)/(2N-n-k)*(N-n-1)/(2N-n-k+1) כלומר הסיכוי שהקלף שאחרי הבא יהיה אדום (סכום 2 הביטויים הקודמים) הוא שוב:(N-n)/(2N-n-k) מכאן שכאמור אין טעם לעצור לפני חשיפת N-1 אדומים (שאז הסיכוי לאדום+אדום מתאפס).ועצה לחיים, ידידי הצעיר, התחושה כי בתחומי עסוקנו המדעיים, מוחות מתמטיים מבוגרים הופכים מהר מאוד לעוברים בטלים היא לצערי לעתים קרובות נכונה. דוקא לכן, זוהי איסטרטגיה טובה תמיד, לא לחשוף מחשבותינו בנידון. |
|
|
|
|
|
|
||
|
||||
|
בכל מקום שכתוב: (2N-n-k+1) צ"ל: (2N-n-k-1). |
|
|
|
|
|
|
||
|
||||
|
ראשית, הרשה לי להביע את התנצלותי: לרגע לא התכוונתי לזלזל, ורק בקריאה חוזרת של הודעותי הבנתי שכך יכולים להתפרש דברי. סליחה, באמת. אני מסכים אתך לחלוטין שההסתברות שזוג האדומים האחרון הוא צמוד היא זהה להסתברות שכל זוג אדומים עוקבים אחרים הוא צמוד. מאד יכול להיות שאני מחמיץ כאן משהו, אבל אני לא מצליח לראות למה זה נובע ממה שהראית. לפי דעתי, אתה הראית שלאחר שהוצאנו כבר n אדומים ו- k שחורים, ההסתברות שהקלף הבא יהיה אדום זהה לזו שהקלף שאחרי הבא יהיה אדום (וזוהי כמובן טענה נכונה, אבל אחרת). אני גם לא מצליח לראות איך כל הנ"ל עוזר לפתור את החידה המקורית. התוכל בבקשה להסביר ביתר פירוט, מההתחלה? ודבר אחרון: בעוד כמה שעות אני אתנתק מהמחשב לכמה ימים (טיול אופניים!), וייתכן שאקרא את תגובתך רק לאחר שאחזור. מתנצל מראש על העיכוב. |
|
|
|
|
|
|
||
|
||||
|
יש כאן 2 שאלות: א) אכן לא הוכחתי שיטתית, שהטענה שהוכחתי (כי הסיכוי שהקלף הבא יהיה אדום שווה לסיכוי שהקלף שאחריו יהיה אדום) שקולה לטענה שלא הוכחתי (בדבר ההסתברות האחידה של אדומים צמודים בתוך סדרת האדומים). זו רק התחושה שלי שהדברים שקולים. (אגב, שניהם נובעים מהעובדה שבחישוב ערכי תוחלת החשיבות של הסידורים האקראיים של הקלפים מתקזזת ומה שחשוב זו ההסתברות הזהה של כל קלף להיות אדום או שחור, בעיית "עשינו עסק"). ב) הטענה שהוכחתי פותרת לדעתי את הבעיה כך: בחר נקודה כלשהי בה השחקן עוצר ומחשב אם כדאי לו להפוך קלף נוסף או לעצור. בכל נקודה כזאת המצב הוא: אם לפניו שחור - בודאי כדאי לו להמשיך. אם לפניו אדום - מה הסיכוי שגם הקלף הבא אחריו הוא אדום? הראיתי שהסיכוי זהה לשני הקלפים. מכאן שבכל מקרה כדאי לו להמשיך. מצד אחד סיכויו לחשוף את כל הקלפים השחורים משתפרים ומצד שני סיכויו לעצור לפני קלף אדום אינם משתנים. כל זה נכון עד לחשיפת האדום הלפני האחרון כאשר לפי החישוב שהבאתי הסיכויים לעצירה לפני אדום יפחתו אם ימשיך, מה גם שהופעת אדום בחשיפה הבאה היא הפסד ודאי. |
|
|
|
|
|
|
||
|
||||
|
תוכל לפרט מהי בדיוק האסטרטגיה שאתה מציע, נניח במקרה פשוט של ארבעה קלפים (שני שחורים, שני אדומים)? אני ממש לא אומר שאתה טועה, רק שלא לגמרי הבנתי מה אתה מציע. אם לדעתך ארבעה קלפים אינם מספיקים בשביל לחשוף את היתרון של השיטה שלך, קח יותר. מה היתרון שאתה מסוגל להבטיח? כלומר, מה סיכוי הזכייה של שחקן המשחק לפי מתכונך, לעומת שחקן שסתם עוצר מתישהו? |
|
|
|
|
|
|
||
|
||||
|
נראה לי שנפלתי בפח. יהיה קשה למצוא איסטרטגיה עם סהסתברות הצלחה של יותר מ-50%. בכל אופן איפה שלא תעצור הסיכוי שהקלף הבא אדום זהה לסיכוי שהקלף שאחריו אדום. האיסטרטגיה שהצענו אינה טובה יותר מסתם לעצור בקלף אקראי. | |
|
|
|
|
|
||
|
||||
|
בוא ננסה להחליף את "יהיה קשה" ב"בלתי אפשרי". ניסיתי לכתוב הסבר אינטואיטיבי אבל כל הנסיונות שלי יצאו הרבה יותר ארוכים ומסורבלים מהתאור האינדוקטיבי הבא: הסתברות ההצלחה כאשר יש n אדומים ו- k שחורים הוא תמיד n/n+k. עבור n,k=0, ברור. אחרת אם מחליטים לעצור מיד - ברור. אם מחליטים להמשיך: סיכוי של n/n+k שיצא אדום ואז באינדוקציה n-1/n+k-1 להצליח. סיכוי של k/n+k שיצא שחור ואז באינדוקציה סיכוי של n/n+k-1 להצליח. סיכום שני המחוברים נותן בדיוק n/n+k. באופן אינטואיטיבי צריך להבין שכל אסטרטגיה משאירה את מרחב הקלפים סימטרי במובן אדום-שחור ופיצול בעץ האפשרויות ייתן שני צדדים כך שהרווח באחד יהיה זהה להפסד בשני. |
|
|
|
|
|
|
||
|
||||
|
זה אכן המצב, מה שדי מפתיע הרבה אנשים ששומעים את זה לראשונה. יש הסבר אינטואיטיבי ממש מוצלח, ושווה לחפש אותו. אגב, למען הקוראים הפחות מנוסים כדאי לציין שההוכחה שכתבת באינדוקציה לא מנוסחת בצורה לגמרי מדוייקת: עבור n=k=0 מקבלים 0/0 ולא ברור מה זה "ברור", וכאשר n+k=1 אתה לכאורה מקבל אפסים במכנה. סתם עניין של עריכה, וסליחה על הטרחנות. |
|
|
|
|
|
|
||
|
||||
|
טוב, הכנסתי את זה בכוונה, לא רציתי שהנוקדנים יטפלו לחלקים אחרים בהודעה... הכוונה ב- n,k=0 היא n=0 או k=0 ולא "וגם" (למעשה האופרטור המתאים כאן הוא xor אבל בוא לא נעמיק עד כדי כך). שים לב שכל מקרה בו n+k=1 מכוסה על ידי אחד מתנאי הקצה הללו. |
|
|
|
|
|
|
||
|
||||
|
שוב נמצאתי מוליך את הפותרים לטעות. ועל כן אשתדל לפחות לתקן המעוות. האתגר כרגע הוא למצוא איסטרטגיה בעלת סיכוי גדול מ-50%. יש לנו סה"כ N קלפים אדומים ו-N שחורים. עיינו באיסטרטגיות הבאות: הפסק כאשר הפכת n אדומים ו-k שחורים ומתקיים אחד מן המצבים הבאים: א) k=N, או ב) k-n>x, כאשר x שלם חיובי כלשהו. בהערכה ראשונית סיכויי ההצלחה באיסטרטגיות אלו עולים על חצי, כיון שבכל העצירות הלא ודאיות (מקרה ב) מספר האדומים שנותרו (N-n)עולה על מספר השחורים (N-k). ליתר דיוק, הסיכוי הוא "בערך": (N-n)/(2N-n-k)=(N-n)/(2N-2n-x)=0.5*(1/(1-(x/(2N-2n))) השאלה עכשיו היא מהו ה-x האופטימלי? הרצת כמה נסיונות מגלה את התשובה: התוחלת של ההצלחה היא אכן גדולה מחצי אך היא יורדת יחד עם ה-x, ולכן ה-x האופטימלי הוא 1. (עבור 2N=10 ו-x=1, ההצלחה היא 83.33%).ועכשיו לאזהרות (למען לא ניפול שוב): א) על פניו זו נראית איסטרטגיה טובה מאוד, אבל זה לא אומר שאין טובה ממנה. ב) יש לי "הוכחה" שככל שלוקחים x גדול יותר ההצלחה פוחתת. ההוכחה לא כל כך "מושלמת" ולכן עדיף להשאיר את הבמה לפיתרון מחוכם ומסודר יותר (וגם כדי להמנע מבשת פנים נוספת), אבל העובדה כנראה נכונה. ג) הסיבה שככל שמגדילים את x ההצלחה פוחתת נעוצה בכך שיש להפוך יותר קלפים כדי לגלות x יותר שחורים מאדומים (לפחות x קלפים) וכך מפסידים יותר ויותר אפשרויות זכייה (הנובעות מאדומים שהפכנו). הפסד זה מקזז את היתרון המושג בכך שאנו עוצרים רק עם סיכוי הצלחה מחמיר יותר. ד) סיכוי ההצלחה אינו הביטוי שכתבתי כאן. צריך ל"מצע" על כל ה-n האפשריים. כעת שהחזרתי אותכם למסלול הנכון, לא נותר אלא לצפות לפתרון המבריק והמלא של המכשלה הזאת. |
|
|
|
|
|
|
||
|
||||
|
הפעם זו היתה טעות בסימולציה. לאחר תיקון תוחלת ההצלחה היא הפלא ופלא: 50%. ולכן תגובה 162498 צודק. |
|
|
|
|
|
|
||
|
||||
|
אם עקבתי נכון, לא השתכנעת מההוכחה האינדוקטיבית של השור וניסית להפילו ע"י מציאת אסטרטגיה מוצלחת. זה הקסם בתוצאות לא אינטואיטיביות: גם אחרי שראית הוכחה, משהו ממשיך לרצות להראות את ההיפך. כאמור, יש נימוק מילולי קצר ונטול חישובים המסביר מדוע במשחק הזה אין שום חשיבות ל-"אסטרטגיה". אם רואים אותו, החשק לחפש דרכים לנצח את הבנק עובר לגמרי. אם נשבר לכם מלחפש אותו, זרקו מילה ונגאלכם מייסוריכם. אגב, אין לי שום כוונה או זכות להתנשא פה: אם אינני טועה גם אני פתרתי את השאלה בדרך הקשה. |
|
|
|
|
|
|
||
|
||||
|
טוב, הנה (ספוילר! מי שרוצה עוד לחשוב - לא לקרוא): אם השאלה המקורית היתה מנוסחת כך: השחקנית הופכת קלפים עד שמחליטה לעצור, ואז מביטים בקלף *האחרון בחפיסה* ולפיו קובעים האם ניצחה. מה סיכויי הניצחון? האם יש חשיבות להחלטה מתי לעצור? והאם, אחרי שהשחקן מהחידה המקורית עצר, יש הבדל בין סיכויי האדמומיות של הקלפים שעוד לא נחשפו, למשל בין הקלף *הבא* לקלף *האחרון*? יובל, מקווה שלא קילקלתי לך את ההנאה. לא אמרת מתי תשוב מטיול האופניים, והאלמוני כבר היה לחוץ... |
|
|
|
|
|
|
||
|
||||
|
לטעמי הספוילר שלך לא מספיק מקלקל את החשק להמשיך ועדיין אני מחכה להסבר המילולי המוחץ. עד כמה שאני מבין ההסבר שלך אינו שונה מהותית מההסבר של מ. השור תגובה 162498 שהיות ואף אני הבאתי משהו דומה תגובה 162324 (אם כי כשלתי בצורה מחפירה בשלב האחרון והקובע) אני מרשה לעצמי לחזור עליו תוך שינוי ההסבר המילולי: המשחק נוסח במקורו כך: לפניך סידור אקראי של N קלפים אדומים ו-N שחורים הפוכים. מותר להפוך ולחשוף קלפים עד לעצירה כרצונך. אם הקלף הבא אדום - זכית, שחור - הפסדת. כעת נניח שעצרת בנקודה כלשהי לאחר חשיפת n אדומים ו-k שחורים. אם תעצור כעת סיכוי ההצלחה שלך:(N-n)/(2N-n-k). אם לא תעצור ותמשיך, סיכוי ההצלחה שלך לאחר חשיפת קלף נוסף יהיה: (N-n)/(2N-n-k)*(N-n-1)/(2N-n-k-1)+(N-k)/(2N-n-k)*(N-n)/(2N-n-k-1)=(N-n)/(2N-n-k) כלומר אותו דבר. כלומר בשום נקודה בחפיסה אין יתרון מיוחד לעצירה או אי עצירה ואפשר להמשיך עד לחשיפת N שחורים. דא עקא שהסיכוי להגיע לחשיפת N שחורים (לפני הקלף האחרון, זכיה) זהה לסיכוי לחשוף N אדומים (הפסד).כלומר החיפוש אחר הסבר אינטואיטיבי מבריק נמשך. ברצוני להציג הסבר אחד. מאחר והיו לי כבר כמה הסברים מבריקים במיוחד אך גם שגויים במיוחד, אני סקרן לדעת אם ההסבר הבא נכון: הדבר היחידי שצ"ל בכל איסטרטגיה מוצלחת (מעל 50%) הוא עצירה רק כאשר k>n (כלומר יותר שחורים נחשפו). נבדוק את כל הקלפים האדומים בכל הסידורים האפשריים וננסה לגלות בכמה מקרים מתקיים התנאי הנ"ל. תחילה יש לבודד את המקרים בהם הקלף האחרון שנהפך הוא השחור האחרון בחפיסה. כנגד כל סידור כזה ישנו סידור המתקבל מהפיכת הצבע בסידור המקורי. כלומר כנגד כל זכיה ודאית קיים גם הפסד ודאי (חשיפת N אדומים). נוריד את כל המקרים האלו מן הדיון. שנית נשקול את המקרים בהם לפני הקלף האדום מתקיים n=k. לשם פשטות נניח שבמקרה כזה איננו עוצרים ולכן המקרים הנ"ל לא מעניינים ונוריד גם אותם. לבסוף נבדוק את המקרים בהם k>n (אך k<N). כנגד כל הסידורים השונים המקימים תנאי זה ישנו מספר זהה של סידורים, המתקבלים מהפיכת צבע הקלפים שלפני הקלף האדום הנידון (ובהם n>k). כלומר אם מתחשבים בכל הסידורים האפשריים (ללא הזכיות הודאיות שקיזזתי בנפרד), רק ב-50% מן המקרים מתקיים לפני קלף אדום התנאי k>n. כלומר האסטרטגיה תפספס אדומים במספר זהה למספר האדומים שיזוהו. הקשר לחידת שלושת הוילונות הוא רק זה שמה שקבע שם את התשובה היתה ההסתברות הזכיה של כל וילון (שליש) כאשר חישוב התוחלת מקזז את השפעת הבחירה האקראית הראשונית. גם כאן מה שקובע הוא שהסכוי של כל קלף להיות אדום או שחור הוא חצי, כאשר חישוב התוחלת מבטל את השפעת הסידור האקראי. |
|
|
|
|
|
|
||
|
||||
|
"לטעמי הספוילר שלך לא מספיק ..." - כי הוא לא נכון, לא ברור, או לא מספיק קצר? למרות שההסבר של מ. השור נכון לחלוטין, קשה לי לראות איך הוא לא שונה מהותית מה-"ספוילר", שאין בו אינדוקציה או חישוב כלשהו. ההסבר בפיסקה הראשונה שלך לא ברור לי לפחות: מדוע הגורם השני בכל מכפלה הוא מה שהוא? אתה הרי לא מניח שאחרי הפיכת קלף נוסף ישר נעצור. עליך להניח באינדוקציה את ערך המשחקים הפשוטים יותר, וזה בדיוק מה שמ. השור עשה. בכל אופן ההסבר ממש לא דומה להסבר המילולי הקצר שניסיתי לתאר. הנה הוא שוב, במילים אחרות: בכל שלב במשחק, הסיכוי שהקלף הבא יהיה אדום שווה לסיכוי שהקלף האחרון יהיה אדום (או כל קלף אחר שטרם נפתח); אבל הקלף האחרון הוא תמיד אותו קלף, והחלטת העצירה שלך אינה משפיעה על סיכוייו להיות אדום. זהו! כדי לא לענות את האיילים האומללים, אשמח להמשיך את הדיון איתך ב-e-mail. בסוף נפתור את אי-ההבנות. |
|
|
|
|
|
|
||
|
||||
|
אולי הפעם נתכנס. ההסבר שלי הוא באמצע, בין ההסבר של מ. השור להסבר שלך. כמוך איני משתמש באינדוקציה, אך לעומת זאת מחשב את ההסתברות של הקלף האחרון (או כל קלף לא הפוך אחר) להיות אדום. החישוב הוא כך: נניח שכבר הפכנו n אדומים ו-k שחורים. אם נחליט לעצור סיכוי הזכיה שוה לסיכוי של הקלף הבא להיות אדום (N-n)/(2N-n-k). אם נחליט להמשיך והקלף הבא יתגלה כאדום, הסיכוי של כ"א מן הקלפים הנותרים להיות אדום הוא (N-n-1)/(2N-n-1-k). סיכוי הזכיה במשחק בהנחה שנעצור לפני אחד מן הקלפים הנותרים (על סמך הידע שיש לנו כרגע) הוא (N-n)/(2N-n-k)*(N-n-1)/(2N-n-1-k). אם נוסיף לביטוי זה את סיכוי הזכיה במקרה שהקלף הבא הוא שחור, מקבלים סה"כ שוב (N-n)/(2N-n-k). זהו גם הסיכוי ברגע זה של הקלף האחרון (או כ"א מאלו שעדיין לא הפכנו) להיות אדום וגם הסיכוי הכולל לזכות במשחק אם נהפוך עוד קלף. בנקודה זו אני אומר שבין אם נעצור ובין אם נמשיך סיכוי הזכיה אינו משתנה ולכן בשום מקום במשחק אין מקום בו כדאי במיוחד לעצור. (שים לב שהסיכוי של האחרון להיות אדום אינו חצי כפי שהיה בתחילת המשחק אלא הוא נקבע ע"י התוחלת של כל הסידורים האפשריים כאשר n+k הראשונים ידועים). |
|
|
|
|
|
|
||
|
||||
|
תראה מה מפריע לי. בשלב האינדוקציה שלך אתה מחשב מה הסיכוי של כל אחד מן הקלפים הנסתרים להיות אדום, ומזה אתה גוזר בלי להניד עפעף שזהו גם "סיכוי הזכייה במשחק בהנחה שנעצור לפני אחד מן הקלפים הנותרים (על סמך הידע שיש לנו כרגע)". זה כמובן נכון, אבל *למה*? מדוע האסטרטגיה מכאן והלאה לא משפיעה על סיכוי הזכייה? הלא לפני שהשאלה נפתרה, האמנו שעבור כמות נתונה של אדומים ושחורים, אפשר לשחק יותר טוב או פחות טוב. אחת משתיים - או שאתה מניח שזה ברור אינטואיטיבית שהאסטרטגיה לא תשפיע, ואז מתעוררת השאלה, למה לא יישמת הבנה זו כבר בראשית המשחק כדי לטעון שסיכוי הזכייה הוא חצי וגמרנו? ואם אתה לא מניח זאת, עליך להוכיח זאת באינדוקציה, וזו ההוכחה של השור - אתה לא עושה זאת, מפני שאתה *מניח* את זה בשלב האינדוקציה. זו הסיבה שקשה לי להבין איזו מן הוכחה נמצאת "באמצע" בין ההסבר המילולי להוכחה באינדוקציה. לגבי המשפט האחרון שלך, חציו הראשון נכון לגמרי, אך חציו השני סתום בעיני. מה זה "התוחלת של כל הסידורים האפשריים"? תוחלת יש למשתנה מקרי, שהוא גודל מספרי. הסיכוי של האחרון להיות אדום הוא פשוט מספר האדומים שנותרו חלקי מספר הקלפים שנותרו. ככל שאתה חושף יותר קלפים אתה משנה את הערכתך לגבי סיכוי זה, אבל ברור שאינך משנה את צבעו של הקלף ולכן אין זה משנה כלום אם תפתח אותו ישר בהתחלה (כאשר הסיכוי להערכתך הוא חצי) או אחרי שפתחת שבעה-עשר קלפים, שישה מתוכם אדומים (שאז הערכתך היא אחרת). |
|
|
|
|
|
|
||
|
||||
|
אתחיל בחלק היותר קל. לגבי "התוחלת של כל הסידורים האפשריים". מה שאני אומר זה פשוט ההגדרה המדוייקת של הסתברות ה"אדומיות" של הקלף האחרון. למושג הזה אין משמעות עבור סידור קלפים מסויים אחד. נניח למשל 10 קלפים לאחר שנחשפו 2 אדום+3 שחור. סיכוי ה"אדומיות" של הקלף האחרון (ובכלל כל 5 הקלפים הנותרים) היא 3/5. מנין? ערוך לפניך את כל הסידורים האפשריים של 3 אדום+2 שחור. ב-3/5 מן הסידורים האלו הקלף האחרון הוא אדום. השאלה ששאלת בהתחלה היא יותר קשה לי. אנחנו מסכימים שה-3/5 הזה הוא גם סיכוי הזכיה במשחק בשלב זה. השאלה היא רק איך להוכיח זאת אינטואיטיבית או מילולית. יתכן וכאן מסתתרת איזו אינדוקציה. דרך אגב בספוילר שלך יש מצב ממש דומה. ראה תגובה 163475 |
|
|
|
|
|
|
||
|
||||
|
ה-email שלי לא פועל מאתמול, לכן אטריד את מנוחת האיילים עוד מעט. את הספוילר הבנתי יותר בהסבר השני אבל עדיין חסרה לי שורת המחץ בסיום. הבנתי שבכל נקודה במשחק סיכויי הזכיה שוים לסיכויי ה"אדומיות" של הקלף האחרון (אבל סיכוי זה משתנה בכל מצב ואינו דוקא חצי. סיכוי זה בלאו הכי אין לו משמעות בסידור ספציפי אלא רק באוסף כל הסידורים האפשריים). איך מגיעים מהנקודה הזאת לסיכוי האדומיות של הקלף האחרון על כל הסידורים האפשריים, שהוא חצי? | |
|
|
|
|
|
||
|
||||
|
אתה מבלבל את עצמך. ערבבת חפיסת קלפים. הנחת אותה הפוכה על שולחן. הקלף האחרון הוא או אדום או שחור, זה כבר נקבע רק שאתה לא יודע מה המצב. פעולות החשיפה שלך בראש החפיסה *לא משנות את הסיכוי שלו להיות אדום*, רק את *ההערכה שלך לגבי סיכוי זה*. אתה יודע שבסוף תהפוך את הקלף האחרון ותזכה אם הוא אדום. אם פתחת קלף ראשון וראית שחור, האם עכשיו "יותר כדאי לך" להפוך את האחרון משהיה כדאי לך לפני רגע? שני אנשים משחקים את המשחק במקביל. אחד חושף ישר את האחרון, ואחד פותח X קלפים (כל פעם X אחר, לפי אלגוריתם סבוך) ואז חושף את האחרון. יש למישהו מהם יתרון? לבסוף, ננסה לייצר אנלוגיה לחידת הווילונות. אומרים לך מראש שהווילון שתפתח הוא הימני ביותר. אין לך ברירה! אתה יכול לבקש מהמנחה לפתוח קודם את הוילון השמאלי, ואם בא לך אז גם את האמצעי. זה משנה משהו? |
|
|
|
|
|
|
||
|
||||
|
טוב, אני יכול להגיד משהו כמו ''אם אתה לא לוקח קלף - אתה משחק על ההסתברות שהקלף העליון אדום. אם אתה כן - אתה משחק על ההסתברות שהקלף הלפני-עליון אדום. בכל נקודה במשחק שתי ההסתברויות האלה שוות, אז לא משנה מה תחליט''. זה אפילו נשמע משכנע, אבל הבעיה (שלי) היא שזה נשמע משכנע גם ביחס לבעיה עם שלושת הווילונות... | |
|
|
|
|
|
||
|
||||
|
אני לא רואה את הדמיון לבעיית שלושת הוילונות - מה אני מחמיץ? בבעיית הוילונות (אם אתה מתכוון למה שאני מתכוון) המנחה חושף אינפורמציה - אם לא בחרת נכון (סיכוי 2/3), הוא מראה לך את הוילון האחד מבין השניים שלא בחרת שמאחוריו אין פרס, ובכך מבאר עבורך מהו הוילון מאחוריו *יש* פרס. מה האנלוגיה בחידת הקלפים? | |
|
|
|
|
|
||
|
||||
|
אין אנלוגיה (יש מטא-אנלוגיה שאין לי כח לנסח עכשיו). האם לדעתך ההסבר שנתתי נכון לחידת הקלפים? | |
|
|
|
|
|
||
|
||||
|
להבנתי ההסבר שלך נכון. ההבדל בין המשחק כאן לחידת הוילונות הוא: במשחק בכל נקודת החלטה סיכויי הזכייה בעצירה ובהמשך המשחק שוים ולכן לא משנה היכן עצרת. בחידת הוילונות סיכוי ההזכיה אם תדבוק בבחירתך הוא 1/3, ואם תחליף 2/3 ולכן הסתברותית כדאי להחליף. "סיכויי" הזכיה מחושבים לפי מספר הזכיות מתוך כל הסידורים האפשריים של הקלפים או של הפרס בוילונות. (מאחר ויש סידור פרס אחד שבו הוא נמצא בוילון שבחרת ו-2 סידורים בהם אינו שם, ברור איך חשבנו את סיכויי הזכיה). | |
|
|
|
|
|
||
|
||||
|
ברור לך ש"תנאי העצירה" שלך מתקיים בחלק די קטן של המקרים (משיקולי סימטריה, פחות מחצי עבור x חיובי). | |
|
|
|
|
|
||
|
||||
|
ראה תגובה 162768 | |
|
|
|
|
|
||
|
||||
|
בענין "עשינו עסק". טוב ערערת לי את הבטחון, אבל מה שחשבתי הוא בערך ככה. אחת הדרכים להסביר את החידה ההיא הוא להסביר כי האסטרטגיה הנכונה נקבעת ע"פ ערך התוחלת של סיכויי הזכייה. תוכלת משמעותה היא שיש לחזור על המשחק פעמים רבות תחת האסטרטגיה הנבחרת ולספור את הזכיות. בחישוב כזה הסיכוי שמכונית הפרס תהיה ב-2 הוילונות שלא בחרת הוא שליש+שליש (בלי תלות איזה וילון כן בחרת) מפני שזהו הפיזור של המכונית בין הוילונות. בחידה שלך, כשמחשבים תוחלת הצלחה, הקלף האדום הN-1-י או הN-2-י או ה.. יופיע כל פעם במקום אחר. אני מנחש שזה די אקויולנטי לבחירה אקראית של הקלף האדום הN-י או הN-1-י בתוך טווח מסויים. והסיכוי של קלף זה להיות אדום הוא באמת חצי. |
|
|
|
|
|
|
||
|
||||
|
לא רק שארדוש טעה, הוא גם נמנה עם אותם עקשנים שלא מוכנים לזוז מדעתם אחרי שהתשובה השגויה התקבעה במוחם, אותם הזכרתי בתגובה 355210 ורק סימולציה ממוחשבת שכנעה אותו לבסוף. אני תוהה אם סימולציה וירטואלית כפי שהדגמתי בקשר לבעיה אחרת בתגובה 528515 היתה עושה את העבודה. מכל מקום, כל זה רק תרוץ לספר לכם שפינקר מעביר קורס פתוח על רציונליות. |
|
|
|
|
|
|
||
|
||||
|
באותו קורס עצמו1 למדתי היום שגוטפריד לייבניץ, האיש שפיתח את החשבון האינפיניטיסימלי במקביל לניוטון, טען שהסיכוי לקבל דו-שש שווה לסיכוי לקבל שש-בש בהטלת שתי קוביות - שגיאה מקבילה לשגיאה הנפוצה בחידת הקלפים שפותחת את דיון 2518. אני מניח שגאונים מסוג לייבניץ וארדוש טועים לעתים רחוקות כל-כך עד שמתקבעת אצלם ההרגשה שהם לא טועים אף פעם - לפחות במה שנוגע לאינטואיציה המיידית בתחומי הגאונות שלהם - ולכן הם לא טורחים להתייחס ברצינות לרעיון שאולי למרות הכל יש טעם להטיל קוביות כמה עשרות פעמים ולראות מה קורה. הו, כמה חבל שלא יצא לי לשחק שש-בש מול היקה הפוץ! ______________ 1- בינתיים די משעמם |
|
|
|
|
|
|
||
|
||||
|
טוב, זה אגוז קטן ונחמד אבל די מוכר - לא אקלקל לכולם. אם אנחנו כבר בשוונג, וממילא עיצבנו את האייל ההומניסט מתגובה 161524, אז למה לא עוד אחת, קלה, מסוג אחר? מי שמכיר, נא להיות מנומס... *** תחרות לקוראי האייל *** *** התחרות פתוחה ומתאימה לכל *** *** לא רק לכמה סטודנטים לפיסיקה מהטכניון *** מנצח מי ששולח את המספר הגדול ביותר שהוא מכפלה של מספרים טבעיים שסכומם 100. שימו לב: לאו דווקא _שני_ מספרים טבעיים. הפרס: יופי של קארמה, שזה בדיוק ההיפך מעונשו של מי שמכיר את החידה ושולח כדי לצאת כאילו גדול. |
|
|
|
|
|
|
||
|
||||
|
2 בחזקת 50? 1125899906842624 |
|
|
|
|
|
|
||
|
||||
|
עוד לא הספקתי להרהר מספיק בענין (תרוצים, תרוצים...), אבל ארבע כפול שלש בחזקת שלשים ושנים נראה לי חביב. | |
|
|
|
|
|
||
|
||||
|
בהחלט! יפה מאוד. ממש ממש לא צריך מטלב בשביל לראות שזה (הרבה) יותר משתיים בחזקת חמישים - אבל האינטואיציה של הרבה אנשים מוליכה אותם להרבה פעמים שתיים. אפשר לכתוב את ההוכחה שזה אופטימלי בערך בשתי שורות, אם אף אחד אחר לא יעשה זאת אז אני אסביר. |
|
|
|
|
|
|
||
|
||||
|
או קיי, נדמה לי שפתרתי. אמנם לא פתרון של שתי שורות, אבל אני חושב שהוא נכון. נניח שנתונה לנו סדרת טבעיים שסכומם מאה, ונתבונן באבר 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). |
|
|
|
|
|
|
||
|
||||
|
נכון מאוד, אבל אפשר טיפה לקצר - כדאי להחליף כל m>3 ב-2 ו-(m-2), אין צורך להפריד לזוגיים ואי-זוגיים. | |
|
|
|
|
|
||
|
||||
|
מטלב אומר: 4*(3^32)-2^50 = +6.29e015
|
|
|
|
|
|
|
||
|
||||
|
אני חושב שדי קל להוכיח שהפתרון הזה אופטימלי. | |
|
|
|
|
|
||
|
||||
|
אתמול גיליתי שניתן לפתור את החידה גם בדרך נוספת לאלו שהועלו עד כה - על ידי משפט העצירה האופציונלית עבור מרטינגיילים. זה אמנם קצת overkill מתמטי, אבל עדיין נחמד (פירוט יינתן על פי דרישה). | |
|
|
|
|
|
||
|
||||
|
דרישה. אפשר גם בדואל, אם כמות המתעניינים הצפויה לדעתך קרובה להערכה שלי. אבל Overkill מזכיר לי רב-שיח חמוד שראיתי לאחרונה (אני מקווה שזה יעבוד בתרגום הצולע שלי): א': (פותר בעייה פשוטה בתותחים כבדים) ב' (משועשע): נו מה, א'? שוב מחסלים זבובים עם קורנסים? א' (נעלב): כאילו שלחסל זבוב עם קורנס זה כל כך קל. תנסה פעם. ג': היי, אם פעם אראה זבוב עם קורנס אני לא מתכוון להישאר בסביבה ולנסות להרוג אותו. |
|
|
|
|
|
|
||
|
||||
|
הנה. נניח שיש N קלפים אדומים ו- N שחורים. יהי I_n האינדיקטור של המאורע "הקלף ה- n הוא אדום", ותהי F_n הסיגמא-אלגברה הנוצרת על ידי I_1,...,I_n. אז {F_n} היא פילטרציה במרחב ההסתברות, והסדרה {I_n} כמובן מותאמת אליה. עוד נגדיר p_n = [N - I_1 - I_2 - ... - I_n]/(2N - n) כלומר p_n הוא סיכוי הזכייה אם עוצרים לאחר שליפת n קלפים. הסדרה {p_n} כמובן מותאמת גם לפילרטציה. בעזרת קצת אלגברה ותוצאות בסיסיות על תוחלת מותנית מקבלים שהסדרה {p_n} היא מרטינגייל ביחס לפילטרציה שלנו.היות שקבוצת הפרמטר של המרטינגייל היא חסומה על ידי 2N (או, לחילופין, היות שהסדרה {p_n} עצמה היא חסומה בין 0 ל- 1 בהסתברות 1), ניתן להפעיל את משפט ה- optional stopping למרטינגיילים האומר, במקרה שלנו, שלכל זמן עצירה T (המותאם לפילטרציה) מתקיים E[p_T] = E[p_0] = 1/2 במילים יותר פשוטות: אי אפשר לנצח את המערכת. כל כלל עצירה המתבסס על צבע הקלפים שנחשפו עד כה יניב הסתברות זכיה של 1/2 (שזה בדיוק מה שנקבל אם נעצור בלי להפוך אף קלף, והזכייה/הפסד ייקבעו על פי הקלף הראשון בחפיסה).
|
|
|
|
|
|
|
||
|
||||
|
נחמד מאוד. אני לא משוכנע שזו ממש ''דרך נוספת'' כי החשבון הבסיסי שלך, זה שמראה שזה באמת מרטינגייל, הוא בדיוק החשבון של מ. השור. אבל זו דרך מקורית ויפה להסתכל על זה. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |