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

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

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

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

כעת לחידת הכובעים. אנסה להסביר את הפתרון בפירוט יחסי, שכן הוא אינו פשוט. ראשית, אנסה לנסח את הבעיה בצורה קצת יותר מתמטית, שאולי תהיה יותר ברורה מאנשים וכובעים: כל סידור אפשרי של כובעים לאנשים ניתן לתיאור באמצעות סדרה של אפסים ואחדות, כש-0 במקום ה-\( 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) ולכן שניהם שייכים לאותה מחלקת שקילות.

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

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

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