בתשובה ליובל נוב, 07/08/03 8:32
חידה 162230
אם זכרוני אינו מטעני דפקת לי טיעון יפה (בענין שמואל זיגלבוים). אנסה להשיב לך כגמולך.
אם באיסטרטגיה אופטימלית אינך כולל דרישה למספר מינימלי של צעדים (אז אין סיכוי לעצלני מטלב כמוני) אז השאלה שלך בעצם דומה מאד לחידת שלושת הוילונות שהצליחה לבלבל גם מתמטיקאים מקצועיים.
אני מנחש כי האיסטרטגיה האופטימלית היא כפי שהציע המגיב הראשון היא להפוך קלפים עד שמגיעים ל-N-1 אדומים הפוכים או N שחורים, כמובן מה שבא קודם (מתוך סה"כ 2N קלפים). הפכת N שחורים קודם -זכית.
מה אם N-1 האדומים הגיעו קודם? נסתכל על המקרה הגרוע ביותר: הפכת N-1 קלפים וכולם אדומים. הקטצ' בחידות מסוג זה הוא שרבים מניחים כי הסיכוי שהקלף הבא יהיה אדום הוא
1 חלקי N+1. ולא היא. הסיכוי הוא חצי. כך שמה שעשינו במשכנו עד N-1 אדומים (ולא N-2 למשל) הוא להגביר את הסיכוי למשוך N שחורים ולזכות ולא הגדלנו את הסיכוי להפסיד במאום.
אם תהיה דרישת קהל אשמח לנסות להסביר מילולית מדוע הסיכוי הוא חצי ולא אחרת.
הקהל דורש! 162237
הסבר.

ההסתברות (המותנית, לאחר שהוצאו כבר N-1 אדומים) מן הסתם אינה 1 ל- N+1 , אבל מדוע אינה 1 חלקי מספר הקלפים שעוד נותרו?
סליחה טעות 162244
פשוט טעיתי. דברתי על מקרה בו יצאו N-1 אדומים רצופים ואז הסיכוי שהקלף הבא יהיה אדום הוא אכן 1 חלקי N+1 ולא חצי כפי שטענתי בחוצפתי. מה שכנראה הייתי צריך להגיד הוא שהסיכוי שלאחר משיכת N-1 (או כל מספר קבוע אחר) קלפים אדומים בדיוק, יבוא קלף אדום היא חצי.
מספר הקלפים שצריך למשוך כדי למשוך בדיוק
X אדומים הוא בין X לN+X. ולכן הסיכוי שהקלף הבא יהיה אף הוא אדום זהה לסיכוי שבחירת קלף אקראי בתחום זה תתן קלף אדום (כאמור חצי). הסבר מסודר יותר, אם אני צודק ואם אמצא כזה בהמשך.
חידה 162241
אילו הייתי יודע שתנטור לי טינה בגלל זיגלבוים אולי לא הייתי נענה לאתגר שלך אז... :)

אני בכוונה עדיין לא אומר האם האסטרטגיה שק. נבוך ואתה הצעתם היא אופטימלית. כשתנתן התשובה המלאה (והיא עדיין לא ניתנה), יהיה ברור למה.

ומשהו אחר: אני חולק על קביעתך שההסתברות לקבל קלף אדום אחרי רצף של N-1 אדומים (ואף שחור) היא חצי ולא 1 חלקי N+1. אני אכן יודע שחידת שלושת הוילונות הצליחה לבלבל גם מתמטיקאים מקצועיים (כולל את ארדוש, אם אני זוכר נכון מהביוגרפיה שלו), אבל בתור מי שסבור שהוא מכיר חידה זו היטב (יצא לי גם ללמד אותה כמתרגל בטכניון בקורס בהסתברות), דומני שהיא לא רלוונטית כאן.

