בתשובה לגדי אלכסנדרוביץ', 01/02/07 7:29
פרדוקסים 431400
זה הסבר נאה מאוד.

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

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

"Seven puzzles you think you must not have heard correctly"

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

הנה החידה:

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

נכון שיש טעות בפסקה הקודמת?
פרדוקסים 431407
ודאי שיש טעות: אין אינסוף אנשים.
______________
אזהרת ספוילר (?)
.
.
.
.
.
.
.
.
.

(אגב, מתמטיקאי שחדתי לו את החידה הזאת אמר לי "קלי קלות. סליחה, קלי שקילות")
פרדוקסים 431410
מנין לך?
פרדוקסים 431413
ספרתי.
פרדוקסים 431416
נו, אז איזה כובע יש לך על הראש?
פרדוקסים 431423
עזוב, אני בקושי יודע איך שלושה אנשים יכולים להסתדר עם בעיה דומה.
פרדוקסים 431459
הנה מה שנראה לי בתור פתרון לא-רשמי:

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

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

הסידור האמיתי שונה מהנציג המוסכם רק במספר סופי של מקומות, אז יהיה רק מספר סופי של טעויות.
פרדוקסים 431462
לא הבנתי. מה הקשר בין הכובע של הנציג המוסכם לבין הצבע של הכובע של המתבונן?
פרדוקסים 431475
במחשבה שנייה - הבנתי אותך - *נציג* פירושו ההתאמה בין האנשים לכובעים, לא לאדם ספציפי. אני עדיין לא יודע אם מה שאמרת יכול לעבוד.
פרדוקסים 431465
איך תסכים על נציג מוסכם בלי לדבר?
איך תזהה את מחלקת השקילות?
פרדוקסים 431471
מותר לתאם *מראש*.
פרדוקסים 431480
מתאמים מראש על אין סוף (?) אפשרויות?

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

התשובה לשאלה השנייה היא במחלקה של גדי. כנראה שיש משהו בתורת הקבוצות שמלמדת אותך איך לבנות מחלקות שקילות כאלו ולוודא שלא פספסת כלום.
פרדוקסים 431492
אני חושב שיש הבדל בין להניח זיכרון גדול כרצונך לבין להניח זכרון אין סופי. את הראשון בד"כ מקבלים בחידות כאלה, את השני?
פרדוקסים 431495
אם מדובר בחידה הכוללת את המושג אין-סוף נראה לי שקשה להמלט מכך. לדוגמה, נניח שלצורך הפיתרון אני דורש למספר כל אחד מהנוכחים באופן סידורי ( בן-מניה, כן?) ודורש מכל אחד לזכור את המספר שלו. תגיד לי שהפיתרון הזה לא בסדר משום שלכל זיכרון מוגבל N אפשר למצוא אדם שצריך N+1 ביטים כדי לזכור את המספר הסידורי שלו?
פרדוקסים 431498
עדיין לכל אחד יהיה זכרון בגודל מוגבל (גדל והולך, אבל עדיין מוגבל), אבל אם תוסיף שכל אחד לא מכיר רק את עצמו והמספר שלו, אלא גם את כל האחרים והמספר שלהם, אז נראה לי שהוספת דרישה חמורה יותר.
פרדוקסים 431500
וזה שצריך זמן אינסופי לתאם ביניהם, לא מפריע לך?
פרדוקסים 431506
לא במיוחד (זה פועל יוצא של תיאום בין אין סוף אנשים).
פרדוקסים 431514
ופועל יוצא של החלטה מה לעשות כשרואים אין סוף כובעים?

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

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

(מצד שני, אח שלי אומר שהתשובה של גדי היא נכונה, ואם אח שלי אומר...)
פרדוקסים 431496
אם הוא גדול *כרצונך*? אינך *רוצה* זכרון אינסופי?
פרדוקסים 431574
מה הבעיה להודיע לכולם בזמן סופי. הראשון ישב כאן, בתחילת הספסל. השני ישב באמצע. השלישי, באמצע החלק שנשאר...
פרדוקסים 431579
כי הכובעים הם מנייר ולנייר יש עובי.
פרדוקסים 431670
בוודאי. לכובע הראשון עובי של מילימטר אחד, לשני חצי מילימטר... (פיזיקאים קוראים לזה ''כובע מתמטי'').
פרדוקסים 431914
על ראש המתמטיקאי בוער הכובע.
פרדוקסים 431489
השאלה השנייה מטרידה גם אותי, ובלי לענות עליה אין לי פתרון *אלגוריתמי* לחידה (אבל אני מודה שאני לא חושב שיש). גם בשביל לבחור נציג מלכתחילה לכל מחלקה צריך את אקסיומת הבחירה.
פרדוקסים 431503
אין פתרון אלגוריתמי. יתר על כן, אין פתרון מדיד.
הוכחה: אם הפונקציה שקובעת עבור כל איש האם להגיד שחור או לבן היא מדידה אז הסיכוי (בהנחה שהגרלנו את הצבעים באופן אחיד ובלתי תלוי) של כל איש לצדוק בניחוש הוא חצי. בהנתן אינסוף מאורעות בסיכוי חצי, הסיכוי שיקרו אינסוף מהם הוא לפחות חצי (מה שידוע בתור הלמה של פאטו, ההוכחה לא קשה).
פרדוקסים 432003
מה זה מדיד?
פרדוקסים 432006
לצורכינו כאן: כזה שעבורו ההסתברות מוגדרת.
פרדוקסים 431547
איך מוכיחים שקבוצת מחלקות השקילות היא בת-מנייה?
פרדוקסים 431548
אה, הבנתי, תודה (-:
פרדוקסים 431551
עכשיו סוף-סוף הבנתי למה אקסיומת הבחירה זה לא דבר מובן מאליו.
פרדוקסים 431561
למה צריך כאן את אקסיומת הבחירה? הסדר הטוב לא מובן מאליו כשמדובר בקבוצה בת מניה?
פרדוקסים 431569
אני צריך אותה לא בשביל סדר טוב, אלא כדי לבחור נציג של כל מחלקת שקילות. יש מספר לא בן מניה של מחלקות שקילות, ואין לי מושג איך להציג בחירה מפורשת של נציג לכל מחלקה, או אם אפשר בכלל.
פרדוקסים 431636
רגע, חשבתי שהבנתי אבל מסתבר שטעיתי. אתם אומרים שיש א1 מחלקות שקילות, נציג לכל מלחקה, ומספר הנציגים הוא א0? ובצד, איך מוכיחים שמס' מחלקות השקילות אינו בן-מניה?
פרדוקסים 431637
מכיון שעוצמת כל מחלקת שקילות היא א0, ויש 2^א0 איברים בקבוצה, הרי שיש 2^א0 מחלקות שקילות (ו2^א0 נציגים).
פרדוקסים 431638
לא יודע מי אמר שמספר הנציגים הוא א0, אבל הוא עבד עליך.

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

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

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

מנה את מחלקות השקילות: M1,M2,M3...
(M עבור מחלקה :-) )
תגדיר את סידור הכובעים B הבא
לכל מחלקת שקילות,Mx, צבעי הכובעים של האנשים ב-Ax בסידור B הפוכים מאלה שב-Mx.
תוצאה: B אינו שקול ל-Mk לכל k טבעי.

