בתשובה לאלון עמית, 09/08/03 18:00
 |
|
 |
||
|
||||
 |
טוב, הכנסתי את זה בכוונה, לא רציתי שהנוקדנים יטפלו לחלקים אחרים בהודעה... הכוונה ב- 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 | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |