חידה 161136
מאחר והטריוויה שלי הייתה קלה מידי, ודי הרסתי את זו של רון, אז הרי חידה ששמעתי לא מזמן כפיצוי:

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

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

האם אתה יודע מה האסטרטגיה המיטבית?
חידה 161162
אני לא חושב שזו האסטרטגייה הטובה ביותר.

הסיבה שאני מסייג זה כי אני יודע את התשובה רק נומרית - סימלצתי הכל במטלב, וראיתי מה הכי הרבה רווח שאפשר להוציא בסיכוי טוב. אשמח לפתרון יותר אינטליגנטי.
חידה 161163
האסטרטגיה הטובה ביותר היא זו עם תוחלת הרווח הגדולה ביותר, כן? אני מבין שאינך יודע מה האסטרטגיה המיטבית אולם יש לך אסטרטגיה שתוחלת הרווח שלה גדולה משל האסטרטגיה שהצעתי, אבל גם בכך אינך משוכנע כי הסימולציה שלך לא כללה את כל ה-‏52 מעל 26 אפשרויות. נכון? האם ניסית לבדוק אותה במלואה על חפיסה בת 8 קלפים, למשל?
חידה 161165
כל סדרה סופית של משחקים עם תוחלת 0
תניב תוחלת 0. אם המטרה היא אחרת,
נא לציין זאת בחידה.
חידה 161169
אנו דנים בתוחלת הרווח של אסטרטגיות שונות במשחק הנתון. לי (וכנראה גם לגלעד) אסטרטגיות שתוחלת הרווח שלהן חיובית, ובפרט אינה 0. החידה היא מהי האסטרטגיה שתוחלת הרווח שלה היא המירבית. כל אסטרטגיה שתוצג תקבע חסם מלרע על התוחלת (וכאמור אנו כבר יודעים שהחסם הוא חיובי). גם הצגת חסם מלעיל לא-טריוויאלי תבורך, במיוחד אם החסם זהה לחסם מלרע שהוצג.
חידה 161170
התוחלת היא אפס רק במשיכה הראשונה - אחר כך יש שוני במספר הקלפים השחורים והאדומים שנשארו בחפיסה.

התוחלת של המשחק כולו היא בברור חיובית - הרי אם תמשוך את כל הקלפים, תצא על אפס, אז אם תפסיק ברגע שמשכת 26 אדומים, ונארו עוד קלפים בחבילה, הרווחת. (לא האסטרטגיה המיטבית).
חידה 161172
אבל איך זה יעזור לי? אז אני אקבל את התוחלת למשחק של 8 קלפים. יש. הסימולציה שלי אומרת לי כרגע "אם יש לך בקופה X שקלים, הפסק למשוך" (לגלות את X?), ודי סביר שזה נכון, אבל א. - מי אמר שזה נכון, אפילו אם אני אריץ על כל האפשרויות למשחק של 8 קלפים וב. - זה לא כל כך מעניין. אני רוצה לדעת למה, לא רק כמה.
חידה 161174
אתה לא יכול להתאים את X למקרה של 8 קלפים? הרי בטח הגעת ל-X דרך 52. או שבדקת רק אסטרטגיות מסוג "אם יש לך בקופה X שקלים, הפסק למשוך", ומבין אלה, עבור מדגם של חפיסות 52 קלפים ועבור מדגם של Xים גילית שיש ערך X שונה מ-‏1 המביא לתוחלת גבוהה מ- 26/27 ?

