זוהי בעיה אינטראקטיבית.
סם העצלן ושרה החרוצה קיבלו משימה להמציא שתי התפלגויות מעניינות מעל קבוצת המחרוזות באורך $n$ מעל האלף-בית $\{H, T\}$. סם העצלן פשוט יטיל מטבע $n$ פעמים (כאשר כל צד מופיע בהסתברות $\frac{1}{2}$; כל הטלות המטבע הן בלתי תלויות) וירשום "H" עבור כל עץ ו-"T" עבור כל פלי. אתם רוצים לעזור לשרה החרוצה ללמד את סם העצלן לקח. נתון לכם מספר שלם $t$. עזרו לשרה להמציא התפלגות שהיא $t$-קרובה להתפלגות האחידה, תוך הוכחה אינטראקטיבית שאתם יכולים להבחין בין ההתפלגויות של סם העצלן ושרה החרוצה באמצעות גישת אורקל באורך $t$.
באופן פורמלי, עבור מספר שלם כלשהו $n$, נתבונן בקבוצה $S = \{H, T\}^n$ בגודל $2^n$, המורכבת מכל המחרוזות האפשריות באורך $n$ מעל האלף-בית בן שני התווים: "H" ו-"T". התפלגות מעל הקבוצה $S$ מוגדרת כמערך של מספרים ממשיים אי-שליליים $\{a_s\}_{s \in S}$ באורך $2^n$ המאונדקס על ידי איברי $S$, כך שסכומם שווה ל-$1$. אחת ההתפלגויות הפשוטות ביותר היא ההתפלגות האחידה, שבה כל ה-$a_s$ שווים ל-$2^{-n}$.
עבור זוג מספרים $\varepsilon \in [0; +\infty)$ ו-$k \in \{0, 1, \dots, n\}$, אנו אומרים ש-$\{a_s\}_{s \in S}$ היא התפלגות $(\varepsilon, k)$-בלתי תלויה אם, עבור כל בחירה של $k$ אינדקסים $1 \le i_1 < i_2 < \dots < i_k \le n$ וכל תת-קבוצה $T \subseteq \{H, T\}^k$ של מחרוזות באורך $k$ מעל האלף-בית $\{H, T\}$, מתקיים הדבר הבא: הסכום של $a_s$ על פני $2^{n-k}|T|$ המחרוזות $s$ שתת-הסדרה שלהן $s[i_1]s[i_2]\dots s[i_k]$ שייכת ל-$T$ סוטה מ-$\frac{|T|}{2^k}$ בלכל היותר $\varepsilon$. במונחים הסתברותיים, ניתן לבטא זאת כך:
$$\forall 1 \le i_1 < i_2 < \dots < i_k \le n \quad \forall T \subseteq \{H, T\}^k \quad \frac{|T|}{2^k} - \varepsilon \le \mathbb{P}_{s \leftarrow \{a_s\}_{s \in S}} \{s[i_1]s[i_2]\dots s[i_k] \in T\} \le \frac{|T|}{2^k} + \varepsilon.$$
באופן אינטואיטיבי, משמעות הדבר היא שכדי להבחין בין ההתפלגות לבין ההתפלגות האחידה, תצטרכו או להבחין בין הסתברויות שההפרש ביניהן אינו עולה על $\varepsilon$, או להסתכל על יותר מ-$k$ ביטים של המחרוזות הנוצרות על ידי ההתפלגות.
ההתפלגות $\{a_s\}_{s \in S}$ נקראת $t$-קרובה להתפלגות האחידה אם היא $(2^{-t}t, t)$-בלתי תלויה.
בהגדרה של $(\varepsilon, k)$-אי-תלות, השתמע שעליכם לבחור תחילה $k$ אינדקסים ורק אז לחקור את התפלגות ההסתברות על פני אותם $k$ אינדקסים. במודל גישת האורקל באורך $k$, הכל שונה. מחרוזת אקראית באורך $n$ נוצרת, ולאחר מכן מתנהלים $k$ סיבובים בפורמט הבא: אתם קוראים בשמו של מספר שלם $i \in \{1, 2, \dots, n\}$, ובתגובה נאמר לכם מהו $s[i]$. אתם יכולים להחליט לאיזה אינדקס לקרוא בפעם הבאה, תוך התחשבות בכל השאלות שנשאלו קודם לכן ובתשובותיהן.
כדי להוכיח שאתם יכולים להבחין בין ההתפלגויות של סם העצלן ושרה החרוצה, תצטרכו, בהינתן גישת אורקל באורך $t$ אל $m$ מחרוזות באורך $n$ שנדגמו מההתפלגויות שלהם (כל אחת נוצרה באופן בלתי תלוי ובאופן אחיד מההתפלגות של סם העצלן או מההתפלגות של שרה החרוצה), להסיק עבור כל אחת מהן מההתפלגות של מי היא נלקחה, ולנחש נכון לפחות $0.75m - 2\sqrt{m}$ פעמים.
פרוטוקול אינטראקציה
השורה הראשונה מכילה מספר שלם $t$, המציין את הקרבה הנדרשת להתפלגות אחידה ואת אורך גישת האורקל ($1 \le t \le 5$).
בתגובה, הדפיסו שורה עם מספר שלם יחיד $n$, המציין את אורך המחרוזות שעבורן אתם מוכנים לספק את ההתפלגות והוכחה אינטראקטיבית ליכולת ההבחנה ($t \le n \le 20$).
בשורה הבאה, הדפיסו שורה עם $2^n$ מספרים שלמים $b_s$, המגדירים את ההתפלגות שלכם ($0 \le b_s < 2^{64}$; $\sum_{s \in S} b_s > 0$). על סמך נתונים אלה, חבר השופטים יבחר את ההתפלגות $\{a_s\}_{s \in S}$ לפי הכלל $a_s = b_s / \sum_{s \in S} b_s$. הערכים של $b_s$ חייבים להיות רשומים בסדר לקסיקוגרפי של המחרוזות $s$: לדוגמה, עבור $n = 3$, יש להדפיס את המספרים בסדר הבא: $b_{HHH}, b_{HHT}, b_{HTH}, b_{HTT}, b_{THH}, b_{THT}, b_{TTH}, b_{TTT}$.
לאחר מכן, קראו מספר שלם $m$, המציין את מספר הבדיקות האינטראקטיביות ($1 \le m \le 10^4$). בהמשך יוצגו $m$ הבדיקות, שאותן יש להשלים בזו אחר זו.
בתחילת כל בדיקה, חבר השופטים יבחר תחילה את ההתפלגות $\{a_s\}_{s \in S}$ של סם העצלן או של שרה החרוצה בהסתברות $\frac{1}{2}$. לאחר מכן, חבר השופטים דוגם מחרוזת אקראית $s \sim \{a_s\}_{s \in S}$: כל מחרוזת $s$ יכולה להתקבל בהסתברות $a_s$. לאחר מכן חבר השופטים נותן לכם הזדמנות לשאול לא יותר מ-$t$ שאלות על התווים של המחרוזת $s$. כדי לשאול שאלה, הדפיסו שורה עם מספר שלם $q \in \{1, 2, \dots, n\}$, המציין את האינדקס של התו המעניין אתכם. לאחר מכן, קראו את התו "H" או "T" שהוא התשובה לשאילתה. לאחר ששאלתם בין $0$ ל-$t$ שאלות, הדפיסו שורה עם השם "Sam" אם אתם מאמינים ש-$s$ נלקחה מההתפלגות של סם העצלן, או "Sarah" אם אתם מאמינים ש-$s$ נלקחה מההתפלגות של שרה החרוצה. מיד לאחר מכן, עברו לבדיקה הבאה עד שתשלימו את כל $m$ הבדיקות.
ניתן להדפיס מחרוזות באותיות גדולות או קטנות.
לאחר כל שורה מודפסת, אל תשכחו לרוקן את חוצץ הפלט (flush).
דוגמה
קלט 1
2 3 T T T T T
פלט 1
3 7 4 8 9 7 6 7 1 1 2 SAM 1 2 Sarah 3 sARaH