שיחת פורטל:מתמטיקה/חידה/38

ניסיון לפתרון חידת הבונוס

שינחשו. אם אינסוף מתמטיקאים ינחשו את צבע הכובע שלהם מבין שתי אפשרויות כ50% מהם יצדקו ו50% יטעו. מספר המתמטיקאים שיצדקו בניחושם הוא אינסוף בעצמה $\aleph _{0}$ תומר א. - שיחה 13:00, 23 בינואר 2009 (IST)

שיניתם את החוקים באמצע תומר א. - שיחה 13:02, 23 בינואר 2009 (IST)

כן, פתאום חשבתי שזה קל מדי אם מבקשים רק ש-$\aleph _{0}$ יינצלו אבל גם ככה הפתרון שלך לא נכון, כי הוא תלוי בהסתברות. תמיד יש סיכוי (קטן אך עדיין קיים) שבמקרה כל אחד ינחש בדיוק את הצבע הלא נכון, או שרק מספר סופי של מתמטיקאים (ולא $\aleph _{0}$) ינחשו את הצבע הנכון. בכל מקרה, נסה לפתור את החידה עבור כמעט כל המתמטיקאים ולא "רק" $\aleph _{0}$ מהם. ברק שושני - שיחה 14:09, 23 בינואר 2009 (IST)

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

על זה אפשר להתווכח, אך בכל מקרה לא פתרת החידה בניסוח החדש שלה. נסה לחשוב כמו מתמטיקאי ברק שושני - שיחה 19:11, 23 בינואר 2009 (IST)

אני מוכרח להגיד שזה נשמע לגמרי לא הגיוני. אם המתמטיקאים לא שומעים את התשובות של הקודמים להם בתור, אזי זה בדיוק כאילו כל אחד מהמתמטיקאים הוא הראשון בתור, ולכן אין שום דרך שהוא יכול לדעת מה הכובע על הראש שלו!? טוקיוני 15:36, 23 בינואר 2009 (IST)

גם אני בהתחלה לא הבנתי איך זה יכול להיות, אבל בסוף כשהצלחתי לפתור את החידה, זה בעצם נראה די הגיוני ברק שושני - שיחה 19:11, 23 בינואר 2009 (IST)

רצוי להעביר חידה זו לפורטל:מתמטיקה/חידה/38, כחידת המשך. ראו דוגמה בפורטל:מתמטיקה/חידה/33. דוד שי - שיחה 15:05, 23 בינואר 2009 (IST)

אני מבצע כמה העברות כדי לסדר קצת את האוסף. טוקיוני 15:36, 23 בינואר 2009 (IST)

נסיון לפתרון של חלק 1: אם קיים מספר סופי של כובעים מצבע מסוים טריוויאלי. נניח שלא... קיימים C אפשרויות של חלוקה של N לשני קבוצות זרות A,B שניהם מגודל אינסופי(AUB=N) כך שבכל קבוצה A או B קיימים מספר סופי של כובעים מאותו צבע. המתמטיקאים משתמשים בעקרון הסדר הטוב ומסדרים את האפשרויות האלה לפי סדר (איך? בשביל זה הם מתמטיקאים). לאחר ששמו עליהם את הכובעים כל אחד בוחר את החלוקה הראשונה מתוך אוסף החלוקות של A,B המתאימות לכובעים שלפניו ואומר את הצבע של רוב הכובעים בקבוצה שלו (A או B). מכיון שכל המתמטיקאים בחרו באותה חלוקה של A,B(כי אם הראשון פסל חלוקה מסויימת כי היא לא מביאה לחלוקה של מספר סופי של כובעים מאותו צבע אז גם כל הבאים אחריו יפסלו אותה מאותו שיקול) ובA וב B יש מספר סופי של כובעים מאותו צבע זה אומר שקיים רק מספר סופי של מתמטיקאים שיגידו צבע לא נכון. ―Shlosmem (שיחה | תרומות | מונה) לא חתם ‌ 00:00, 10 בינואר 2000 (IST)

מצטער, אך התשובה אינה נכונה. בתור התחלה, איך אתה יודע שניתן לחלק את N לשתי קבוצות אינסופיות זרות כך שבכל קבוצה קיים מספר סופי של כובעים מאותו הצבע? ברק שושני - שיחה 18:08, 4 בפברואר 2009 (IST)