(לפחות את זה הצלחתי)
פרדוקסים 431708
אופס.. צ"ל "צבעי הכובעים... הפוכים מאלה שבנציג כלשהו של Mx" (הופ - אקסיומת הבחירה)
פרדוקסים 431739
מתברר שרק להודות באייל על הבורות שלי גורם לי לפתור: קודם עם גדי, עכשיו איתך. את מה שאתה כותב ניסיתי, אבל לא הצלחתי לחלק את האינסוף לקבוצות (השלב הראשון שלך, שהנחת שהוא קל; צריך כמובן שהקבוצות תהיינה "זרות מספיק"). עכשיו גיליתי לבד איך. תודה בכל אופן (-:
פרדוקסים 431760
איך? אני חושב על חלוקה לקבוצות בעזרת ראשוניים (קבוצה אחת של כל האיברים שמספרם הסידורי הוא חזקה של 2; קבוצה אחרת של חזקות של 3, וכן הלאה - ועוד קבוצה של כל אלו שלא נכנסו לאף אחת מהקבוצות הללו) אבל בטח יש משהו יותר פשוט.
פרדוקסים 431766
אוי, אני חמור. כל הזמן חשבתי מסביב לראשוניים, אבל על חזקות שלהם לא חשבתי. מה שכן חשבתי בסוף הוא טיפה יותר מסובך משלך: הראשון הוא כפולות של 2; השני הוא כפולות של 3 שאינן כפולות של 2; ... ה-N הוא כפולות של המספר הראשוני ה-N שאינן כפולות של שום מספר ראשוני קטן יותר. אגב, אאל"ט אינך צריך את הקבוצה האחרונה שלך (מתי בכלל תשתמש בה?). מה שמעניין הוא ששני הפתרונות שלנו נותנים קבוצות זרות לחלוטין, שזה יותר חזק ממה שנחוץ - אאעל"ט[*] מספיק שלכל שתי קבוצות An, Am יהיו ב-An אינסוף אברים שאין ב-Am.

[*]עדיין
פרדוקסים 431795
אתה חמור? לעולם אל תכנה את עצמך בכינויים מעליבים. תמיד יימצאו אחרים שיעשו את זה טוב ממך :)
פרדוקסים 431800
איפה תשים את 6 למשל?
ועוד אפשרות: "מנה את הרציונליים החיוביים" (= העתקה חח"ע ועל מהם לשלמים החיוביים. אופס, לא ממש עזרתי נכון?), ותגדיר את הקבוצות כמספרים הסידוריים של כל הרציונליים בין 0 ל-‏1, בין 1 ל-‏2, בין 2 ל-‏3 וכו'. אבל זאת סתם התחכמות, ובטח יש מלא דרכים אחרות יפות.

אגב, אולי מישהו סוף סוף יגיד לי מה זה אאל"ט ותטל"א?
פרדוקסים 431802
אם אני לא טועה.
תשובה טובה לשאלה אחרת.
פרדוקסים 431808
בקבוצה הראשונה: כל האי זוגיים.
בשניה: האי זוגיים כפול 2.
ב-n: האי זוגיים כפול 2 בחזקת (n-1).
פרדוקסים 432068
הקבוצה השנייה מכילה את השלישית, לא?
פרדוקסים 432071
לי יוצא שהן זרות:
...2,6,10,14,18
לעומת
...4,12,20,28
תקן אותי אם אני טועה.

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

גם הדרך שלך לא פחות טובה - ואת ההעתקה מהרציונליים לטבעיים אני דווקא זוכר עדיין, לפחות זה (-:
פרדוקסים 431683
גם אני סברתי שיש אדם שמייצג כל מחלקה. אם לא, מהו הנציג המוסכם?
פרדוקסים 431684
אכן היה עדיף להשתמש בתיאור כמו "סידור כובעים מוסכם". מחלקות השקילות הן של *סידורי כובעים* ששונים זה מזה רק במספר סופי של כובעים - לכן, לכל מחלקת שקילות בוחרים סידור כובעים מסויים מתוכה, ש"ייצג" אותה. אני פשוט כבר רגיל למחלקות שקילות ולכן "נציג" מתורגם אצלי אוטומטית ל"נציג של מחלקת שקילות", ולא לקונוטציות אפשריות אחרות.
פרדוקסים 431687
עם מחלקות שקילות אין לי בעיה, אבל מה פירוש "סידור כובעים מסוים" מתוך המחלקה? ומי בוחר את הסידור הזה?
פרדוקסים 431688
זו פשוט ההתאמה של כובע לכל אדם בקבוצה. למשל, סידור אחד הוא זה שבו לכל האנשים כובע שחור, סידור אחר הוא זה שבו לכולם כובע לבן, באחד אחר יש כובע שחור לכל האנשים שמספרם זוגי ולבן לכל אלו שמספרם אי זוגי (אם יש מספר בן מניה של אנשים, אפשר להתאים לכל אחד מספר מזהה שלם חיובי), וכו'.
פרדוקסים 431572
כל מחלקת שקילות היא בת מניה, אבל אוסף המחלקות אינו כזה! (בפרט, בטקס התיאום והחלפת האינפורמציה שלפני חשיפת הכובעים יש להעביר כמות אינפורמציה שאינה בת מניה, וזה גם צריך להיות גודל הזכרון הנגיש לכל משתתף).
פרדוקסים 431958
עכשיו אני מסתקרן אם אפשר לפתור את זה גם בלי אקסיומת הבחירה (למשל, לתת דרך קונסטורקטיבית לבחור נציג). מה אתה אומר, אפשר?
פרדוקסים 431984
נראה לי שאלון כיוון לבלוג הזה בהודעתו המקורית:

קרא שם את מה שכתבה Luca. היא טוענת שאקסיומת הבחירה הכרחית ומנמקת.
פרדוקסים 431992
תגובה 431503.
פרדוקסים 431466
נראה לי שפתרתי.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
האטסרטגיה לאדם: מסביבך תראה קבוצות של שלושה ומעלה שעומדות יציב, זוגות שעומדים בהמתנה, ובודדים בחיפוש. כל השלשות-ומעלה הן אחידות (כל השלושה לבנים, או כולם שחורים). התעלם מהם (מותר לך בסתר לבך לקנא). בין הזוגות (אם יש), תראה שחלק הם זוג שחור, חלק זוג לבן, וחלק זוג מעורב. חפש זוג שחור ונסה להצטרף אליו. אם הם נשארו, ברכותיי: אתה חלק משלשה שחורה, ושחור בעצמך. אם הם התסלקו בשאט נפש, ממך וזה מזה, ברכותיי: אתה לבן. חפש זוג לבן, או קבוצה לבנה גדולה יותר, והצטרף אליהם. אם אין זוג שחור, עשה ההפך עם זוג לבן. אם כולם או זוגות מעורבים או בודדים, חפש בודד שחור, קרא לו בסתר לבך "שוורץ", הצטרף אליו, והמתינו ביחד. אם בא אליכם בודד שחור נוסף, הישאר. אם גם שוורץ נשאר, ברכותיי: שלושתכם שחורים. אם שוורץ מסתלק, אתה לבן. אם בא אליכם בודד לבן, הסתלק. אינך יודע עדיין מה אתה; המשך לחפש. אם אין בסביבה בודד שחור, הצטרף לבודד לבן ופעל באופן סימטרי. אם אתה חלק מזוג בהמתנה, וכל מה שאתה רואה מסביבך הוא שלשות-ומעלה או זוגות אחרים בהמתנה, חכה רגע, ואם עדיין כולם מחכים, עזוב את שוורץ. יהיו בסיבה עוד שיעזבו את בן הזוג שלהם, והנה יש לך בודדים לבחור ביניהם.
פרדוקסים 431472
זה נראה כסתירה ל''אסור להם לדבר, להרים גבה, לעשות פרצופים, כלום - שום תקשורת,''
פרדוקסים 431479
חשבתי שהתנאי נועד רק לפסול התנהגות ש*מטרתה* להעביר מסר. באסטרטגיה שלי אתה מעביר מסר, אבל רק דרך התהנגות "טבעית" של חיפוש דומים לך על פי ניחוש, ותיקון הניחוש. סביר שבאמת זה לא עונה על התנאי שמחבר החידה התכוון לו, כי אז היא בטח לא מספיק קשה, ואם כך מעניין אותי האם החידה הקלה יותר שעניתי עליה בכל זאת שווה משהו. אשאל זאת כך: תחת מה שהרשיתי לעצמי, האם יש פתרונות יותר פשוטים?
פרדוקסים 431473
אבל זה סוג של תקשורת, לא?
פרדוקסים 431510
נחמד, גם אני לא הכרתי (א"ש הוא מי שאני חושב שהוא?).
אבל כן הכרתי ורסיה דומה על שלושה אסירים בתאים והסוהר המטורף שמדליק ומכבה את הנורות בתאיהם. מכיר?
תשובות 431539
1. הפתרון של גדי מדוייק (למה "לא רשמי"?) - יפה! שים לב שהפתרון עובד גם אם האנשים עומדים בשורה המשתרעת ימינה "עד אינסוף", וכל אדם רואה רק את אלה שלימינו.

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

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

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

5. א"ש הוא מי שאתה חושב שהוא.

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

2. תגובה 431503.

3. שאלה מענינת. בטח בעיית העצירה נדחפת כאן איפשהו. או שלא.

5. האם זה אומר שא"ש בחו"ל או שאתה בארץ?

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

5. זה אומר שהייתי בארץ לפני כמה שבועות.

6. תודה. זו באמת החידה של האולטרא-פילטר.
פרדוקסים 431550
יש עוד חידה בז'אנר הזה... הרבה יותר קלה:

אותם אינסוף אנשים מסתדרים הפעם בשורה ארוכה שמתחילה מאדם כלשהו. שוב מלבישים אותם בכובעים בצבעים אדום ושחור, וכל אחד יכול לראות רק את אלו שבאים אחריו.
כללי המשחק: הראשון צועק איזשהו צבע, כל האחרים יכולים לשמוע אותו. לאחר מכן צועק השני צבע משלו, אחר כך תור השלישי וכך הלאה.
עכשיו צריך להראות שיש אסטרטגיה שבה אם נשחק את המשחק לפיה, רק אחד מהם לכל היותר יטעה בניחוש הצבע של הכובע שלו.
parity bit 431578
אני חושב שהתבלבלת בניסוח. כל אחד רואה מספר סופי או אין סופי?
נ.ב.-אני כמעט בטוח שהחידה הזאת נשאלה באייל.
parity bit 431665
כל אחד רואה מספר אינסופי... מצטער אם זה כבר נשאל.
פרדוקסים 431591
לפני שאני ניגש לפתור את הבעיה, עליי לדעת אם פתרון זה יכול לעבוד גם במקרה שהכובעים הם בצבעי ירוק וסגול.
פרדוקסים 431664
לא. אם הצבעים הם ירוק וסגול, זה לא פתיר.
פרדוקסים 431680
אם כך, זהו רמז מועיל מאוד. הבנתי.
פרדוקסים 431600
זה הרבה יותר קל? החידה הזו מצריכה לפתור את השאלה הסופית ואז להשתמש במחלקות שקילות יותר מתוחכמות מבשאלה של אלון כדי לעבור למקרה האינסופי. בכל מקרה, יפה.
פרדוקסים 431666
הרבה יותר קל, כי אותה פתרתי ואת השאלה של אלון לא.
פרדוקסים 431701
טוב, יש לי פתרון "נורמאלי" (עם זיכרון סופי לכל אחד, אבל הולך וגדל) שנותן אחוז קטן כרצונכם , ואפילו 0 של טועים (אבל מספר אינסופי). לגבי החידה הקודמת, אני עדיין קצת בשוק מזה שלתת תשובה כמו בנציג של המחלקה (שאין לך שום סיבה לחשוב שצבע הכובע שלך בו זהה לצבע הכובע שלך באמת בהסתברות של יותר מ-‏50%) זה באמת יותר טוב מתשובה אקראית, אז אני לא מנסה אפילו לתת תשובה שמשתמשת בזה.
פרדוקסים 431885
אני קיבלתי שמחלקות השקילות (ואפילו הנציגים!) שגדי תאר בתגובה 431459, מספיקים גם כאן.
הנה שאלה: 431601
מה קורה אם יש מספר לא בן מניה של אנשים?

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

תחושת הבטן שלי היא שזה בדיוק מה שאפשר להשיג, אבל תחושות בטן לא שוות הרבה כשמדובר בתורת הקבוצות.
הנה שאלה: 431613
אני לא בטוח שהבנתי. אפשר תמיד להבטיח שכולם, פרט למספר סופי, יהיו צודקים. לא? כל עוצמה אחרת של טועים היא רק יותר קלה.
הנה שאלה: 431635
תגובה 427552.
זה מה שקורה כשחושבים בלילה.
הנה שאלה: 431639
תודֶה: התגובה הזו תלויה אצלך על הקיר, ממוסגרת, נכון?
הנה שאלה: 431641
לא, אבל זה רעיון.
מה שמזכיר לי: רון גראהם, שלקח על עצמו את ההתחיבויות של ארדש ז"ל התלונן פעם שמישהו פדה את הצ'ק...

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

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