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

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

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

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

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

AviBiton · שליחה 07/04/2008 12:41

אני גם בעד רמז.

moco · שליחה 07/04/2008 12:46

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

AviBiton · שליחה 07/04/2008 13:12

moco כתב:אני מציע שאני אכתוב פה "הוכחה" למה זה לא יכול להיות ואמיר יגיד רק מה הבאג בהוכחה.
...

לך על זה.

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

נחכה לאישור של אריה, הרי הוא זה שמשחק מול אמיר.

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

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

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

משה, לך על זה,
אמיר, מה עם הפתרון שלי ?

moco · שליחה 07/04/2008 14:30

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

amirbd · שליחה 07/04/2008 14:34

osherov כתב:משה, לך על זה,
אמיר, מה עם הפתרון שלי ?
...

כרגע עניתי לך בפרטי...

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

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

עד פה נכון.

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

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

האם לשחרר רמז?

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

כן, שחרר, למשל תסביר מה ההבדל בין לראות 100 לבין לראות 100- .

amirbd · שליחה 07/04/2008 15:39

moco כתב:כן, שחרר, למשל תסביר מה ההבדל בין לראות 100 לבין לראות 100- .
...

תראה - האסטרטגיה של אריה יכולה להיות תלויה באופן שרירותי כלשהו במספר שהוא רואה (לכל מספר אסטרטגיה אחרת לצורך הדיון) - בפרט אין לך כל יכולת להניח שאריה מתנהג באותה צורה כשהוא רואה את X ואת X-

וכעת רמז -

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

שימו לב שיש שתי דרכים ל"הקל" על אריה במשימה (שהיא להגיע להסתברות גדולה מ-1/2)

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

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

אני מוכן לעוד רמז

amirbd · שליחה 12/04/2008 15:11

moco כתב:אני מוכן לעוד רמז
...

בוא נסכים שאם אני יכול לבחור שני מספרים שונים מתוך הקבוצה {1,2}, אז אריה יכול להצליח בהסתברות 1

- לכן המקרה הראשון שזה לא טריוויאלי, הוא שהקבוצה היא בגודל 3.

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

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

moco · שליחה 12/04/2008 15:23

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

תוך כתיבת שורות אלה עולה לי איזה רעיון מטורף. נראה מה יצא ממנו.

moco · שליחה 12/04/2008 15:52

לא יצא ממנו כלום.

תראה, הגעתי שלכל בחירה מתוך N מספרים, אריה יכול להגיע ל
[left]
N/(N-1) /2
[/left]

שזה גדול מ0.5 לכל N .
במילים אחרות , כלל שהקבוצה N תגדל, כך אריה יתקרב לחצי.

עדיין, לא מבין איך להכליל לכל אינסוף המספרים, הרי זה שואף ל0.5 .

moco · שליחה 12/04/2008 17:37

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

אם האחרים לא מתנגדים, אני נכנע. אני מקווה לעמוד נדהם

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

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

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

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

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

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

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

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