הנחנו שקיימים אינסוף לבנים ואינסוף שחורים. אז ניתן לבנות קבוצה A שיש בה את כל הלבנים וקבוצה B שיש בה את כל השחורים. ניתן לבנות A שיש בה את כל הלבנים חוץ מאחד ושחור אחד וקבוצה B שיש לה את כל השחורים חוץ מאחד ולבן אחד וכן הלאה. אבל לא דייקתי ויש לדבר על סדרות ולא על קבוצות אז הנה הניסוח שוב.

קיימים C אפשרויות של חלוקה של הקבוצה N לשני סדרות זרות A,B שניהם מגודל אינסופי(AUB=N) כך שבכל סדרה A או B קיימים מספר סופי של כובעים מאותו צבע. המתמטיקאים משתמשים בעקרון הסדר הטוב ומסדרים את האפשרויות האלה לפי סדר (איך? בשביל זה הם מתמטיקאים). לאחר ששמו עליהם את הכובעים כל אחד בוחר את החלוקה הראשונה מתוך אוסף החלוקות של A,B המתאימות לכובעים שלפניו ואומר את הצבע של רוב הכובעים בסדרה שלו (A או B). מכיון שכל המתמטיקאים בחרו באותה חלוקה של A,B (כי אם הראשון פסל חלוקה מסויימת כי היא לא מביאה לחלוקה של מספר סופי של כובעים מאותו צבע אז גם כל הבאים אחריו יפסלו אותה מאותו שיקול) ובA וב B יש מספר סופי של כובעים מאותו צבע זה אומר שקיים רק מספר סופי של מתמטיקאים שיגידו צבע לא נכון. ―Shlosmem (שיחה | תרומות | מונה) לא חתם ‌ 00:00, 10 בינואר 2000 (IST)

זה שהחלפת "קבוצה" ב"סדרה" לא ממש מועיל. לצערי, זה עדיין רחוק מלהיות הפתרון הנכון. הוא מכיל טעויות ושימוש שגוי במושגים. אבל בינתיים היית הכי קרוב מכולם... ברק שושני - שיחה 12:01, 5 בפברואר 2009 (IST)

ובכן, אולי זה לא הפתרון שלך ויתכן שהטרמינולוגיה המתמטית שלי חלודה אבל לדעתי הוא בהחלט פותר. אם אתה חושב שהוא פתרון שגוי אנא נמק.Shlosmem - שיחה 13:03, 7 בפברואר 2009 (IST)

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

כתבתי שכאשר יש מספר סופי של כובעים מאותו צבע הפתרון טריוויאלי כי אז כולם אומרים את הצבע השני. ושאני מדבר על מקרה בו יש אינסוף משני הצבעים שאז אין בעייה לבנות שני סדרות כמו שהצעתי.Shlosmem - שיחה 10:54, 9 בפברואר 2009 (IST)

אוקיי, בכל מקרה, הבעיה העיקרית בפתרון שלך היא שאתה אומר "כל אחד בוחר את החלוקה הראשונה ואומר את הצבע של רוב הכובעים בסדרה שלו". תסביר לי בבקשה איך זה מבטיח שכולם פרט למספר סופי יגידו את הצבע הנכון. בנוסף, השימוש שלך כאן בעקרון הסדר הטוב לא ממש מובן לי. אין שום צורך להשתמש בזה בפתרון החידה. הפתרון שלך קרוב אבל הוא מאוד לא מדויק, הפתרון האמיתי הרבה יותר פשוט. ברק שושני - שיחה 15:36, 9 בפברואר 2009 (IST)

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

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

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

כעת, כל איש יסתכל האם הוא שייך לB או למשלימה שלה, אם הוא שייך ל-B הוא יבחר בצבע לבן, אחרת, בצבע שחור ושלום על ישראל.

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

(שים לב שאם המתמטיקאים הם במקרה אינטיאיציוניסטים, הפתרון לא יעבוד). Shlosmem - שיחה 16:48, 9 בפברואר 2009 (IST)

כתבת "ברור שקיימת כזו קבוצה למשל קבוצת כל המספרים הטבעיים של אנשי הכובעים השחורים ומשלימתה" - למה שבקבוצה הזאת יהיה מספר סופי של כובעים מצבע כלשהו...? ברק שושני - שיחה 17:39, 9 בפברואר 2009 (IST)

אני לא מבין אותך. בקבוצה הזו יש מספר סופי במיוחד של כובעים מצבע לבן - 0. ובמשלימתה 0 כובעים מצבע שחור. ―Shlosmem (שיחה | תרומות | מונה) לא חתם ‌ 00:00, 10 בינואר 2000 (IST)

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