א. מה זה "זה"? שהאסטרטגיה המיטבית היא מסוג "אם יש לך בקופה X שקלים, הפסק"?
עדכון 161197
רבע דף A4 הספיק לניתוח המשחק בן 4 קלפים (כלומר לבחינת *כל* האסטרטגיות). במקרה זה, האסטרטגיה המיטבית אינה מטיפוס "אם יש לך בקופה X שקלים, הפסק למשוך", ותוחלת הרווח שלה היא 7/8. לכן קשה לי להאמין שבמקרה המורכב יותר של 52 קלפים, האסטרטגיה המיטבית תהייה מהטיפוס הנ"ל. (עם זאת, מבין האסטרטגיות הנ"ל, עבור 4 קלפים המנצחת היא כמובן X=1 ). אני חושש שאין לי די נייר וסבלנות לניתוח המשחק בן 6 הקלפים.
רבותי נברר 161200
בשלב כלשהו במשחק, יש לפנינו n קלפים אדומים ו-k קלפים שחורים. עלינו לקבל החלטה: האם למשוך קלף, או לעצור? ההחלטה תלויה אך ורק במספרים n ו-k, ולא במה שהרווחנו עד כה. אם קביעה זו טעונה הסבר, אשמח להסביר.

איך לקבל את ההחלטה? נניח שלצדנו פיה טובה היודעת להשיב על השאלה הבאה: מהי תוחלת הרווח ממשחק עם n אדומים ו-k שחורים, אם נשחק בצורה מיטבית? הפיה איננה אומרת איך יש לשחק, רק מהי תוחלת הרווח אם משחקים נכון.

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

(+) נמשוך קלף אדום, נרוויח שקל, ונגיע למצב שבו לפנינו n-1 קלפים אדומים ו-k שחורים.

(-) נמשוך קלף שחור, נפסיד שקל, ונגיע למצב שבו לפנינו n קלפים אדומים ו- k-1 שחורים.

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

עכשיו זה קל: אם תוחלת זו חיובית, יש למשוך. אם היא שלילית, יש לעצור ולהסתפק ב-‏0.

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

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

אם יש רק קלף אחד אדום וקלף אחד שחור, תוחלת הרווח היא מחצית השקל.

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

במשחק עם 8 אדומים ו-‏8 שחורים, תוחלת הרווח היא 1.43411.

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

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

- אלון
רבותי נברר 161218
טוב, העובדה שקיימת אסטרטגיה מיטבית ברורה, וכך גם העובדה שניתן לחשב אותה כפי שהצעת. מניתוח המשחק ה-‏4-קלפי כבר עולה שהאסטרטגיה המיטבית אינה כלל התלוי רק במה שהרווחנו עד כה, כך שאתה לא צפוי להפתעות. השאלה המעניינת היא מה הנוסחא לתוחלת המירבית במשחק עם 2n קלפים.
תיקון 161217
התוחלת במשחק בן ארבעת הקלפים היא 5/6. במשחק עם שישה קלפים, 19/20.
תיקון 161220
אתה בטוח? לדעתי, התוחלת במשחק עם ארבעה קלפים (שני אדומים, שני שחורים) היא 2/3. הבה נראה: האם אתה מסכים שהמצב (אדום, שני שחורים) שווה 0? ושהמצב (שחור, שני אדומים) שווה 4/3?

נוסחה כללית "מפורשת" למשחק עם N קלפים אין, לדעתי. נוסחה רקורסיבית יש ויש, והיא לא מאוד קשה לחישוב.
תיקון 161223
טוב, על זה כבר אמר מיודענו ירדן ניר תגובה 83059. אתה צודק, מה שאומר שגם החישוב שלי עבור שישה קלפים שגוי.
חידה 161219
טוב, אז הנה המצב לאשורו, אם אינני טועה. ובהחלט יכול להיות שאני טועה.

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

לבריאות!
חידה 161330
אלון,

יצאו לי אותם המספרים שיצאו לך, גם לגבי תוחלת הרווח וגם בכלל העצירה. את נוסחת הנסיגה של תוחלת הרווח לא קשה לכתוב, אבל פתרון סגור (נוסחה) לכל n ו- k לא מצאתי.
חידה 161345
תודה על האישור! נוסחה סגורה סביר שאין פה.
חידה 161408
כמה זמן לקחה לך הריצה במחשב? לפי החישוב שלי (לא בדקתי מעשית) זה אמור לצאת סדר גודל של מילישניות לכל היותר.
חידה 161416
אכן, איו פה שום בעיית מהירות - מילישניות אם לא פחות. גם באופן תאורטי האלגוריתם הוא כמובן מאוד מהיר (פולינומיאלי, פרופורציוני ל-n*k עבור n קלפים אדומים ו-k שחורים). אני מימשתי את זה בכמה שורות Mathematica.
חידה 161561
הרצתי את זה על 200 קלפים מכל סוג (וכמובן כתוצר לוואי קיבלתי את כל התוצאות הנמוכות יותר), נראה שהתוצאה כפונקציה של מספר הקלפים מאוד מאוד קרובה (לפחות עבור התחום הזה) לפונקצית שורש ריבועי. ריצה על מספר קלפים גדול יותר גירדה את תחתית מחסנית הרקורסיה שלי (אני צריך לשכתב את העסק לעומק סופי) אבל זה מעניין כי שום דבר (בערך) לא מתנהג כמו שורש ריבועי חוץ, אולי, מהילוך שיכור.
חידה 161633
בוא נשאל שאלה אחרת: נגיד שתרוץ כל פעם עד הסוף ותשמור את הערך הכי גבוה שאי פעם התקבל במשחק ( מין ניחוש בדיעבד כזה). באופן טיפוסי הערך הכי גדול יהיה בסביבות שורש מספר הקלפים ( מהלך שיכור וכולי)‏1. מה שגילית הוא שהאיסטרטגיה האופטימלית ללא ידיעת העתיד מתנהגת באופן דומה.

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

1 הערכים הם למעשה מהלך אקראי תחת האילוץ שהערך הראשון והאחרון הוא אפס.
חידה 161811
למעשה "גיליתי" זאת רק עבור מספר ערכים קטנים. במשך היום חשבתי שיהיה נחמד גם לחסום את העסק מלמעלה ומלמטה ולהראות שההתנהגות היא תמיד שורש. אתה תיארת חסם מלעיל (צריך רק לראות בדיוק כמה הוא יוצא מספרית), עכשיו רק צריך חסם מלרע וסיימנו לתת second best לא רע בכלל לנוסחה סגורה.

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

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

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

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

האם מישהו יכול לבדוק על הפיתרון המדויק איך נראה קו ה<רווח,מספר קלפים> של האסטרטגיה המדויקת למשחק עם הרבה ( נגיד כמה מאות) קלפים?
חידה 161552
(צר לי על העיכוב, בעיות גישה וזמינות)

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

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

עכשיו הרצתי את זה 10000 פעם, וחישבתי ממוצע - יוצא משהו קרוב מאד ל4 (מלמעלה). כ55% מהמשחקים מסתיימים ב4 ומעלה, כך שתוחלת הרווח שלי היא בערך 2.2 - פחות מ 2.6.

אגב, גם לעצור ב3 זה לא רע - כ70% מהמשחקים מסתיימים ב3 ומעלה - תוחלת של בערך 2.1.

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

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

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

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

הוא אכן עוסק בבעייה הנ"ל (שבמקור נחקרה ע"י Shepp ב-‏1969). במהלך המאמר מוצגת המשוואה הרקורסיבית שהוזכרה, ומוכחים אי-שיוויונים שונים לגביה.

למשל:

V(m, p+1) <= V(m,p)+1/(n+1)
V(m, p) <= V(m+1,p)+1/(n+1)
V(m+1, p+1) > V(m,p)

כאשר 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 קבוע.