למתעניינים: חידת שלושת הוילונות ידוע גם בשמות "הפרדוקס של מונטי הול" ו"עשינו עסק". פרטים ב- http://math.ucsd.edu/~crypto/Monty/Montytitle.html
נסיון אחרון ודי 162250
על פניו נראה שהסיכוי שהאדום ה-Nי והN-1י יהיו צמודים זהה לסיכוי שהN-2י והN-1י יהיו צמודים וכן הלאה. לכן אין שום יתרון בעצירה בקלף האדום הN-2י אלא רק חסרון של הקטנת הסיכוי להשלים N-יה שלמה של שחורים.
דרך אגב, מנין הידע הזיגלבוימי? אני עצמי לא הצלחתי לזכור את השם.
נסיון אחרון ודי 162278
על זיגלבוים שמעתי במסגרת משלחת תלמידים לפולין בכיתה י"א.

ובנוגע לחידה: אולי עדיף לחכות עוד כמה ימים, ואחד מקומץ האיילים שמתעניין בפתיל זה יעלה על התשובה המלאה.
היה צליל זלזול 162324
אנסה להוכיח טענתי הקודמת (הסיכוי שזוג האדומים האחרונים צמוד זהה לסיכוי של כל זוג אדומים עוקבים אחר) בריגורוזית:
נניח בנקודה מסויימת חשפנו 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 אדומים (שאז הסיכוי לאדום+אדום מתאפס).
ועצה לחיים, ידידי הצעיר, התחושה כי בתחומי עסוקנו המדעיים, מוחות מתמטיים מבוגרים הופכים מהר מאוד לעוברים בטלים היא לצערי לעתים קרובות נכונה. דוקא לכן, זוהי איסטרטגיה טובה תמיד, לא לחשוף מחשבותינו בנידון.
errata 162351
בכל מקום שכתוב:
(2N-n-k+1) צ"ל: (2N-n-k-1).
היה צליל זלזול 162379
ראשית, הרשה לי להביע את התנצלותי: לרגע לא התכוונתי לזלזל, ורק בקריאה חוזרת של הודעותי הבנתי שכך יכולים להתפרש דברי. סליחה, באמת.

אני מסכים אתך לחלוטין שההסתברות שזוג האדומים האחרון הוא צמוד היא זהה להסתברות שכל זוג אדומים עוקבים אחרים הוא צמוד. מאד יכול להיות שאני מחמיץ כאן משהו, אבל אני לא מצליח לראות למה זה נובע ממה שהראית. לפי דעתי, אתה הראית שלאחר שהוצאנו כבר n אדומים ו- k שחורים, ההסתברות שהקלף הבא יהיה אדום זהה לזו שהקלף שאחרי הבא יהיה אדום (וזוהי כמובן טענה נכונה, אבל אחרת).

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

ודבר אחרון: בעוד כמה שעות אני אתנתק מהמחשב לכמה ימים (טיול אופניים!), וייתכן שאקרא את תגובתך רק לאחר שאחזור. מתנצל מראש על העיכוב.
היה צליל זלזול 162397
יש כאן 2 שאלות:
א) אכן לא הוכחתי שיטתית, שהטענה שהוכחתי (כי הסיכוי שהקלף הבא יהיה אדום שווה לסיכוי שהקלף שאחריו יהיה אדום) שקולה לטענה שלא הוכחתי (בדבר ההסתברות האחידה של אדומים צמודים בתוך סדרת האדומים). זו רק התחושה שלי שהדברים שקולים. (אגב, שניהם נובעים מהעובדה שבחישוב ערכי תוחלת החשיבות של הסידורים האקראיים של הקלפים מתקזזת ומה שחשוב זו ההסתברות הזהה של כל קלף להיות אדום או שחור, בעיית "עשינו עסק").
ב) הטענה שהוכחתי פותרת לדעתי את הבעיה כך: בחר נקודה כלשהי בה השחקן עוצר ומחשב אם כדאי לו להפוך קלף נוסף או לעצור. בכל נקודה כזאת המצב הוא: אם לפניו שחור - בודאי כדאי לו להמשיך. אם לפניו אדום - מה הסיכוי שגם הקלף הבא אחריו הוא אדום? הראיתי שהסיכוי זהה לשני הקלפים. מכאן שבכל מקרה כדאי לו להמשיך. מצד אחד סיכויו לחשוף את כל הקלפים השחורים משתפרים ומצד שני סיכויו לעצור לפני קלף אדום אינם משתנים. כל זה נכון עד לחשיפת האדום הלפני האחרון כאשר לפי החישוב שהבאתי הסיכויים לעצירה לפני אדום יפחתו אם ימשיך, מה גם שהופעת אדום בחשיפה הבאה היא הפסד ודאי.
אני לא בטוח שהבנתי... 162409
תוכל לפרט מהי בדיוק האסטרטגיה שאתה מציע, נניח במקרה פשוט של ארבעה קלפים (שני שחורים, שני אדומים)? אני ממש לא אומר שאתה טועה, רק שלא לגמרי הבנתי מה אתה מציע.

