שירשור החידות הגדול

AviBiton · שליחה 13/04/2008 8:29

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

).

moco · שליחה 13/04/2008 9:17

אני גם ביום ד', בערב

amirbd · שליחה 13/04/2008 10:35

למה רביעי ולא חמישי ?

היה פה שרשור איפשהוא שהסביר כי עדיף (מבחינת תנועה וחנייה) להגיע ביום חמישי ולא רביעי.

AviBiton · שליחה 13/04/2008 10:45

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

.
אבל זה מסתדר לי הכי טוב עם העבודה ועם ההנהלה שבבית

.

moco · שליחה 13/04/2008 11:14

אני פשוט לא יכול ביום חמישי.

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

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

osherov · שליחה 13/04/2008 12:25

אני יגיע ברביעי בערב או בחמישי בצהריים, דווקא

אמיר, מה עם החידה ? איך ממשיכים לקדם אותה לקראת פתרונה ?

amirbd · שליחה 13/04/2008 12:26

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

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

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

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

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

לטענתי קיימת אסטרטגיה לאריה שתצליח בהסתברות מעל 1/2 גם אם הוא יספר לי אותה לפני שבחרתי את המספרים, ובפרט המספרים שאני אבחר לא צריכים להבחר באקראי, היא יכולים להיות תלויים באסטרטגיה שלך.

תראה לי איך אתה מצליח בתנאים האילו להגיע להסתברות הצלחה 3/4 עבור {1,2,3} בלי להניח שאני בוחר את המספרים שלי באקראי

osherov · שליחה 13/04/2008 12:34

אסטרטגייה:
אם יוצא 3 אז המספר ביד השנייה קטן יותר
אם יוצא 1 אז המספר ביד השנייה גדול יותר
אם יוצא 2 אז אני מגריל את התשובה (50%)

הסיכוי שיצא 3 או 1 הוא 1/2 ובמידה ואחד מהם יוצא אז 100% אני פותר נכון
הסיכוי שיצא 2 גם הוא 1/2 (אני מניח לא משתמשים בספרות 1 ו 3) ואז יש 50% למציאת פתרון נכון

סה"כ הסתברות להצלחה 3/4

אבל, לדעתי, זאת בדיוק הדרך שמשה רשם

moco · שליחה 13/04/2008 12:44

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

המקרה הפרטי של 1,2,3 הוא פשוט:
אם 3 אז "גדול", אם 1 אז "קטן", אם 2 אז "כאילו" שאתה בחרת בארקאי - כלומר 50-50 .
אתה תצמצם את סיכויי אריה על ידי בחירה 2 באמצע, שבמקרה זה , זה (1,2) (או 2,3) . וההסברות של אריה יוצאת 3/4 לפי הנוסחא הנ"ל.
במקרה הפשוט הזה : אם אריה בחר 2 הוא יצדק ב50%, אם הוא בחר 1 ( או 3) הוא יצדק ב100%. יש 50-50 על איזה יד הוא יבחר ראשונה.
מה שעשיתי למעלה זה הכללה של זה לכל קבוצה סופית.

לא יודע להכליל לאינסוף.

amirbd · שליחה 13/04/2008 12:55

osherov כתב:אסטרטגייה:
אם יוצא 3 אז המספר ביד השנייה קטן יותר
אם יוצא 1 אז המספר ביד השנייה גדול יותר
אם יוצא 2 אז אני מגריל את התשובה (50%)

הסיכוי שיצא 3 או 1 הוא 1/2 ובמידה ואחד מהם יוצא אז 100% אני פותר נכון
הסיכוי שיצא 2 גם הוא 1/2 (אני מניח לא משתמשים בספרות 1 ו 3) ואז יש 50% למציאת פתרון נכון

סה"כ הסתברות להצלחה 3/4

אבל, לדעתי, זאת בדיוק הדרך שמשה רשם
...

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

מה האסטרטגיה שלך עבור הסט {99,100,...1,2} ? שוב תניח שאני יודע את האסטרטגיה לפני שאני בוחר את זוג המספרים.

moco · שליחה 13/04/2008 12:55

בקריאה של מה שכתבתי אני רואה שצריך להבהיר מה הכוונה באסטרטגיה של אריה שהיא להתנהג כאילו אמיר בחר אותם באקראי.
הכוונה היא שאם מדובר בקבוצת המספרים מ1 עד 10, אז אם אריה רואה 6 , אז הוא יבחר להגיד "גדול" בהסתברות של 5/9 , ולהגיד "קטן" בהסתברות של 4/9 - כאילו שהוא מניח שהמספר השני נבחר באקראי (בהסתברות שווה) משאר 9 המספרים האפשריים.

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

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