תבדקו לראות אם זה יוצא...
תוספת קטנה 162162
המאמר מציין שעבור ערכים של p (מס' הקלפים ה"טובים") בין 0 ל-‏100, שווה לקחת עוד קלף אמ"ם מספר הקלפים ה"רעים" קטן מ-
p+0.83992sqrt(2p)-0.1427

הם מסבירים שהחישובים שלהם הם עד p=100 מטעמי נוחות בלבד, ולא בגלל קשיים חישוביים ושזמן הריצה של המחשב עלה להם רק 10 דולר.
טוב, אז הנה עוד קצת פרטים... 162286
קודם כל - תודה!

אני לא בטוח שאני מבין את הנוסחה האחרונה שציטטת. עבור m=p זה יוצא בערך 1, בעוד שערך המשחק בוודאי שואף לאינסוף (כמו שורש n חלקי שתיים, לפי הניחוש שלי). חסר גורם? זה מנורמל אחרת?

בכל אופן, תודה שוב על המאמץ.
חידה 162120
והנה וריאציה על החידה של גלעד, שלה דווקא יש פתרון אנליטי קצר ונקי.

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

מהי האסטרטגיה שממקסמת את הסתברות הזכייה במשחק?

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

לחילופין, אפשר לתת נימוק מילולי פשוט למה האסטרטגיה האופטימלית היא מה שהיא. רעיון, מישהו?
סתם אינטואיציה 162132
אולי להפסיק כשיש רק עוד קלף אדום אחד בערימה?
חידה 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- בינתיים די משעמם
חידה 162242
טוב, זה אגוז קטן ונחמד אבל די מוכר - לא אקלקל לכולם.
אם אנחנו כבר בשוונג, וממילא עיצבנו את האייל ההומניסט מתגובה 161524, אז למה לא עוד אחת, קלה, מסוג אחר? מי שמכיר, נא להיות מנומס...

*** תחרות לקוראי האייל ***
*** התחרות פתוחה ומתאימה לכל ***
*** לא רק לכמה סטודנטים לפיסיקה מהטכניון ***

מנצח מי ששולח את המספר הגדול ביותר שהוא מכפלה של מספרים טבעיים שסכומם 100. שימו לב: לאו דווקא _שני_ מספרים טבעיים.

הפרס: יופי של קארמה, שזה בדיוק ההיפך מעונשו של מי שמכיר את החידה ושולח כדי לצאת כאילו גדול.
תשובת תם 162248
2 בחזקת 50?
1125899906842624
תשובת תם 162255
עוד לא הספקתי להרהר מספיק בענין (תרוצים, תרוצים...), אבל ארבע כפול שלש בחזקת שלשים ושנים נראה לי חביב.
תשובת תם 162281
בהחלט! יפה מאוד. ממש ממש לא צריך מטלב בשביל לראות שזה (הרבה) יותר משתיים בחזקת חמישים - אבל האינטואיציה של הרבה אנשים מוליכה אותם להרבה פעמים שתיים.

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

נניח שנתונה לנו סדרת טבעיים שסכומם מאה, ונתבונן באבר 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).
תשובת תם 162285
נכון מאוד, אבל אפשר טיפה לקצר - כדאי להחליף כל m>3 ב-‏2 ו-(m-2), אין צורך להפריד לזוגיים ואי-זוגיים.
תשובת תם 162258
מטלב אומר:
4*(3^32)-2^50 = +6.29e015
תשובת תם 162263
אני חושב שדי קל להוכיח שהפתרון הזה אופטימלי.
חידה 163699
אתמול גיליתי שניתן לפתור את החידה גם בדרך נוספת לאלו שהועלו עד כה - על ידי משפט העצירה האופציונלית עבור מרטינגיילים. זה אמנם קצת overkill מתמטי, אבל עדיין נחמד (פירוט יינתן על פי דרישה).
חידה 163702
דרישה. אפשר גם בדואל, אם כמות המתעניינים הצפויה לדעתך קרובה להערכה שלי. אבל Overkill מזכיר לי רב-שיח חמוד שראיתי לאחרונה (אני מקווה שזה יעבוד בתרגום הצולע שלי):

א': (פותר בעייה פשוטה בתותחים כבדים)

ב' (משועשע): נו מה, א'? שוב מחסלים זבובים עם קורנסים?

א' (נעלב): כאילו שלחסל זבוב עם קורנס זה כל כך קל. תנסה פעם.

ג': היי, אם פעם אראה זבוב עם קורנס אני לא מתכוון להישאר בסביבה ולנסות להרוג אותו.
חידה 163704
הנה.

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

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

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