שיתוף חידות שיתוף (ועוד העלאה באוב)

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

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

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

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

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

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

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

המטרה: שלכל היותר מספר סופי של אנשים יטעו בתשובה שיתנו.

בהצלחה!”

בהצלחה.