חידה מתמטית

[גיל14]

חידה מתמטית

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

 

[Renatius Cartesius]

רעיון לא מפותח וכנראה גם שגוי.

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

 

[Renatius Cartesius]

שטויות, מה שרשמתי...

ואני מתנצל על כך.

 

[Alkhimey]

האם

הפתרון צריך להיות מטמתי או שאפשר להסתמך על זה שהדילר "אנושי".

 

[ייץ]

נסיון לאסטרטגיה לא בטוח שהיא אופטימלית

אם אין כלל הגבלה על המספרים וגם הם מסודרים רנדומלית מבחינת המיקום (כלומר הדילר לא מתכנן מראש את סדר הופעתם) אז: אם המספר הראשון גדול מ 10 בחזקת 16 נבחר אותו. אחרת נדלג עליו. אם המספר השני קטן מהראשון או קטן מ 10 בחזקת 14 נדלג גם עליו. אם המספר השלישי קטן מ 10 מאחד משני המספרים הקודמים וגם קטן מ 10 בחזקת 12 נדלג גם עליו. נמשיך כך עד המספר התשיעי. אם המספר התשיעי קטן משמונת קודמיו וגם קטן מ 0 נדלג עליו אחרת נבחר אותו. כעת נשארנו עם המספר האחרון. הבחירה של קפיצות של 100 היא החלטה שרירותית שלי (אפשר לחלק את הקפיצות למרווחים אחרים). יתכן ואפילו כנראה שהאסטרטגיה אינה אופטימלית אך היא טובה מאשר לבצע בחירה רנדומלית.

 

[עריסטו]

חידת המשך

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

 

[גיל14]

כמובן ../images/Emo127.gif

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

 

[עריסטו]

נסו לפתור עבור החידה שלי, ../images/Emo26.gif

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

 

[גיל14]

../images/Emo58.gif פתרון

זוהי בעיית המזכירה. האסטרטגיה (אסימפטוטית) היא לוותר על n/e הראשונים ולקחת את הכי גדול משם. הסיכוי לזכות אסימפטוטית באסטרטגיה הזו שואף ל-e^-1, באשר n שואף לאינסוף, או בערך 36.79%. לגבי הדרך ליצור n כרטיסים - לוקחים את הקבוצה {1,2,3,...,n} ומגרילים עליה יחס סדר מלא - בהתפלגות אחידה; יש n! אפשרויות כאלה ולכן ההתפלגות האחידה הדיסקרטית תעבוד (יחס הסדר הרגיל - 1≤2≤3≤4... הוא אפשרות אחת מה-n!). הדילר יכתוב את המספרים על הכרטיסיות, ואת יחס הסדר ישמור לעצמו. ונגדיר את המספר הגדול ביותר להיות המספר הגדול ביותר לפי יחס הסדר החדש.

 

[עריסטו]

../images/Emo127.gif../images/Emo128.gif הפתרון לאסטרטגיה לא טוב

הרי הדילר חייב לגלות לשחקן מראש מהו יחס הסדר... אחרת איך השחקן יישם את האסטרטגיה?

 

[עריסטו]

התכוונתי שהפתרון לדרך יצירת הכרטיסים לא טוב

הפתרון לאסטרטגיה דווקא נכון.

 

[גיל14]

הוא ישאל את הדילר.

 

[עריסטו]

התכוונתי לפתרון

בלי לשאול את הדילר: להגדיר מראש יחס סדר ולגלות אותו לשחקן.

 

[גיל14]

זה בכלל יתכן?

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

 

[עריסטו]

זה יתכן.

 

[עריסטו]

רק שיהיה ברור - אני מגדיר את הבעיה

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

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

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

 

[eug]

../images/Emo62.gif

האסטרטגיה צריכה להראות ככה: "מדלגים על n מספרים ראשונים, ואז בוחרים במספר הראשון שיהיה הגדול ביותר עד עכשיו. ההסתברות לזכות, אם כך, היא סכום מ- i=n+1 עד 10 של ההסתברות שהמספר הגדול ביותר נמצא במקום ה-ו כפול ההסתברות שהשחקן יבחר במספר הזה. בהנחה שהמספרים נחברים ראנדומלית, הסיכוי של כל מספר להיות הגדול ביותר הוא 1/10. ההסתברות שהשחקן יבחר במספר הגדול ביותר אם הוא נמצא במקום i שווה להסתברות שהמספר הגדול ביותר בין i-1 מספרים שקודמים ל-i שייך לקבוצה של n מספרים הראשונים. אחרת השחקן היה בוחר במספר המקסימלי בין 1 ל-i-1 והיה מפסיד. ההסתבברות הזאת שווה ל - n/i-1. כלומר עם n=5 והמספר המקסימלי נמצא במקום 7, הסיכוי בהשחקן יבחר בו הוא 5/6. עכשיו הנוסחה השלמה לזכות במשחק:

(n/n + n/(n+1) + n/(n+2) + ... + n/9) /10​

בדקתי בעזרת מחשב את התוצאה עבור n-ים שונים: 1 0.2828968 2 0.3657936 3 0.3986905 4 0.398254 5 0.3728175 6 0.327381 7 0.2652778 8 0.1888889 9 0.1 ניתן לראות מכאן שהדרך האופטימלית היא לדלג על 3 מספרים ראשונים, ואז לבחור במספר הראשון שיהיה גדול מהמקסימום של שלושת הראשונים. ההסתברות לזכות במקרה זה היא 39.87%.

 

[עריסטו]

יפה, זהו הפתרון הנכון עבור ../images/Emo26.gif

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

 

[eug]

../images/Emo62.gif

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

 

[עריסטו]

../images/Emo127.gif