אז בדוגמה שנתת, בה הקבוצה B היא קבוצת כל הכובעים השחורים, אם הוא שייך ל-B זה אומר שהוא בהכרח בעל צבע כובע שחור. אם כן: מאיפה הוא יכול לדעת, אך ורק מתוך הסתכלות בכובעים שלפניו, אם הוא נמצא בקבוצה או לא, כלומר אם יש על ראשו כובע שחור או לא? הרי זה כל העניין בחידה... ברק שושני - שיחה 18:44, 9 בפברואר 2009 (IST)

אני חושש שלא הבנת אותי נכון. כתבת "אז בדוגמה שנתת, בה הקבוצה B היא קבוצת כל הכובעים השחורים, אם הוא שייך ל-B זה אומר שהוא בהכרח בעל צבע כובע שחור. אם כן: מאיפה הוא יכול לדעת, אך ורק מתוך הסתכלות בכובעים שלפניו, אם הוא נמצא בקבוצה או לא" זה פשוט לא נכון. כדי לדעת האם הוא שייך לקבוצה או לא כל שעליו לדעת זה מהי הקבוצה ומה המספר שלו. הקבוצה B המדוברת, היא קבוצת מספרים טבעיים כלשהיא שמקיימת את התנאים שלעיל. הסדר של הקבוצות האלו לא תלוי במה שהמתמטיקאים רואים לפניהם. מה שהם רואים רק מכריע האם קבוצה חלקית מסויימת עומדת בדרישות או לא. ולאחר שמצאנו את הקבוצה הראשונה שעומדת בדרישות (שים לב, שכדי להכריע האם קבוצה עומדת בדרישות או לא. ניתן להתעלם ממספר סופי של פריטים) השאלה לאיזו קבוצה אדם מסויים משתייך לא קשורה לשאלה מה יש לו על הראש אלא למה שיש לכמעט כל שאר החברים באותה קבוצה על הראש. נניח למשל שכל המתמטיקאים עד מספר 10 הם בעלי כובע שחור, ולאחר מכן כל מתמטיקאי בעל מספר זוגי כובעו שחור, ואי-זוגי כובעו לבן (סתם דוגמא להבהרה בלי חשיבות), נניח כמו כן שבסדר הטוב שבחרנו הקבוצה הראשונה שמקיימת את התנאים שלעיל היא קבוצת המספרים הזוגיים. בשביל המתמטיקאי הראשון והאחד-עשרה וכל אחד אחר קבוצת המספרים האי-זוגיים עומדת בתנאים בלי שום תלות במה שיש לאלו שלפניהם על הראש. כיוון שהתנאים מתעלמים ממספר סופי של חריגות. ולכן המתמטיקאי הראשון יבחר בצבע שחור כי המספר שלו הוא אי-זוגי ובקבוצת המספרים האי-זוגיים נמצאים רק מספר סופי של כובעים שחורים. אני סקרן לדעת איך פתרת את החידה בלי להשתמש בעקרון הסדר הטוב. אבל אין מה לעשות איעזר בסבלנות עד שיגיע זמן הפתרון. ―Shlosmem (שיחה | תרומות | מונה) לא חתם ‌ 00:00, 10 בינואר 2000 (IST)

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

צר לי שלא השתכנעת. אני כלשעצמי משוכנע ולכן איני רואה עניין שאתייעץ במשתמשים נוספים.

יש לי פתרון דומה אך יותר פשוט.

ניקח את קבוצת הסדרות האינסופיות של שחור ולבן. נחלק אותם לקבוצות כך ששתי סדרות A,B יהיו באותה קבוצה אם A נבדלת מ B רק במספר סופי של איברים.

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

מכיון שכל המתמטיקאים בחרו באותה קבוצה (כי כולם ראו כמעט את אותם איברים) וכולם התייחסו לאותה סדרה מספר המתמטיקאים שיענו לא נכונה יהיה סופי.Shlosmem - שיחה 13:27, 11 בפברואר 2009 (IST)

כל הכבוד, זו התשובה הנכונה (בשביל שהיא תהיה פורמלית לחלוטין צריך לנסח אותה בצורה קצת יותר מדויקת עם מחלקות שקילות ואקסיומת הבחירה. אבל מה שכתבת נכון לחלוטין) ברק שושני - שיחה 14:39, 11 בפברואר 2009 (IST)

עכשיו נשאר לך לפתור את סעיף 2 ואת החידה למיטיבי לכת... ברק שושני - שיחה 14:43, 11 בפברואר 2009 (IST)

