בתשובה לבועז, 15/03/03 12:59
 |
|
 |
||
|
||||
 |
ההכללה של הפרדוקס הוא ההסתברות המותנה. הסיכוי שמטבע שנזרק 10 פעמים יפול בכולן על "עץ" הוא אפסי. אבל אם הוא כבר נפל 9 פעמים על "עץ" הסיכוי לסדרה באורך 10 הוא חצי. והגרסא האהובה עלי לפרדוקס: יש משחק טלויזיה בו אתה מתבקש לפתוח דלת, ומבטיחים לך לקבל את מה שנמצא מאחוריה. ישנן שלוש דלתות, מאחורי אחת יש מכונית ומאחורי האחרות יש ערימת קש. אתה בוחר דלת (נניח מס' 2), והמנחה פותח את אחת הדלתות הנותרות (נניח מס' 1) ומראה את הקש הטרי שמאחוריה. ואז הוא שואל "האם אתה עדיין מעוניין בדלת 2 או שאולי אתה מעדיף להחליף לדלת 3?" מה האפשרות העדיפה? |
 |
 |
 |
|
|
|
||
|
||||
|
כדי לחסוך קצת הודעות, אפשר להציץ ב תגובה 59524 ואילך. | |
|
|
|
|
|
||
|
||||
|
אני מעדיף להסתכל על הפרדוקס הזה כך: לכל סדרה מסוימת של תוצאות ולאו דווקא לסדרה שהיא כולה "עץ" יש סיכוי אפסי שאם נטיל 10 פעמים מטבע, נקבל בדיוק את הסדרה הזו. למרות זאת, ברור לכולנו שאחרי שנטיל את המטבע 10 פעמים, התוצאה תהיה איזושהי סדרה מסויימת. |
|
|
|
|
|
|
||
|
||||
|
נסמן את הדלתות ב X, Y ו Z ונסמן ב P(x) את ההסתברות שהמכונית נמצאת מאחורי דלת X נניח הדלת שאני בחרתי היא X והדלת שהמנחה פתח היא Y נסמן שלילה ע"י הסימן ~ על פי משפט בייז: P(X|~Y)=P(X)P(~Y|X)/P(~Y) ההסתברות האפריורית של ~Y היא 1 במקרה שהמנחה יודע איפה נמצאת המכונית ו 2/3 אם הוא לא יודע מראש.P(X)=1/3 P(~Y|X)=1 P(~Y)=? יוצא שאם המנחה יודע מראש את מיקום המכונית ופותח בכוונה את דלת שמאחוריה אין מכונית, משתלם לעבור לדלת שנשארה אבל אם מי שפתח את דלת Y הוא מתחרה כמוך שניחש בלי לדעת מראש, אין משמעות למעבר. |
|
|
|
|
|
|
||
|
||||
|
לכאורה משתלם להחליף את הבחירה, אבל אני סבור שאוכל להוכיח שזה לא נכון. הטיעון שראיתי לטובת החלפת הבחירה, כפי שהוא מופיע בספר „המקרה המוזר של הכלב בשעת לילה” מאת מארק האדון (הניסוח אינו זה שהוא משתמש בו, אבל החישוב זהה): נניח שהמכונית נמצאת מאחורי דלת X. אתה בוחר אחת מהדלתות X,Y,Z. אם אתה מחליט להתעקש גם בשלב השני על בחירתך: בחרת דלת קש (Y) -> רואה קש בדלת אחרת -> משאיר -> מקבל קש. בחרת דלת קש (Z) -> רואה קש בדלת אחרת -> משאיר -> מקבל קש. בחרת דלת מכונית (X) -> רואה קש בדלת אחרת -> משאיר -> מקבל מכונית. אם אתה מחליט להחליף בשלב השני את בחירתך: בחרת דלת קש (Y) -> רואה קש בדלת אחרת -> מחליף -> מקבל מכונית. בחרת דלת קש (Z) -> רואה קש בדלת אחרת -> מחליף -> מקבל מכונית. בחרת דלת מכונית (X) -> רואה קש בדלת אחרת -> מחליף -> מקבל קש. כלומר: אם אתה מתעקש על בחירתך, הסיכוי שלך לקבל מכונית הוא 1/3. אם אתה מחליף את בחירתך, הסיכוי שלך לקבל מכונית הוא 2/3. זה נראה מוזר, ואכן לדעתי לא מכוסות כל האפשרויות. הנה התיאור הנכון, לדעתי: אם אתה מחליט להתעקש גם בשלב השני על בחירתך: בחרת דלת קש (Y) -> רואה קש בדלת אחרת (Z) -> משאיר -> מקבל קש (Y). בחרת דלת קש (Z) -> רואה קש בדלת אחרת (Y) -> משאיר -> מקבל קש (Z). בחרת דלת מכונית (X) -> רואה קש בדלת אחרת (Y) -> משאיר -> מקבל מכונית (X). בחרת דלת מכונית (X) -> רואה קש בדלת אחרת (Z) -> משאיר -> מקבל מכונית (X). אם אתה מחליט להחליף בשלב השני את בחירתך: בחרת דלת קש (Y) -> רואה קש בדלת אחרת (Z) -> מחליף -> מקבל מכונית (X). בחרת דלת קש (Z) -> רואה קש בדלת אחרת (Y) -> מחליף -> מקבל מכונית (X). בחרת דלת מכונית (X) -> רואה קש בדלת אחרת (Y) -> מחליף -> מקבל קש (Z). בחרת דלת מכונית (X) -> רואה קש בדלת אחרת (Z) -> מחליף -> מקבל קש (Y). כלומר – בשלב השני הסיכוי שלך עומד על 50%, בין אם תחליף את בחירתך או תשאיר אותה. זה נראה הרבה יותר תואם לאינטואיציה. המכשלה בצורת התיאור הראשונה היא ההנחה שיש רק דרך אחת לתיאור מכונית -> קש. היות שיש שתי חבילות קש, תיתכנה שתי אפשרויות. |
|
|
|
|
|
|
||
|
||||
|
החישוב המתוקן שלך שגוי, אני חושש. איני מבין מדוע אתה סבור שיש לספור פעמיים את המקרים בהם במקרה בחרת דלת נכונה מראש, רק מפני שלמנחה יש במקרים אלו חופש בחירה, איזו דלת ברצונו לפתוח. חשוב על זה כך: נניח שמשחקים את המשחק 90 פעמים. ב-30 מתוכן בחרת את דלת Y (ואז ההחלפה היתה לטובתך), בשלושים אחרות בחרת Z (וגם אז ההחלפה היתה לטובתך), ורק בשלושים בחרת נכון את דלת X (ב-15 מאלה, המנחה פתח את Y, וב-15 האחרות, את Z - אז מה?) גם לאינטואיציה שלך אפשר לעזור, אני מקווה. הנקודה היא שהמנחה מוגבל בבחירתו לפתוח דלת שאיננה זו שבחרת ואיננה זו הנכונה. בכך הוא מעביר לך, ב-2/3 מהמקרים, מידע רב ערך: הוא מצביע, בעקיפין, על הדלת הנכונה. דרך נוספת לחשוב על כך: נניח שיש 1000 דלתות, ורק מאחורי אחת מהן יש פרס. אתה מצביע על אחת מהן (ביודעך היטב שסיכוייך קלושים), והמנחה עושה לך טובה עצומה: הוא פותח 998 דלתות ללא פרס. בכך הוא רומז לך רמז עצום - רואה את הדלת שלא פתחתי? זה שם! - פרט למקרה הנדיר בו *במקרה* צדקת בבחירתך המקורית. במקרה זה יש למנחה שלל אפשרויות, איזו דלת להשאיר סגורה, אבל אז מה בכך? זה לא משנה את העובדה שכל זה קורה רק בסיכוי 1/1000. בחישוב שלך, היית סופר את המקרה הזה 999 פעמים (אחת עבור כל דלת שהמנחה משאיר סגורה), ולא בצדק. |
|
|
|
|
|
|
||
|
||||
|
הנקודה העדינה בסיטואציה המדוברת היא שהמכונית והקש נמצאות מאחורי הדלתות לפני הבחירות שאתה עושה, כלומר הסיכוי שתבחר מלכתחילה בדלת עם המכונית הוא בדיוק שליש. כשהמנחה בוחר את הדלת לפתוח, אם בחרת ב Y או ב Z יש לו בדיוק אופציה אחת, ואילו אם בחרת X יש לו שתיים, והוא יבחר בין שתיהן בסיכוי של חצי חצי. כלומר: אם נכתוב את את ההסתברות שכל אירוע יקרה בכל התפצלות, התיאור המלא של מה שכתבת צריך להיות כזה: אם אתה מחליט להתעקש גם בשלב השני על בחירתך: בחרת דלת קש (Y) (הסתברות 1/3) -> רואה קש בדלת אחרת (Z) (הסתברות 1) -> משאיר -> מקבל קש (Y) בחרת דלת קש (Z) (הסתברות 1/3) -> רואה קש בדלת אחרת (Y) (הסתברות 1) -> משאיר -> מקבל קש (Z). בחרת דלת מכונית (X) (הסתברות 1/3) -> רואה קש בדלת אחרת (Y) (הסתברות 1/2) -> משאיר -> מקבל מכונית (X). בחרת דלת מכונית (X) (הסתברות 1/3) -> רואה קש בדלת אחרת (Z) (הסתברות 1/2) -> משאיר -> מקבל מכונית (X). נכפול את הסיכויים ונחבר, ונקבל "מקבל קש" בהסתברות 2/3 ו"מקבל מכונית" בהסתברות 1/3. אם אתה מחליט להחליף בשלב השני את בחירתך: בחרת דלת קש (Y) (הסתברות 1/3) -> רואה קש בדלת אחרת (Z) (הסתברות 1) -> מחליף -> מקבל מכונית (X). בחרת דלת קש (Z) (הסתברות 1/3) -> רואה קש בדלת אחרת (Y) (הסתברות 1) -> מחליף -> מקבל מכונית (X). בחרת דלת מכונית (X) (הסתברות 1/3) -> רואה קש בדלת אחרת (Y) (הסתברות 1/2) -> מחליף -> מקבל קש (Z). בחרת דלת מכונית (X) (הסתברות 1/3) -> רואה קש בדלת אחרת (Z) -> מחליף (הסתברות 1/2) -> מקבל קש (Y). נכפול את הסיכויים ונחבר, ונקבל "מקבל קש" בהסתברות 1/3 ו"מקבל מכונית" בהסתברות 2/3. לפעמים, לשם המחשה, יש מי שמנסה להסביר את אותו הסיפור עם 100 דלתות, כשהמנחה פותח 98 ומשאיר אותך מול שתיים. בדרך כלל זה רק מבלבל, אבל בהנתן התיאור הריגורוזי למעלה הנקודה מתבהרת: היינו צריכים לכתוב 99 שורות של "בחרת דלת מכונית X" ו 99 שורות של "בחרת דלת קש A1/A2/...A99", כאשר עבור השורות מהסוג הראשון יש למנחה חופש בחירה בדלת להשאיר פתוחה של 99 (וההסתברות לבחור בדלת מסויימת היא 1/99), ואילו במקרה השני למנחה אין חופש בחירה בכלל (הוא תמיד ישאיר את X, בהסתברות 1). |
|
|
|
|
|
|
||
|
||||
|
"והוא (המנחה) יבחר בין שתיהן בסיכוי של חצי חצי" - מנין לך? אולי הוא בוחר תמיד לפתוח את הדלת השמאלית ביותר שיש בה קש? | |
|
|
|
|
|
||
|
||||
|
ברור, זה היה להמחשה בלבד. | |
|
|
|
|
|
||
|
||||
|
לך זה ברור; ברוב ההסברים הפופולריים של הבעיה הזו, מניחים כמובן מאליו שהמנחה מגריל את התגובות שלו באקראי, ובהסתברויות שוות לכל האפשרויות. אבל שעשועוני טלוויזיה אינם מבוססים על מכונות-טיורינג-לא-דטרמיניסטיות, אלא על משחק והפתעה. לפי כמעט כל ניסוח שנתקלתי בו לבעיית הדלתות, התשובה לשאלה "האם כדאי להחליף" היא "אין לדעת; תלוי אם המנחה אקראי (שאז כדאי), או דטרמיניסטי". | |
|
|
|
|
|
||
|
||||
|
רק כדי שאני אהיה בטוח שהבנתי את מה שאתה מנסה להסביר לי: אתה טוען שהכנסת האקראיות לסיפור מבלבלת? כי בדיוק את ההתבלבלות הזו ניסיתי להקדים ולהכות... כל הפואנטה בהסבר הייתה שהבחירה האקראית (או שרירותית) של המנחה מוגבלת רק למקרה שבו השחקן בחר את הדלת הנכונה, ושבשאר המקרים אין לו שום בחירה. |
|
|
|
|
|
|
||
|
||||
|
אני חושש שקצת סיבכתי את ההסבר. אפשר כמובן להעזר במידע על האופן שבו המנחה בוחר את הדלת שהוא פותח (במקרים שבהם יש לו חופש בחירה), אבל ההנחה הבעייתית אינה שם, אלא בכך שמניחים שהוא *חייב* לפתוח דלת כזו. אם הבעיה היא "בחרת דלת, המנחה פותח דלת אחרת, מה אתה עושה עכשיו" (כפי שהיא מופיעה כמעט בכל מקום, לרבות, במשתמע, הדיון הזה), אז אי אפשר לדעת מה היה המנחה עושה אילו בחרתי דלת אחרת (אולי הוא היה פותח את הדלת ההיא בצהלת נצחון?); וכל חישובי התועלת משתבשים. | |
|
|
|
|
|
||
|
||||
|
נראה לי שהזמן בשל לכך שתביא דוגמה להסבר פופולרי אחד או שניים שכאלו (כלומר, איפה אפשר למצוא אותם). | |
|
|
|
|
|
||
|
||||
|
למשל בתגובה 431389. לא שמרתי מקורות אחרים. | |
|
|
|
|
|
||
|
||||
|
אני כנראה קשה תפיסה כי אני לא מבין על מה אתם מדברים. איזה ווריאציות יכולות להיות על הבעיה? האם אתה מתכוון שהמנחה לא חייב להגיב ע"י פתיחת דלת? כי אם הוא כן חייב להגיב אז זה לא משנה אם אחרי שבוחרים במקרה את הדלת הנכונה הוא בוחר את הדלת הריקה באקראי או בכל שיטה אחרת. אם לא אז קשה לי להבין איך הבעיה יכולה להראות... |
|
|
|
|
|
|
||
|
||||
|
כמו במציאות (של שעשועוני טלוויזיה, כן?): בחרת דלת, המנחה מחייך, פותח דלת אחרת, ומציע לך לעבור. אין לך מושג האם הוא פתח את אותה דלת משום שהוא חייב לעשות כך, או כדי לבלבל ולחסוך את המכונית למתחרה הבא. | |
|
|
|
|
|
||
|
||||
|
ויש לסיטואציה החדשה איזשהו מימד מתמטי מעניין (חידתי או אחר)? ניסיתי לחשוב על למה זה מעניין, אם זה מעניין: ברור שאם המשתתף בחר במכונית משתלם למנחה להציע לו להחליף, וברור שאם הוא לא בחר לא משתלם להציע לו, וזה כל מה שאפשר להגיד פחות או יותר, חוץ מזה שאחרי פעמיים שלוש כאלה אף אחד לא יחליף אם בכלל יציעו לו. אפשר לנסח את האסטרטגיה האופטימלית למנחה שלא תקרוס למה שכתוב למעלה? היא מבטיחה סיכוי של שליש ומטה להעניק את המכונית. אם החידה מוצגת כך שהמנחה לא היה חייב לפתוח דלת זה אומר שהמכונית נמצאת בדלת שכבר בחרת בסיכוי של יותר משליש? אני מניח שצריך למצוא את האסטרטגיה האופטימלית למנחה לפני שאפשר לענות (זאת בהנחה שהאסטרטגיה האופטימלית של המנחה לא צריכה לקחת בחשון גם את האסטרטגיה האופטימלית של השחקן...) בשל האמור לעיל, לא נראה לי שהמקרה שבו המנחה לא היה חייב לפתוח את הדלת שייך בדיוק לחידות במתמטיקה... |
|
|
|
|
|
|
||
|
||||
|
בלי לקחת בחשבון את זה שיהיו כאן משחקים חוזרים, אין למנחה שום אינטרס להציע למישהו להחליף אם הוא בחר בדלת הלא נכונה. הסיבה היחידה שלו לעשות את זה היא כדי ליצור רושם של ''אמינות'' עבור המשתתפים הבאים שהוא כן יפיל בפח. | |
|
|
|
|
|
||
|
||||
|
כן, לזה התכוונתי בפסקה הראשונה. | |
|
|
|
|
|
||
|
||||
|
בהחלט. לפעמים, יש הבדל בין החידה "A", לבין "להלן חידה ניתנת לפתרון: A". אבל זה נכון שבמקרה הזה, (נדמה לי ש)המתחרה אף פעם אינו ניזוק מהחלפה (למרות שבמקרים מסויימים היא מיותרת). | |
|
|
|
|
|
||
|
||||
|
אני לא חושב שההנחה המקובלת היא שהמנחה הוא אקראי; נהפוך הוא, בהרבה מקרים מדגישים שהוא פותח דלת אחרת מזו שבחרת וכזו שאין בה פרס. מהמשפט האחרון שלך אפשר להבין שאצל מנחה כזה לא כדאי להחליף, ולא היא. הפרשנויות הסבירות היחידות שעולות בדעתי למצבים בהם *לא* כדאי להחליף הן אצל מנחים עויינים, שמציעים החלפה רק כאשר הם יודעים שבחירתך המקורית מוצדקת (ובמקרים האחרים כל סיפור פתיחת הדלת וההצעה כלל לא מתרחש), או פועלים כך בהסתברות גבוהה. לזה התכוונת? |
|
|
|
|
|
|
||
|
||||
|
לי אישית תמיד היה נראה שמובן מאליו שהשאלה *לא* נשאלת על מקרה שבו המנחה יכול לעשות מה שבראש שלו. הרי ברור שהמקרה הזה טריוויאלי לחלוטין (המנחה הוא לא חבר שלך; אם הוא מציע להחליף, כנראה שהוא עובד עלייך, כי אם היית בוחר דחליל הוא לא היה טורח להציע כלום). כבר ניהלנו את כל הדיון הזה לפני שנה-שנתיים (והתוצאות שלו אז היו מצערות למדי). | |
|
|
|
|
|
||
|
||||
|
אלון ענה טוב ממני, אבל הנה עשר האגורות שהן מה שגרמו לי להשתכנע בשעתו: נניח שהמנחה, במקום לפתוח דלת חסרת תועלת אחרת ושאול אותך אם אתה רוצה להחליף ולקחת את הדלת שנותרה, היה שואל אותך אם אתה רוצה במקום הדלת הנוכחית שלך את *שתי* הדלתות האחרות גם יחד - האם נשמע הגיוני שבסיטואציה כזו ההסתברות שלך להצליח אם תקבל את הצעת המנחה היא 2/3? הרי יש לך שתי דלתות במקום אחת שהייתה קודם. אין שום הבדל בין הסיטואציה של "שתי הדלתות" וזו של ה"דלת אחרת שהראינו שהיא חסרת תועלת, ועוד הדלת הנוספת". |
|
|
|
|
|
|
||
|
||||
|
זה הסבר נאה מאוד. אם אנחנו כבר בעניינים כאלה, הנה סיפור על חידה שהביסה את האינטואיציה שלי. ידידי א"ש צעד אלי למשרד לפני כמה שבועות וסיפר לי שיש לו חידה שהוא שמע מנוגה אלון אבל הוא בטוח שהוא לא הבין היטב או לא זוכר נכון. אולי, תהה, אני מכיר את הנוסח הנכון של החידה ואוכל לזהות אותה מהסיפור השגוי שבידיו? ספר, אמרתי בנחת, אני מכיר את כל החידות. סיפר. לא הכרתי. התעצבנתי, ואמרתי לו שאני מסרב בתוקף לחשוב על החידה שכן היא, בעליל, מבקשת את הבלתי-אפשרי, ואין לי כח לנסות גם לנחש מה החידה הנכונה וגם לפתור אותה. בכל זאת, משנתקררה דעתי, הצעתי לשאול את דוד ג. אם הוא במקרה יודע משהו. חיפשנו, ומצאנו את החידה בבלוג של מישהו תחת (בערך) הכותרת "Seven puzzles you think you must not have heard correctly" אחרי שהפסקנו לצחוק קלטנו עד כמה עגום מצבנו: בידינו חידה שלא רק שאנחנו לא יודעים לפתור, אנחנו כל כך טפשים שנראה לנו שאי-אפשר בכלל.הנה החידה: יש אינסוף (בן-מנייה של) אנשים, ויש למצוא אסטרטגיה שתאפשר להם לעמוד באתגר הבא. לכל אחד מהם ישימו על הראש כובע שחור או לבן, וכל אחד מהם יראה את כל הכובעים פרט לזה שהוא עצמו חובש. ברגע הישמע הגונג צריכים כולם, סימולטנית, לרשום על פתק מה לדעתם הם חובשים. אסור להם לדבר, להרים גבה, לעשות פרצופים, כלום - שום תקשורת, והאסטרטגיה חייבת להבטיח שתמיד, תמיד, כולם-פרט-למספר-סופי ינחשו נכונה מה יש להם על הראש. נכון שיש טעות בפסקה הקודמת? |
|
|
|
|
|
|
||
|
||||
|
ודאי שיש טעות: אין אינסוף אנשים. ______________ אזהרת ספוילר (?) . . . . . . . . . (אגב, מתמטיקאי שחדתי לו את החידה הזאת אמר לי "קלי קלות. סליחה, קלי שקילות") |
|
|
|
|
|
|
||
|
||||
|
מנין לך? | |
|
|
|
|
|
||
|
||||
|
ספרתי. | |
|
|
|
|
|
||
|
||||
|
נו, אז איזה כובע יש לך על הראש? | |
|
|
|
|
|
||
|
||||
|
עזוב, אני בקושי יודע איך שלושה אנשים יכולים להסתדר עם בעיה דומה. | |
|
|
|
|
|
||
|
||||
|
הנה מה שנראה לי בתור פתרון לא-רשמי: הרמז של שכ"ג נתן לי את הרעיון הזה - נחלק את סידורי הכובעים למחלקות שקילות, כך ששני סידורי כובעים שקולים אם ורק אם הם נבדלים במספר סופי של מקומות. עכשיו, נבחר נציג מוסכם לכל מחלקת שקילות. כל משתתף יסתכל על הכובעים של כל שאר המשתתפים, ולכן יוכל לזהות באיזו מחלקת שקילות הוא (לא משנה אם הוא לובש כובע שחור או לבן; שני הסידורים שייכים לאותה מחלקה) ולכן הוא יביט על הנציג המוסכם של המחלקה ויגיד את הכובע שיש לו על הראש בנציג הזה. ברור גם שכל שני אנשים יחשבו בדיוק על אותה מחלקת שקילות, ולכן גם על אותו נציג מוסכם. הסידור האמיתי שונה מהנציג המוסכם רק במספר סופי של מקומות, אז יהיה רק מספר סופי של טעויות. |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי. מה הקשר בין הכובע של הנציג המוסכם לבין הצבע של הכובע של המתבונן? | |
|
|
|
|
|
||
|
||||
|
במחשבה שנייה - הבנתי אותך - *נציג* פירושו ההתאמה בין האנשים לכובעים, לא לאדם ספציפי. אני עדיין לא יודע אם מה שאמרת יכול לעבוד. | |
|
|
|
|
|
||
|
||||
|
איך תסכים על נציג מוסכם בלי לדבר? איך תזהה את מחלקת השקילות? |
|
|
|
|
|
|
||
|
||||
|
מתאמים מראש על אין סוף (?) אפשרויות? והתשובה לשאלה השניה? |
|
|
|
|
|
|
||
|
||||
|
זאת חידה, כן? אתה לא אמור להתעסק עם זה. הרי גם אי אפשר להודיע לאין סוף אנשים משהו בזמן סופי, מהירות האור וכל זה. התשובה לשאלה השנייה היא במחלקה של גדי. כנראה שיש משהו בתורת הקבוצות שמלמדת אותך איך לבנות מחלקות שקילות כאלו ולוודא שלא פספסת כלום. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שיש הבדל בין להניח זיכרון גדול כרצונך לבין להניח זכרון אין סופי. את הראשון בד"כ מקבלים בחידות כאלה, את השני? | |
|
|
|
|
|
||
|
||||
|
אם מדובר בחידה הכוללת את המושג אין-סוף נראה לי שקשה להמלט מכך. לדוגמה, נניח שלצורך הפיתרון אני דורש למספר כל אחד מהנוכחים באופן סידורי ( בן-מניה, כן?) ודורש מכל אחד לזכור את המספר שלו. תגיד לי שהפיתרון הזה לא בסדר משום שלכל זיכרון מוגבל N אפשר למצוא אדם שצריך N+1 ביטים כדי לזכור את המספר הסידורי שלו? | |
|
|
|
|
|
||
|
||||
|
עדיין לכל אחד יהיה זכרון בגודל מוגבל (גדל והולך, אבל עדיין מוגבל), אבל אם תוסיף שכל אחד לא מכיר רק את עצמו והמספר שלו, אלא גם את כל האחרים והמספר שלהם, אז נראה לי שהוספת דרישה חמורה יותר. | |
|
|
|
|
|
||
|
||||
|
וזה שצריך זמן אינסופי לתאם ביניהם, לא מפריע לך? | |
|
|
|
|
|
||
|
||||
|
לא במיוחד (זה פועל יוצא של תיאום בין אין סוף אנשים). | |
|
|
|
|
|
||
|
||||
|
ופועל יוצא של החלטה מה לעשות כשרואים אין סוף כובעים? אבל אתה צודק שיש משהו מטריד פה. אני התחלתי לחשוב על החידה עלי ידי כך שעשיתי לעצמי רשימה של איזה אינפורמציה מותר לכל איש להסיק מהרשימה. דוגמה למה שחשבתי שמותר: אחוזי הכובעים מכל צבע מותר להעמיד את כל האנשים בשורה ולעשות ממוצע משוקלל כלשהו ( נניח הראשון במשקל 1 השני במשקל 0.5 השלישי 0.25 וכולי) מותר *לבחור* קבוצה סופית כלשהו ולהתבונן בה מותר *לבחור* קבוצה אינסופית ולהסתכל על ממוצעים משוקללים אני מודה שלא חשבתי על האפשרות להשוות את הרשימה לטבלה של אין סוף רשימות שנקבעו מראש, אבל אני לא חושב שזה משהו יותר בעיתי. חידות הן לא תמיד "סגורות עד הסוף" מבחינת התנאים שלהם. |
|
|
|
|
|
|
||
|
||||
|
האמת, חשבתי שגם אחוז כובעים מכל צבע אי אפשר לחשב... (מצד שני, אח שלי אומר שהתשובה של גדי היא נכונה, ואם אח שלי אומר...) |
|
|
|
|
|
|
||
|
||||
|
אם הוא גדול *כרצונך*? אינך *רוצה* זכרון אינסופי? | |
|
|
|
|
|
||
|
||||
|
מה הבעיה להודיע לכולם בזמן סופי. הראשון ישב כאן, בתחילת הספסל. השני ישב באמצע. השלישי, באמצע החלק שנשאר... | |
|
|
|
|
|
||
|
||||
|
בוודאי. לכובע הראשון עובי של מילימטר אחד, לשני חצי מילימטר... (פיזיקאים קוראים לזה ''כובע מתמטי''). | |
|
|
|
|
|
||
|
||||
|
השאלה השנייה מטרידה גם אותי, ובלי לענות עליה אין לי פתרון *אלגוריתמי* לחידה (אבל אני מודה שאני לא חושב שיש). גם בשביל לבחור נציג מלכתחילה לכל מחלקה צריך את אקסיומת הבחירה. | |
|
|
|
|
|
||
|
||||
|
אין פתרון אלגוריתמי. יתר על כן, אין פתרון מדיד. הוכחה: אם הפונקציה שקובעת עבור כל איש האם להגיד שחור או לבן היא מדידה אז הסיכוי (בהנחה שהגרלנו את הצבעים באופן אחיד ובלתי תלוי) של כל איש לצדוק בניחוש הוא חצי. בהנתן אינסוף מאורעות בסיכוי חצי, הסיכוי שיקרו אינסוף מהם הוא לפחות חצי (מה שידוע בתור הלמה של פאטו, ההוכחה לא קשה). |
|
|
|
|
|
|
||
|
||||
|
מה זה מדיד? | |
|
|
|
|
|
||
|
||||
|
לצורכינו כאן: כזה שעבורו ההסתברות מוגדרת. | |
|
|
|
|
|
||
|
||||
|
איך מוכיחים שקבוצת מחלקות השקילות היא בת-מנייה? | |
|
|
|
|
|
||
|
||||
|
אה, הבנתי, תודה (-: | |
|
|
|
|
|
||
|
||||
|
עכשיו סוף-סוף הבנתי למה אקסיומת הבחירה זה לא דבר מובן מאליו. | |
|
|
|
|
|
||
|
||||
|
למה צריך כאן את אקסיומת הבחירה? הסדר הטוב לא מובן מאליו כשמדובר בקבוצה בת מניה? | |
|
|
|
|
|
||
|
||||
|
אני צריך אותה לא בשביל סדר טוב, אלא כדי לבחור נציג של כל מחלקת שקילות. יש מספר לא בן מניה של מחלקות שקילות, ואין לי מושג איך להציג בחירה מפורשת של נציג לכל מחלקה, או אם אפשר בכלל. | |
|
|
|
|
|
||
|
||||
|
רגע, חשבתי שהבנתי אבל מסתבר שטעיתי. אתם אומרים שיש א1 מחלקות שקילות, נציג לכל מלחקה, ומספר הנציגים הוא א0? ובצד, איך מוכיחים שמס' מחלקות השקילות אינו בן-מניה? | |
|
|
|
|
|
||
|
||||
|
מכיון שעוצמת כל מחלקת שקילות היא א0, ויש 2^א0 איברים בקבוצה, הרי שיש 2^א0 מחלקות שקילות (ו2^א0 נציגים). | |
|
|
|
|
|
||
|
||||
|
לא יודע מי אמר שמספר הנציגים הוא א0, אבל הוא עבד עליך. איך מוכיחים: מספר כל הסידורים האפשריים של כובעים הוא לא בן-מנייה (אלכסון קנטור); כל מחלקת שקילות היא כן בת-מנייה (מנה את הדרכים האפשריות לבצע מספר סופי של שינויים), ולכן מספר המחלקות איננו בן-מנייה. |
|
|
|
|
|
|
||
|
||||
|
סליחה, הבנתי לא נכון את הפתרון של גדי - משום מה חשבתי שבוחרים אדם לייצג כל מחלקת שקילות (אולי הטעה אותי המשפט "יביט על הנציג"), ולשם כך אין מספיק אנשים. תודה על ההוכחה; יש לי הרבה חלודה על גלגלי השיניים האלה, אבל כיף להתאמץ ולסובב אותם בכל זאת. ניסיתי ולא הצלחתי ללכסן קונסטרוקטיבית את מחלקות השקילות של החידה. יש דרך אלגנטית שפספסתי? |
|
|
|
|
|
|
||
|
||||
|
לא רק אותך זה בלבל, גם את ראובן. מה זה "ללכסן קונסטרוקטיבית"? לבחור קונסטרוקטיבית נציג לכל מחלקת שקילות? את זה אני חושש שאי-אפשר לעשות - אקסיומת הבחירה כנראה ממש נחוצה כאן. הפתרון דורש מאיתנו לדמיין שאינסוף אנשים המתכנסים לטכס עצה יכולים גם להכין פתקים עם מספר לא בן-מנייה של סידורים אפשריים מוסכמים. |
|
|
|
|
|
|
||
|
||||
|
לא, ב''ללכסן קונסטרוקטיבית'' כוונתי להוכחה שקבוצת מחלקות השקילות לא בת-מנייה - האם אתה יכול לעשות זאת בדרך ה''קלאסית'' של נניח-בשלילה-שכן-נסדר-בשורה-נבנה-נציג-שלא-שייך. | |
|
|
|
|
|
||
|
||||
|
כן - חלק את האנשים לאינסוף קבוצות בגודל אינסוף A1,A2,A3...(אתה יודע איך...) ותשתמש באלכסון של קנטור: מנה את מחלקות השקילות: M1,M2,M3... (M עבור מחלקה :-) ) תגדיר את סידור הכובעים B הבא לכל מחלקת שקילות,Mx, צבעי הכובעים של האנשים ב-Ax בסידור B הפוכים מאלה שב-Mx. תוצאה: B אינו שקול ל-Mk לכל k טבעי. (לפחות את זה הצלחתי) |
|
|
|
|
|
|
||
|
||||
|
אופס.. צ"ל "צבעי הכובעים... הפוכים מאלה שבנציג כלשהו של Mx" (הופ - אקסיומת הבחירה) | |
|
|
|
|
|
||
|
||||
|
מתברר שרק להודות באייל על הבורות שלי גורם לי לפתור: קודם עם גדי, עכשיו איתך. את מה שאתה כותב ניסיתי, אבל לא הצלחתי לחלק את האינסוף לקבוצות (השלב הראשון שלך, שהנחת שהוא קל; צריך כמובן שהקבוצות תהיינה "זרות מספיק"). עכשיו גיליתי לבד איך. תודה בכל אופן (-: | |
|
|
|
|
|
||
|
||||
|
איך? אני חושב על חלוקה לקבוצות בעזרת ראשוניים (קבוצה אחת של כל האיברים שמספרם הסידורי הוא חזקה של 2; קבוצה אחרת של חזקות של 3, וכן הלאה - ועוד קבוצה של כל אלו שלא נכנסו לאף אחת מהקבוצות הללו) אבל בטח יש משהו יותר פשוט. | |
|
|
|
|
|
||
|
||||
|
אוי, אני חמור. כל הזמן חשבתי מסביב לראשוניים, אבל על חזקות שלהם לא חשבתי. מה שכן חשבתי בסוף הוא טיפה יותר מסובך משלך: הראשון הוא כפולות של 2; השני הוא כפולות של 3 שאינן כפולות של 2; ... ה-N הוא כפולות של המספר הראשוני ה-N שאינן כפולות של שום מספר ראשוני קטן יותר. אגב, אאל"ט אינך צריך את הקבוצה האחרונה שלך (מתי בכלל תשתמש בה?). מה שמעניין הוא ששני הפתרונות שלנו נותנים קבוצות זרות לחלוטין, שזה יותר חזק ממה שנחוץ - אאעל"ט[*] מספיק שלכל שתי קבוצות An, Am יהיו ב-An אינסוף אברים שאין ב-Am. [*]עדיין |
|
|
|
|
|
|
||
|
||||
|
אתה חמור? לעולם אל תכנה את עצמך בכינויים מעליבים. תמיד יימצאו אחרים שיעשו את זה טוב ממך :) | |
|
|
|
|
|
||
|
||||
|
איפה תשים את 6 למשל? ועוד אפשרות: "מנה את הרציונליים החיוביים" (= העתקה חח"ע ועל מהם לשלמים החיוביים. אופס, לא ממש עזרתי נכון?), ותגדיר את הקבוצות כמספרים הסידוריים של כל הרציונליים בין 0 ל-1, בין 1 ל-2, בין 2 ל-3 וכו'. אבל זאת סתם התחכמות, ובטח יש מלא דרכים אחרות יפות. אגב, אולי מישהו סוף סוף יגיד לי מה זה אאל"ט ותטל"א? |
|
|
|
|
|
|
||
|
||||
|
אם אני לא טועה. תשובה טובה לשאלה אחרת. |
|
|
|
|
|
|
||
|
||||
|
בקבוצה הראשונה: כל האי זוגיים. בשניה: האי זוגיים כפול 2. ב-n: האי זוגיים כפול 2 בחזקת (n-1). |
|
|
|
|
|
|
||
|
||||
|
הקבוצה השנייה מכילה את השלישית, לא? | |
|
|
|
|
|
||
|
||||
|
לי יוצא שהן זרות: ...2,6,10,14,18 לעומת ...4,12,20,28 תקן אותי אם אני טועה. (הרעיון: מפרידים את הטבעיים לאי-זוגיים וזוגיים; קבוצת הזוגיים מתאימה לטבעיים כפול 2, אז אפשר לבצע בה הפרדה כמקודם; וחוזר חלילה). |
|
|
|
|
|
|
||
|
||||
|
צודק, התבלבלתי. | |
|
|
|
|
|
||
|
||||
|
את 6 אני אשים בסדרה הראשונה, כפולות של 2. אבל כפי שאמרתי לגדי בנוגע לקבוצת-כל-השאר שלו, אני לא חייב בכלל לשים אותו - אני צריך תתי קבוצות אינסופיות של השלמים, אבל אני לא חייב לכסות את *כל* השלמים; רק במקרה יצא לי כך. גם הדרך שלך לא פחות טובה - ואת ההעתקה מהרציונליים לטבעיים אני דווקא זוכר עדיין, לפחות זה (-: |
|
|
|
|
|
|
||
|
||||
|
גם אני סברתי שיש אדם שמייצג כל מחלקה. אם לא, מהו הנציג המוסכם? | |
|
|
|
|
|
||
|
||||
|
אכן היה עדיף להשתמש בתיאור כמו "סידור כובעים מוסכם". מחלקות השקילות הן של *סידורי כובעים* ששונים זה מזה רק במספר סופי של כובעים - לכן, לכל מחלקת שקילות בוחרים סידור כובעים מסויים מתוכה, ש"ייצג" אותה. אני פשוט כבר רגיל למחלקות שקילות ולכן "נציג" מתורגם אצלי אוטומטית ל"נציג של מחלקת שקילות", ולא לקונוטציות אפשריות אחרות. | |
|
|
|
|
|
||
|
||||
|
עם מחלקות שקילות אין לי בעיה, אבל מה פירוש "סידור כובעים מסוים" מתוך המחלקה? ומי בוחר את הסידור הזה? | |
|
|
|
|
|
||
|
||||
|
זו פשוט ההתאמה של כובע לכל אדם בקבוצה. למשל, סידור אחד הוא זה שבו לכל האנשים כובע שחור, סידור אחר הוא זה שבו לכולם כובע לבן, באחד אחר יש כובע שחור לכל האנשים שמספרם זוגי ולבן לכל אלו שמספרם אי זוגי (אם יש מספר בן מניה של אנשים, אפשר להתאים לכל אחד מספר מזהה שלם חיובי), וכו'. | |
|
|
|
|
|
||
|
||||
|
כל מחלקת שקילות היא בת מניה, אבל אוסף המחלקות אינו כזה! (בפרט, בטקס התיאום והחלפת האינפורמציה שלפני חשיפת הכובעים יש להעביר כמות אינפורמציה שאינה בת מניה, וזה גם צריך להיות גודל הזכרון הנגיש לכל משתתף). | |
|
|
|
|
|
||
|
||||
|
עכשיו אני מסתקרן אם אפשר לפתור את זה גם בלי אקסיומת הבחירה (למשל, לתת דרך קונסטורקטיבית לבחור נציג). מה אתה אומר, אפשר? | |
|
|
|
|
|
||
|
||||
|
נראה לי שאלון כיוון לבלוג הזה בהודעתו המקורית: קרא שם את מה שכתבה Luca. היא טוענת שאקסיומת הבחירה הכרחית ומנמקת. |
|
|
|
|
|
|
||
|
||||
|
תגובה 431503. | |
|
|
|
|
|
||
|
||||
|
נראה לי שפתרתי. . . . . . . . . . . . . . . . . . . . . האטסרטגיה לאדם: מסביבך תראה קבוצות של שלושה ומעלה שעומדות יציב, זוגות שעומדים בהמתנה, ובודדים בחיפוש. כל השלשות-ומעלה הן אחידות (כל השלושה לבנים, או כולם שחורים). התעלם מהם (מותר לך בסתר לבך לקנא). בין הזוגות (אם יש), תראה שחלק הם זוג שחור, חלק זוג לבן, וחלק זוג מעורב. חפש זוג שחור ונסה להצטרף אליו. אם הם נשארו, ברכותיי: אתה חלק משלשה שחורה, ושחור בעצמך. אם הם התסלקו בשאט נפש, ממך וזה מזה, ברכותיי: אתה לבן. חפש זוג לבן, או קבוצה לבנה גדולה יותר, והצטרף אליהם. אם אין זוג שחור, עשה ההפך עם זוג לבן. אם כולם או זוגות מעורבים או בודדים, חפש בודד שחור, קרא לו בסתר לבך "שוורץ", הצטרף אליו, והמתינו ביחד. אם בא אליכם בודד שחור נוסף, הישאר. אם גם שוורץ נשאר, ברכותיי: שלושתכם שחורים. אם שוורץ מסתלק, אתה לבן. אם בא אליכם בודד לבן, הסתלק. אינך יודע עדיין מה אתה; המשך לחפש. אם אין בסביבה בודד שחור, הצטרף לבודד לבן ופעל באופן סימטרי. אם אתה חלק מזוג בהמתנה, וכל מה שאתה רואה מסביבך הוא שלשות-ומעלה או זוגות אחרים בהמתנה, חכה רגע, ואם עדיין כולם מחכים, עזוב את שוורץ. יהיו בסיבה עוד שיעזבו את בן הזוג שלהם, והנה יש לך בודדים לבחור ביניהם. |
|
|
|
|
|
|
||
|
||||
|
זה נראה כסתירה ל''אסור להם לדבר, להרים גבה, לעשות פרצופים, כלום - שום תקשורת,'' | |
|
|
|
|
|
||
|
||||
|
חשבתי שהתנאי נועד רק לפסול התנהגות ש*מטרתה* להעביר מסר. באסטרטגיה שלי אתה מעביר מסר, אבל רק דרך התהנגות "טבעית" של חיפוש דומים לך על פי ניחוש, ותיקון הניחוש. סביר שבאמת זה לא עונה על התנאי שמחבר החידה התכוון לו, כי אז היא בטח לא מספיק קשה, ואם כך מעניין אותי האם החידה הקלה יותר שעניתי עליה בכל זאת שווה משהו. אשאל זאת כך: תחת מה שהרשיתי לעצמי, האם יש פתרונות יותר פשוטים? | |
|
|
|
|
|
||
|
||||
|
אבל זה סוג של תקשורת, לא? | |
|
|
|
|
|
||
|
||||
|
נחמד, גם אני לא הכרתי (א"ש הוא מי שאני חושב שהוא?). אבל כן הכרתי ורסיה דומה על שלושה אסירים בתאים והסוהר המטורף שמדליק ומכבה את הנורות בתאיהם. מכיר? |
|
|
|
|
|
|
||
|
||||
|
1. הפתרון של גדי מדוייק (למה "לא רשמי"?) - יפה! שים לב שהפתרון עובד גם אם האנשים עומדים בשורה המשתרעת ימינה "עד אינסוף", וכל אדם רואה רק את אלה שלימינו. 2. לסמיילי: ניסיתי להבהיר מפורשות בשאלה שמותר (וברור שחייבים) לבחור מראש אסטרטגיה. צריך גם להיות ברור שאין לשאלה הזו שום מובן אלגוריתמי; כל אדם מביט בכמות אינסופית של אינפורמציה, וקל להראות שאם הוא מגביל את עצמו להתבוננות במספר סופי של אנשים אז לשאלה אין פתרון. הבחירה של נציג לכל מחלקת שקילות היא בדיוק מה שאקסיומת הבחירה מאפשרת; בלעדיה, אני מניח שאין לשאלה מענה. 3. גם ניסיתי לחשוב על ואריאנטים אלגוריתמיים לבעייה. השאלה המעניינת כאן היא מה השאלה הנכונה. אפשר, למשל, להניח שיש עדיין אינסוף אנשים, אבל הסידור של הכובעים נתון ע"י נוסחה רקורסיבית: כל אדם מקבל תיאור אלגוריתמי המאפשר לו לחשב איזה כובע יש לאיש i, פרט לעצמו, וכל אדם צריך לחשב מתוך האלגוריתם הזה את הניחוש שלו. לא יצא לי עדיין לחשוב אם יש לחידה הזו פתרון. 4. הפתרון של ירדן לא עונה על תנאי הבעייה המקורית, אבל מעניין לחשוב איזו חידה הוא כן פותר. 5. א"ש הוא מי שאתה חושב שהוא. 6. זו החידה עם האולטרא-פילטר הלא-ראשי? אם כן, אז אני לא זוכר את החידה (ואם לא, אז גם לא). |
|
|
|
|
|
|
||
|
||||
|
1. הפתרון עובד גם אם הם רואים הרבה פחות מ"כל אלה שלימינו" - מספיק "כולם חוץ ממספר סופי". מענין מה קורה כשרואים עוד פחות. ברור שאם מחלקים לשתי קבוצות בנות מניה ועושים הכל על שתי הקבוצות במקביל, הפתרון עדיין עובד. השאלה היא מתי כבר אי אפשר. אולי כאשר יש אינסוף אנשים שרואים קבוצות כמעט זרות? 2. תגובה 431503. 3. שאלה מענינת. בטח בעיית העצירה נדחפת כאן איפשהו. או שלא. 5. האם זה אומר שא"ש בחו"ל או שאתה בארץ? 6. שלושה אסירים יושבים בשלושת תאיהם. הסוהר המטורף מדליק ומכבה את הנורות בתאים כאוות נפשו, פעם ביום, במשך אינסוף ימים, כאשר מאיזשהו יום, בלתי ידוע לאסירים, הוא מדליק אותו מספר נורות כל יום - או תמיד שתי נורות או תמיד אחת. אחרי אינסוף ימים פותחים את התאים ושואלים את האסירים האם הסוהר הדליק נורה אחת או שתיים אינסוף ימים. תן אסטרטגיה שתגרום לרובם לענות נכון. |
|
|
|
|
|
|
||
|
||||
|
1. מעניין, לא יודע. 5. זה אומר שהייתי בארץ לפני כמה שבועות. 6. תודה. זו באמת החידה של האולטרא-פילטר. |
|
|
|
|
|
|
||
|
||||
|
יש עוד חידה בז'אנר הזה... הרבה יותר קלה: אותם אינסוף אנשים מסתדרים הפעם בשורה ארוכה שמתחילה מאדם כלשהו. שוב מלבישים אותם בכובעים בצבעים אדום ושחור, וכל אחד יכול לראות רק את אלו שבאים אחריו. כללי המשחק: הראשון צועק איזשהו צבע, כל האחרים יכולים לשמוע אותו. לאחר מכן צועק השני צבע משלו, אחר כך תור השלישי וכך הלאה. עכשיו צריך להראות שיש אסטרטגיה שבה אם נשחק את המשחק לפיה, רק אחד מהם לכל היותר יטעה בניחוש הצבע של הכובע שלו. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שהתבלבלת בניסוח. כל אחד רואה מספר סופי או אין סופי? נ.ב.-אני כמעט בטוח שהחידה הזאת נשאלה באייל. |
|
|
|
|
|
|
||
|
||||
|
כל אחד רואה מספר אינסופי... מצטער אם זה כבר נשאל. | |
|
|
|
|
|
||
|
||||
|
לפני שאני ניגש לפתור את הבעיה, עליי לדעת אם פתרון זה יכול לעבוד גם במקרה שהכובעים הם בצבעי ירוק וסגול. | |
|
|
|
|
|
||
|
||||
|
לא. אם הצבעים הם ירוק וסגול, זה לא פתיר. | |
|
|
|
|
|
||
|
||||
|
אם כך, זהו רמז מועיל מאוד. הבנתי. | |
|
|
|
|
|
||
|
||||
|
זה הרבה יותר קל? החידה הזו מצריכה לפתור את השאלה הסופית ואז להשתמש במחלקות שקילות יותר מתוחכמות מבשאלה של אלון כדי לעבור למקרה האינסופי. בכל מקרה, יפה. | |
|
|
|
|
|
||
|
||||
|
הרבה יותר קל, כי אותה פתרתי ואת השאלה של אלון לא. | |
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |