שיתוף חידות שיתוף (ועוד העלאה באוב) – הפתרונות

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

כעת, אם חבורת שחקנים שהקשתות שלה מהוות מסלול מ-$latex s$ אל $latex t$ מתקבצת יחד ומחברת את כל החלקים שבידיה, היא תקבל בדיוק את סכום הביטים של $latex s$ ו-$latex t$, כלומר את הסוד – זאת מכיוון שכל צומת ביניים משתתפת פעמיים בחישוב, ולכן מתבטלת (לסכום שכזה, שכל האיברים בו פרט לראשון והאחרון מבטלים זה את זה, קוראים "טור טלסקופי"). במקרה השני, יש משפט בסיסי בתורת הגרפים לפיו גרף הוא לא דו צדדי אם ורק אם יש בו מעגל מאורך אי זוגי (נסו להוכיח; זה לא קשה). לכן במקרה הזה קבוצת השחקנים שלנו תחבר קשתות שמהוות מעגל שכזה – וכאן כל הביטים של הצמתים יתבטלו, וביט הסוד יחובר לעצמו מספר אי זוגי של פעמים – כל זוג מבטל את עצמו, ולכן נותרים בסוף עם האיבר האחרון בסכום, זה שלא היה לו זוג – ואיבר זה הוא בדיוק הסוד.

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

כעת לחידת הכובעים. אנסה להסביר את הפתרון בפירוט יחסי, שכן הוא אינו פשוט. ראשית, אנסה לנסח את הבעיה בצורה קצת יותר מתמטית, שאולי תהיה יותר ברורה מאנשים וכובעים: כל סידור אפשרי של כובעים לאנשים ניתן לתיאור באמצעות סדרה של אפסים ואחדות, כש-0 במקום ה-$latex i$ פירושו "לאדם מס' i יש כובע שחור" ו-1 מסמל כובע לבן. מכיוון שיש מספר אינסופי (בן מניה) של אנשים, גם הסדרה היא אינסופית. כל סדרה כזו אכנה בקצרה סידור. האתגר של השחקנים הוא כזה: בהינתן סידור שכולו ידוע לכל שחקן, פרט לאיבר אחד שלו (לכל שחקן חסר מידע על איבר אחר), צריך לנחש את הערך המתאים לאיבר האחד הזה, ומותר לכל היותר מספר סופי של טעויות.

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

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

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

פורמלית, יחס שקילות הוא פשוט אוסף של זוגות של איברים, כך שכל זוג איברים מקיים כלל מסויים (למשל, כלל השארית בחלוקה ב-2), ומקיים כמה דרישות נוספות: רפלקסיביות – שכל איבר יהיה שקול לעצמו. סימטריה – שלא תהיה חשיבות לסדר האיברים בהגדרה (כלומר, שלא יהיה מצב שבו x שקול ל-y אבל y לא שקול ל-x) ואולי הכי חשוב – שהיחס יהיה טרנזיטיבי; שאם x שקול ל-y וגם y שקול ל-z אז נובע מכך ש-x שקול ל-z. אם היחס מקיים את התכונה הזו, אז מובטח לנו שכל האיברים ב"עולם" שעליו אנחנו מדברים שייכים למחלקת שקילות כלשהי (בדוגמת המודולו 2 מובטח לנו שכל המספרים הם או זוגיים או אי זוגיים).

חזרה לעניין הכובעים. אנו מגדירים יחס שקילות על הסדרות האינסופיות של אפסים ואחדים בצורה הבאה: שתי סדרות הן שקולות אם מספר המקומות שבהם הן נבדלות זו מזו הוא סופי. ברור שכל סדרה שקולה לעצמה ושיש כאן סימטריה; הטרנזיטיביות היא קצת יותר מאתגרת, אך עדיין פשוטה: אם x נבדל מ-y ב-a מקומות, ואילו y נבדל מ-z ב-b מקומות, אז x נבדל מ-z לכל היותר ב-a+b מקומות (למה רק "לכל היותר" ולא "בדיוק"?) ולכן הוא עדיין נבדל ממנו במספר סופי של מקומות.

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

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

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

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

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

7 תגובות בנושא “שיתוף חידות שיתוף (ועוד העלאה באוב) – הפתרונות”

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

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

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

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

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

    נסמן ב-N את הטבעי המינימלי שהחל ממנו ואילך הסידור שנבחר מזדהה עם הנציג שלו במחלקת השקילות המתאימה. עבור טבעי כלשהו K, נשאל מהי ההסתברות לכך ש-K קטן מ-N. יותר פשוט להסתכל על המאורע המשלים, כלומר המקרה בו K גדול או שווה מ-N. אז בפרט האיבר ה-K-י בסדרה צריך להזדהות עם האיבר ה-K-י בנציג המתאים. אינטואיטיבית, זה קורה בהסתברות חצי (בהנחה שהסידור נבחר באופן אקראי מתוך אוסף כל הסדרות של אפסים ואחדים). לכן, ההסתברות לכך ש-K קטן מ-N היא לכל הפחות חצי. אבל באופן דומה, אם K גדול או שווה מ-N, אז בפרט האיבר ה-K-י והאיבר ה-K+1-י בסדרה צריכים להזדהות עם האיבר ה-K-י והאיבר ה-K+1-י בנציג, בהתאמה. לכן, ההסתברות ש-K קטן מ-N היא לכל הפחות 1-1/4, כלומר 3/4. באופן כללי, ההסתברות ש-K קטן מ-N היא לפחות 1 מינוס (1 חלקי חזקה טבעית של 2), כאשר מותר לבחור בתור החזקה כל טבעי שהוא. מאחר וזה נכון לכל טבעי שנבחר, ההסתברות ש-K קטן מ-N היא בהכרח 1. מאחר וזה נכון לכל K, ההסתברות שמספר טבעי כלשהו ממלא את התפקיד ש-N יועד לו היא אפס. אבל אנחנו יודעים שיש N כזה ובכך המוזרות. אני לא ממש בקיא בדברים האלו, אבל להבנתי הבעייתיות היא בכך שבהנחתנו את אקסיומת הבחירה, הבאנו לקיומן של קבוצות לא מדידות בקבוצת החזקה של מרחב המדגם, ובגלל זה לא קיימת מידת הסתברות שאת קיומה מניחים בניתוח לעיל.

  4. נדמה לי, קומנדוגרד, שהבעיה בניתוח ההסתברותי שלך פשוטה יותר.

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

    אם נסמן את המאורע "כמעט כל הכובעים לבנים" ב-A ואת "יש כובע שחור מחוץ ל-K הראשונים" ב-B, אתה שואל להסתברות של B בהינתן A. הבעיה היא של-A הסתברות 0 (יש מיליוני דרכים לראות את זה), לכן אסור להתנות בו, ולכן ההסתברות שאתה מתעניין בה בכלל לא מוגדרת.

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *