בתשובה לאלון עמית, 01/02/07 8:36
 |
|
 |
||
|
||||
 |
הנה מה שנראה לי בתור פתרון לא-רשמי: הרמז של שכ"ג נתן לי את הרעיון הזה - נחלק את סידורי הכובעים למחלקות שקילות, כך ששני סידורי כובעים שקולים אם ורק אם הם נבדלים במספר סופי של מקומות. עכשיו, נבחר נציג מוסכם לכל מחלקת שקילות. כל משתתף יסתכל על הכובעים של כל שאר המשתתפים, ולכן יוכל לזהות באיזו מחלקת שקילות הוא (לא משנה אם הוא לובש כובע שחור או לבן; שני הסידורים שייכים לאותה מחלקה) ולכן הוא יביט על הנציג המוסכם של המחלקה ויגיד את הכובע שיש לו על הראש בנציג הזה. ברור גם שכל שני אנשים יחשבו בדיוק על אותה מחלקת שקילות, ולכן גם על אותו נציג מוסכם. הסידור האמיתי שונה מהנציג המוסכם רק במספר סופי של מקומות, אז יהיה רק מספר סופי של טעויות. |
 |
 |
 |
|
|
|
||
|
||||
|
לא הבנתי. מה הקשר בין הכובע של הנציג המוסכם לבין הצבע של הכובע של המתבונן? | |
|
|
|
|
|
||
|
||||
|
במחשבה שנייה - הבנתי אותך - *נציג* פירושו ההתאמה בין האנשים לכובעים, לא לאדם ספציפי. אני עדיין לא יודע אם מה שאמרת יכול לעבוד. | |
|
|
|
|
|
||
|
||||
|
איך תסכים על נציג מוסכם בלי לדבר? איך תזהה את מחלקת השקילות? |
|
|
|
|
|
|
||
|
||||
|
מתאמים מראש על אין סוף (?) אפשרויות? והתשובה לשאלה השניה? |
|
|
|
|
|
|
||
|
||||
|
זאת חידה, כן? אתה לא אמור להתעסק עם זה. הרי גם אי אפשר להודיע לאין סוף אנשים משהו בזמן סופי, מהירות האור וכל זה. התשובה לשאלה השנייה היא במחלקה של גדי. כנראה שיש משהו בתורת הקבוצות שמלמדת אותך איך לבנות מחלקות שקילות כאלו ולוודא שלא פספסת כלום. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שיש הבדל בין להניח זיכרון גדול כרצונך לבין להניח זכרון אין סופי. את הראשון בד"כ מקבלים בחידות כאלה, את השני? | |
|
|
|
|
|
||
|
||||
|
אם מדובר בחידה הכוללת את המושג אין-סוף נראה לי שקשה להמלט מכך. לדוגמה, נניח שלצורך הפיתרון אני דורש למספר כל אחד מהנוכחים באופן סידורי ( בן-מניה, כן?) ודורש מכל אחד לזכור את המספר שלו. תגיד לי שהפיתרון הזה לא בסדר משום שלכל זיכרון מוגבל 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. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |