Question

huffman

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

הציעו אלגוריתם (אסטרטגיה) שיבטיח לבוב את התשובה הנכונה עם מספר ממוצע של

119363.305 \frac{119}{36} \approx 3.305

שאלות (כאשר הממוצע נלקח מעל הטלת הקוביות).

1

Answers

נסתכל על ההתפלגות של סכום של שתי קוביות הוגנות ועל עומק הצמתים בץ הופמן המתאים (בהמשך):

SumPdepth2136532364433645436365363763638536394363103363112364121365 \begin{array}{|l|l|l|} \hline \text{Sum} & \text{P} & \text{depth} \\\hline 2 & \frac{1}{36} & 5 \\3 & \frac{2}{36} & 4 \\4 & \frac{3}{36} & 4 \\5 & \frac{4}{36} & 3 \\6 & \frac{5}{36} & 3 \\7 & \frac{6}{36} & 3 \\8 & \frac{5}{36} & 3 \\9 & \frac{4}{36} & 3 \\10 & \frac{3}{36} & 3 \\11 & \frac{2}{36} & 4 \\12 & \frac{1}{36} & 5 \\\hline \end{array}

בוב יכול להציג לאליס את העץ הנ"ל ולשאול אותה אם הסכום נמצא בתת העץ הימני ולהמשיך באופן רקורסיבי לפי התשובה שלה. נשים לב שתוחלת מספר השאלות היא בדיוק משקל העץ הופמן - 11936\frac{119}{36}.

2
Feedback