הפתרון זהה לחלוטין. נמספר את כל הצבעים. נסדר את כל הסדרות מעל N בסדר טוב כלשהוא. נגדיר יחס שקילות בין שתי סדרות: שתי סדרות שקולות אם"ם הם שווים פרט למספר סופי של איברים. כל המתמטיקאים יבחרו בסדרה הראשונה (בסדר הטוב) ששייכת למחלקת השקילות של הסדרה שכל האיברים עד המקום שהם נמצאים שווים למספר שרירותי כלשהוא ושאר איברי הסדרה שווים לסדרה שהם רואים לפניהם וינחשו את הצבע שמתאים להם לפי הסדרה הנבחרת. כמובן כל הסדרות שהם יבחרו שייכות לאותה מחלקת שקילות ולכן כולם יבחרו באותה סדרה ראשונה וכולם פרט למספר סופי ינצלו. (הבעיה בפתרונות האלו שהם לא קונסטרוקטיביים. ובמילים אחרות עקרון הסדר הטוב מניח שקיים סדר טוב על כל סדרות המספרים הטבעיים אבל לא נותן לנו אותו ולא מבטיח אפילו שהוא גדיר). החלק השני של החידה מעניין מאד ועדיין אין לי כיוון לפתור אותו. ―Shlosmem (שיחה | תרומות | מונה) לא חתם ‌ 00:00, 10 בינואר 2000 (IST)

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

בקשה להבהרה, כשאתה כותב: "שכל אחד יכול לראות את כל הכובעים שלפניו", הכוונה היא: א. שבמקרה של n מתמטיקאים כל מתמטיקאי רואה n-1 כובעים או ב. המתמטיקאי הראשון רואה n-1 כובעים, השני n-2 וכו'? (הקושי שלי הוא בהבנת השימוש המדויק של המילה "לפניו" לפניו בכלל או לפניו בתור?) תודה יאיר ―אנונימי לא חתםמש:אנונימי ‌ 00:00, 10 בינואר 2000 (IST)

הם כולם מסודרים בטור, עם הפנים קדימה, כאשר הראשון רואה את כל מי שלפניו (גם במקרה של אינסוף מתמטיקאים), השני רואה את כולם חוץ מהראשון ומעצמו, השלישי רואה את כולם חוץ משלושת הראשונים וכו'. ואז הם צריכים להגיד את הכובעים בסדר הזה (ראשון, שני, שלישי וכו'). ברק שושני - שיחה 15:36, 9 בפברואר 2009 (IST)

פתרון לחלק ב: כמו בחלק א רק שהמתמטיקאי הראשון יגיד שחור אם מספר אי ההתאמות בין הסדרה שהוא רואה לסדרה הראשונה במחלקת השקילות היא אי זוגית ויגיד לבן אם מספר ההתאמות זוגית. כיון שכל אחד שומע את אלו שמאחוריו כל אחד יכול לעשות את החשבון לפי אלו שמלפניו ולדעת אם הוא מתאים לסדרה או לא.Shlosmem - שיחה 21:55, 11 בפברואר 2009 (IST)

יפה מאוד! ברק שושני - שיחה 11:27, 12 בפברואר 2009 (IST)

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

פתרון חידת ה100

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

מראש משייכים מספר (0-99) לכל צבע, וכן מספר (0-99) לכל מתממטיקאי. כל מתמטיקאי "מניח" שסכום צבעי כל הכובעים (סכום המספרים המייצגים את צבעי כל הכובעים) מתחלק במאה עם השארית של מספרו האישי, ולפי כובעי האחרים המתמטיקאי גוזר את מספר כובעו (כלומר, את צבע כובעו). כיוון שבהכרח השארית נמצאת בין 0-99, הרי שאחד מן המתמטיקאים (לא פחות ולא יותר) - יצדק בצבע כובעו. 93.172.236.162 23:09, 20 בדצמבר 2009 (IST) כנראה פספסתי משהו: כל מתמטיקאי יודע שיש 100 צבעים ורואה 99 מהם, כך שכולם יכולים להסיק את צבע הכובע שעל ראשם. לא?

(באיחור רב) הפתרון נכון (בקשר לשאלה, הוספתי הבהרה בחידה) הוספתי אותו במקום הטקסט התמוה "יפורסם לאחר הפותר הראשון", שנותר שם זמן רב אחרי הפותר הראשון. שדדשכ • שיחה • כ"ד בתמוז ה'תשע"א • 01:22, 26 ביולי 2011 (IDT)