אם לדעתך ארבעה קלפים אינם מספיקים בשביל לחשוף את היתרון של השיטה שלך, קח יותר. מה היתרון שאתה מסוגל להבטיח? כלומר, מה סיכוי הזכייה של שחקן המשחק לפי מתכונך, לעומת שחקן שסתם עוצר מתישהו?
אני לא בטוח שהבנתי... 162425
נראה לי שנפלתי בפח. יהיה קשה למצוא איסטרטגיה עם סהסתברות הצלחה של יותר מ-‏50%. בכל אופן איפה שלא תעצור הסיכוי שהקלף הבא אדום זהה לסיכוי שהקלף שאחריו אדום. האיסטרטגיה שהצענו אינה טובה יותר מסתם לעצור בקלף אקראי.
אני לא בטוח שהבנתי... 162498
בוא ננסה להחליף את "יהיה קשה" ב"בלתי אפשרי".

ניסיתי לכתוב הסבר אינטואיטיבי אבל כל הנסיונות שלי יצאו הרבה יותר ארוכים ומסורבלים מהתאור האינדוקטיבי הבא:

הסתברות ההצלחה כאשר יש 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.

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

אגב, למען הקוראים הפחות מנוסים כדאי לציין שההוכחה שכתבת באינדוקציה לא מנוסחת בצורה לגמרי מדוייקת: עבור n=k=0 מקבלים 0/0 ולא ברור מה זה "ברור", וכאשר n+k=1 אתה לכאורה מקבל אפסים במכנה. סתם עניין של עריכה, וסליחה על הטרחנות.
אני לא בטוח שהבנתי... 162514
טוב, הכנסתי את זה בכוונה, לא רציתי שהנוקדנים יטפלו לחלקים אחרים בהודעה...

הכוונה ב- n,k=0 היא n=0 או k=0 ולא "וגם" (למעשה האופרטור המתאים כאן הוא xor אבל בוא לא נעמיק עד כדי כך). שים לב שכל מקרה בו n+k=1 מכוסה על ידי אחד מתנאי הקצה הללו.
במקום שבעלי תשובה ... 162742
שוב נמצאתי מוליך את הפותרים לטעות. ועל כן אשתדל לפחות לתקן המעוות. האתגר כרגע הוא למצוא איסטרטגיה בעלת סיכוי גדול מ-‏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 האפשריים.

כעת שהחזרתי אותכם למסלול הנכון, לא נותר אלא לצפות לפתרון המבריק והמלא של המכשלה הזאת.
errata 162749
בתנאי עצירה (ב) צ"ל:
k-n>=x
errata big time 162768
הפעם זו היתה טעות בסימולציה. לאחר תיקון תוחלת ההצלחה היא הפלא ופלא: 50%.
ולכן תגובה 162498 צודק.
errata big time 162824
אם עקבתי נכון, לא השתכנעת מההוכחה האינדוקטיבית של השור וניסית להפילו ע"י מציאת אסטרטגיה מוצלחת. זה הקסם בתוצאות לא אינטואיטיביות: גם אחרי שראית הוכחה, משהו ממשיך לרצות להראות את ההיפך.

כאמור, יש נימוק מילולי קצר ונטול חישובים המסביר מדוע במשחק הזה אין שום חשיבות ל-"אסטרטגיה". אם רואים אותו, החשק לחפש דרכים לנצח את הבנק עובר לגמרי. אם נשבר לכם מלחפש אותו, זרקו מילה ונגאלכם מייסוריכם. אגב, אין לי שום כוונה או זכות להתנשא פה: אם אינני טועה גם אני פתרתי את השאלה בדרך הקשה.
נשבר 163029
נשבר 163059
טוב, הנה (ספוילר! מי שרוצה עוד לחשוב - לא לקרוא):

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