moco · שליחה 13/04/2008 12:58

אני מקווה שההבהרה הנ"ל עזרה, אך בכל מקרה ל 1-100:

אם הוא רואה 78, אז הוא אומר "גדול" בהסתברות 77/99, אחרת (22/99) הוא אומר "קטן".
(הוא עושה הגרלה כזו עם random number generator) או "קוביה" עם 99 פאות.

amirbd · שליחה 13/04/2008 13:03

moco כתב:בקריאה של מה שכתבתי אני רואה שצריך להבהיר מה הכוונה באסטרטגיה של אריה שהיא להתנהג כאילו אמיר בחר אותם באקראי.
הכוונה היא שאם מדובר בקבוצת המספרים מ1 עד 10, אז אם אריה רואה 6 , אז הוא יבחר להגיד "גדול" בהסתברות של 5/9 , ולהגיד "קטן" בהסתברות של 4/9 - כאילו שהוא מניח שהמספר השני נבחר באקראי (בהסתברות שווה) משאר 9 המספרים האפשריים.

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

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

כמו שסבתא שלי היתה אומרת "או טו זוי" (או משהו כזה) - בתרגום חופשי - "סוף סוף".

בוא תסביר עכשיו, למה אני לא יכול ל"דפוק" את אריה ע"י זה שאני אבחר את 99 ו-100 ?

moco · שליחה 13/04/2008 13:09

אתה הולך פה על שיטה פדגוגית של הולכה ביד ?

אם תבחר את 99 ו100 הוא יצא צודק ב 0.5 + 0.5 * 1/99, שזה יותר מחצי .

הפואנטה החסרה שאני מחכה לה כל כך, זה איך אתה קופץ לאינסוף.

amirbd · שליחה 13/04/2008 13:35

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

מכיוון שאני מרגיש שנמאס לך מהחידה, ואתה לא מרוצה מהדרך הפדגוגית שלי לנסות לא לחשוף את הפתרון, הנה הפתרון המלא -

ראשית - פתרון לקבוצה סופית (נגיד 1 עד 100)

אריה יבחר יד באקראי (זה חשוב, למרות שלא ציינת את זה), ובנוסף יבחר באקראי מספר "ביניים" מהקבוצה {1.5, 2.5, ..., 99.5} - כלומר מספר בין שני מספרים שלמים סמוכים.

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

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

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

למשל - אריה יחליט לעשות את הניסוי המחשבתי הבא - הוא יטיל מטבע (הוגן) עד הפעם הראשונה שיצא "עץ" - ויספור כמה פעמים יצא "פלי" לפני ה"עץ" הראשון (נסמן את זה ב-k).
אם k זוגי אז אריה ישתמש ב-[left](k/2)+0.5[/left] בתור מספר הביניים, ואם K אי זוגי, אריה ישתמש ב-[left]((k+1)/2)+0.5[/left] בתור מספר הביניים.

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

amirbd · שליחה 13/04/2008 13:55

נו - יש respect לחידה ?

osherov · שליחה 13/04/2008 13:59

יפה,
respect

אגב, אני חושב שיש מרחק בין הרמז שלך למצוא אלגוריתם לקבוצה סופית ובין אלגוריתם לקבוצה אין סופית

שוב קבל

moco · שליחה 13/04/2008 14:25

וואו, לקח קצת זמן לעכל את זה.
באמת בעיה יפה מאוד.

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

תגיד, האם פתרת ובכמה זמן?

אגב יש לך באג קטן וקל לתיקון בדוגמא, זה עובד רק על חיוביים. צריך להוסיף עוד מטבע בשביל סימן ועוד משהו בשביל ה0.

moco · שליחה 13/04/2008 14:37

חידה חדשה (לשרשור):
לפני שני עמודים נתתי הוכחה למה זה לא יכול להיות.
מה הבאג המהותי ב"הוכחה" ?

amirbd · שליחה 13/04/2008 15:22

moco כתב:וואו, לקח קצת זמן לעכל את זה.
באמת בעיה יפה מאוד.

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

תגיד, האם פתרת ובכמה זמן?

אגב יש לך באג קטן וקל לתיקון בדוגמא, זה עובד רק על חיוביים. צריך להוסיף עוד מטבע בשביל סימן ועוד משהו בשביל ה0.
...

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

אני לא פתרתי את החידה הזאת - ראיתי אותה עם הפתרון