יובל, מקווה שלא קילקלתי לך את ההנאה. לא אמרת מתי תשוב מטיול האופניים, והאלמוני כבר היה לחוץ...
נשבר 163301
לטעמי הספוילר שלך לא מספיק מקלקל את החשק להמשיך ועדיין אני מחכה להסבר המילולי המוחץ.
עד כמה שאני מבין ההסבר שלך אינו שונה מהותית מההסבר של מ. השור תגובה 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. כלומר האסטרטגיה תפספס אדומים במספר זהה למספר האדומים שיזוהו.
הקשר לחידת שלושת הוילונות הוא רק זה שמה שקבע שם את התשובה היתה ההסתברות הזכיה של כל וילון (שליש) כאשר חישוב התוחלת מקזז את השפעת הבחירה האקראית הראשונית. גם כאן מה שקובע הוא שהסכוי של כל קלף להיות אדום או שחור הוא חצי, כאשר חישוב התוחלת מבטל את השפעת הסידור האקראי.
נשבר 163344
"לטעמי הספוילר שלך לא מספיק ..." - כי הוא לא נכון, לא ברור, או לא מספיק קצר? למרות שההסבר של מ. השור נכון לחלוטין, קשה לי לראות איך הוא לא שונה מהותית מה-"ספוילר", שאין בו אינדוקציה או חישוב כלשהו.

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

בכל אופן ההסבר ממש לא דומה להסבר המילולי הקצר שניסיתי לתאר. הנה הוא שוב, במילים אחרות: בכל שלב במשחק, הסיכוי שהקלף הבא יהיה אדום שווה לסיכוי שהקלף האחרון יהיה אדום (או כל קלף אחר שטרם נפתח); אבל הקלף האחרון הוא תמיד אותו קלף, והחלטת העצירה שלך אינה משפיעה על סיכוייו להיות אדום. זהו!

כדי לא לענות את האיילים האומללים, אשמח להמשיך את הדיון איתך ב-e-mail. בסוף נפתור את אי-ההבנות.
נשבר 163384
אולי הפעם נתכנס. ההסבר שלי הוא באמצע, בין ההסבר של מ. השור להסבר שלך. כמוך איני משתמש באינדוקציה, אך לעומת זאת מחשב את ההסתברות של הקלף האחרון (או כל קלף לא הפוך אחר) להיות אדום. החישוב הוא כך: נניח שכבר הפכנו 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 הראשונים ידועים).
נשבר 163473
תראה מה מפריע לי. בשלב האינדוקציה שלך אתה מחשב מה הסיכוי של כל אחד מן הקלפים הנסתרים להיות אדום, ומזה אתה גוזר בלי להניד עפעף שזהו גם "סיכוי הזכייה במשחק בהנחה שנעצור לפני אחד מן הקלפים הנותרים (על סמך הידע שיש לנו כרגע)". זה כמובן נכון, אבל *למה*? מדוע האסטרטגיה מכאן והלאה לא משפיעה על סיכוי הזכייה? הלא לפני שהשאלה נפתרה, האמנו שעבור כמות נתונה של אדומים ושחורים, אפשר לשחק יותר טוב או פחות טוב.

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

זו הסיבה שקשה לי להבין איזו מן הוכחה נמצאת "באמצע" בין ההסבר המילולי להוכחה באינדוקציה.

לגבי המשפט האחרון שלך, חציו הראשון נכון לגמרי, אך חציו השני סתום בעיני. מה זה "התוחלת של כל הסידורים האפשריים"? תוחלת יש למשתנה מקרי, שהוא גודל מספרי. הסיכוי של האחרון להיות אדום הוא פשוט מספר האדומים שנותרו חלקי מספר הקלפים שנותרו. ככל שאתה חושף יותר קלפים אתה משנה את הערכתך לגבי סיכוי זה, אבל ברור שאינך משנה את צבעו של הקלף ולכן אין זה משנה כלום אם תפתח אותו ישר בהתחלה (כאשר הסיכוי להערכתך הוא חצי) או אחרי שפתחת שבעה-עשר קלפים, שישה מתוכם אדומים (שאז הערכתך היא אחרת).
נשבר 163476
אתחיל בחלק היותר קל. לגבי "התוחלת של כל הסידורים האפשריים". מה שאני אומר זה פשוט ההגדרה המדוייקת של הסתברות ה"אדומיות" של הקלף האחרון. למושג הזה אין משמעות עבור סידור קלפים מסויים אחד. נניח למשל 10 קלפים לאחר שנחשפו 2 אדום+3 שחור. סיכוי ה"אדומיות" של הקלף האחרון (ובכלל כל 5 הקלפים הנותרים) היא 3/5. מנין? ערוך לפניך את כל הסידורים האפשריים של 3 אדום+2 שחור. ב-‏3/5 מן הסידורים האלו הקלף האחרון הוא אדום.
השאלה ששאלת בהתחלה היא יותר קשה לי. אנחנו מסכימים שה-‏3/5 הזה הוא גם סיכוי הזכיה במשחק בשלב זה. השאלה היא רק איך להוכיח זאת אינטואיטיבית או מילולית. יתכן וכאן מסתתרת איזו אינדוקציה. דרך אגב בספוילר שלך יש מצב ממש דומה. ראה תגובה 163475
נשבר 163475
ה-email שלי לא פועל מאתמול, לכן אטריד את מנוחת האיילים עוד מעט. את הספוילר הבנתי יותר בהסבר השני אבל עדיין חסרה לי שורת המחץ בסיום. הבנתי שבכל נקודה במשחק סיכויי הזכיה שוים לסיכויי ה"אדומיות" של הקלף האחרון (אבל סיכוי זה משתנה בכל מצב ואינו דוקא חצי. סיכוי זה בלאו הכי אין לו משמעות בסידור ספציפי אלא רק באוסף כל הסידורים האפשריים). איך מגיעים מהנקודה הזאת לסיכוי האדומיות של הקלף האחרון על כל הסידורים האפשריים, שהוא חצי?
נשבר 163477
אתה מבלבל את עצמך. ערבבת חפיסת קלפים. הנחת אותה הפוכה על שולחן. הקלף האחרון הוא או אדום או שחור, זה כבר נקבע רק שאתה לא יודע מה המצב. פעולות החשיפה שלך בראש החפיסה *לא משנות את הסיכוי שלו להיות אדום*, רק את *ההערכה שלך לגבי סיכוי זה*.

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

שני אנשים משחקים את המשחק במקביל. אחד חושף ישר את האחרון, ואחד פותח X קלפים (כל פעם X אחר, לפי אלגוריתם סבוך) ואז חושף את האחרון. יש למישהו מהם יתרון?

לבסוף, ננסה לייצר אנלוגיה לחידת הווילונות. אומרים לך מראש שהווילון שתפתח הוא הימני ביותר. אין לך ברירה! אתה יכול לבקש מהמנחה לפתוח קודם את הוילון השמאלי, ואם בא לך אז גם את האמצעי. זה משנה משהו?
errata big time 163055
טוב, אני יכול להגיד משהו כמו ''אם אתה לא לוקח קלף - אתה משחק על ההסתברות שהקלף העליון אדום. אם אתה כן - אתה משחק על ההסתברות שהקלף הלפני-עליון אדום. בכל נקודה במשחק שתי ההסתברויות האלה שוות, אז לא משנה מה תחליט''. זה אפילו נשמע משכנע, אבל הבעיה (שלי) היא שזה נשמע משכנע גם ביחס לבעיה עם שלושת הווילונות...
וילונות? 163062
אני לא רואה את הדמיון לבעיית שלושת הוילונות - מה אני מחמיץ? בבעיית הוילונות (אם אתה מתכוון למה שאני מתכוון) המנחה חושף אינפורמציה - אם לא בחרת נכון (סיכוי 2/3), הוא מראה לך את הוילון האחד מבין השניים שלא בחרת שמאחוריו אין פרס, ובכך מבאר עבורך מהו הוילון מאחוריו *יש* פרס. מה האנלוגיה בחידת הקלפים?
וילונות? 163063
אין אנלוגיה (יש מטא-אנלוגיה שאין לי כח לנסח עכשיו). האם לדעתך ההסבר שנתתי נכון לחידת הקלפים?
וילונות? 163466
להבנתי ההסבר שלך נכון. ההבדל בין המשחק כאן לחידת הוילונות הוא: במשחק בכל נקודת החלטה סיכויי הזכייה בעצירה ובהמשך המשחק שוים ולכן לא משנה היכן עצרת. בחידת הוילונות סיכוי ההזכיה אם תדבוק בבחירתך הוא 1/3, ואם תחליף 2/3 ולכן הסתברותית כדאי להחליף. "סיכויי" הזכיה מחושבים לפי מספר הזכיות מתוך כל הסידורים האפשריים של הקלפים או של הפרס בוילונות. (מאחר ויש סידור פרס אחד שבו הוא נמצא בוילון שבחרת ו-‏2 סידורים בהם אינו שם, ברור איך חשבנו את סיכויי הזכיה).
לרבע את המעגל 162782
ברור לך ש"תנאי העצירה" שלך מתקיים בחלק די קטן של המקרים (משיקולי סימטריה, פחות מחצי עבור x חיובי).
התנצלותי המלאה 163441
ראה תגובה 162768
חידה 162265
בענין "עשינו עסק". טוב ערערת לי את הבטחון, אבל מה שחשבתי הוא בערך ככה.
אחת הדרכים להסביר את החידה ההיא הוא להסביר כי האסטרטגיה הנכונה נקבעת ע"פ ערך התוחלת של סיכויי הזכייה. תוכלת משמעותה היא שיש לחזור על המשחק פעמים רבות תחת האסטרטגיה הנבחרת ולספור את הזכיות. בחישוב כזה הסיכוי שמכונית הפרס תהיה ב-‏2 הוילונות שלא בחרת הוא שליש+שליש (בלי תלות איזה וילון כן בחרת) מפני שזהו הפיזור של המכונית בין הוילונות.
בחידה שלך, כשמחשבים תוחלת הצלחה, הקלף האדום הN-1-י או הN-2-י או ה.. יופיע כל פעם במקום אחר. אני מנחש שזה די אקויולנטי לבחירה אקראית של הקלף האדום הN-י או הN-1-י בתוך טווח מסויים. והסיכוי של קלף זה להיות אדום הוא באמת חצי.
ארדוש 713216
לא רק שארדוש טעה, הוא גם נמנה עם אותם עקשנים שלא מוכנים לזוז מדעתם אחרי שהתשובה השגויה התקבעה במוחם, אותם הזכרתי בתגובה 355210 ורק סימולציה ממוחשבת שכנעה אותו לבסוף. אני תוהה אם סימולציה וירטואלית כפי שהדגמתי בקשר לבעיה אחרת בתגובה 528515 היתה עושה את העבודה.

מכל מקום, כל זה רק תרוץ לספר לכם שפינקר מעביר קורס פתוח על רציונליות.
במסגרת פינתנו ''שיימינג לכל'' 713846
באותו קורס עצמו‏1 למדתי היום שגוטפריד לייבניץ, האיש שפיתח את החשבון האינפיניטיסימלי במקביל לניוטון, טען שהסיכוי לקבל דו-שש שווה לסיכוי לקבל שש-בש בהטלת שתי קוביות - שגיאה מקבילה לשגיאה הנפוצה בחידת הקלפים שפותחת את דיון 2518. אני מניח שגאונים מסוג לייבניץ וארדוש טועים לעתים רחוקות כל-כך עד שמתקבעת אצלם ההרגשה שהם לא טועים אף פעם - לפחות במה שנוגע לאינטואיציה המיידית בתחומי הגאונות שלהם - ולכן הם לא טורחים להתייחס ברצינות לרעיון שאולי למרות הכל יש טעם להטיל קוביות כמה עשרות פעמים ולראות מה קורה.

הו, כמה חבל שלא יצא לי לשחק שש-בש מול היקה הפוץ!
______________
1- בינתיים די משעמם

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים