שינויים

נגדיר ''שאלה'' כפסוק היא פסוק לוגי שאנחנו יכולים לבחור ושתלוי , תלוי בסוגים של תושביםוהוא מהצורה <math>X_i\leftrightarrow P</math> עבור פסוק לוגי <math>P</math> כרצוננו. למשל, כמו את השאלה "האם <math>X_2</math> אביר?" שמופנת ל־<math>X_1</math> נייצג בתור <math>X_1\or leftrightarrow X_2</math>. נסמן כ־<math>n</math> את מספר התושבים ונניח שמותר לשאול עד <math>m</math> שאלות כדי להסיק את הסוג של כל אחד מהם. נסמן <math>\mathbf pq=\begin{pmatrix}P_1Q_1\\\vdots\\P_mQ_m\end{pmatrix}</math> כווקטור השאלות. ''תשובה'' תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־<math>\mathbf b=\begin{pmatrix}b_1\\\vdots\\b_m\end{pmatrix}</math> את וקטור התשובות. מההגדרות נובע ישירות ש־<math>\mathbf p=\mathbf bx</math>מוגדר כמקודם. מההגדרות נובע שאם <math>\mathbf x</math> מוגדר כמקודםהפתרון הנכון אז <math>\mathbf q=\mathbf b</math>.

:'''דוגמה 4:''' <math>m=2,n=23</math> ו־<math>X_3</math> טוען ש־<math>X_1</math> ו/או <math>X_2</math> אבירים, דהיינו <math>X_3\leftrightarrow(X_1\or X_2)=1</math> ואין עובדות. וקטור השאלות <math>\mathbf pq=\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\leftrightarrow1\end{pmatrix}=\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\end{pmatrix}</math> מאפשר לפתור את החידה. – אם נניח, למשל, ש־<math>\mathbf b=\begin{pmatrix}0\\1\end{pmatrix}</math> אזי <math>\mathbf x=\begin{pmatrix}1\\0\\1\end{pmatrix}</math>, ובאופן כללי <math>\mathbf x=\begin{pmatrix}b_2\\b_1\leftrightarrow b_2\\b_1\or b_2\end{pmatrix}</math>. <!--נוכיח שאם לא נתונות עובדות אז <math>n\le m</math>: החידה פתירה, כלומר קיים וקטור <math>\mathbf p</math> כנ״ל כך שלכל <math>\mathbf b</math> ניתן להסיק את הפתרון. מספר האפשרויות ל  ושניתן להסתפק ב־<math>n</math> שאלות במקרה שאין מרגלים ואין עובדות החידות האלה טריוויאליות – ניתן לשאול כל תושב "האם 1=1?" (או כל שאלה אחרת שהתשובה לה ידועה) ולהסיק את סוגו. זאת כמובן כאשר מספר השאלות שמותר לשאול הוא לכל הפחות מספר התושבים, מה שחייב להתקיים אם החידה פתירה: נניח שיש <math>n</math> תושבים ו־<math>m</math> שאלות וצ״ל ש־<math>n\le m</math>. לא נתונות עובדות על התושבים ולכן כל אחד מהם יכול להיות מכל סוג, כלומר יש <math>2^n</math> פתרונות אפשריים. מספר הפתרונות האפשריים שווה גם ל־<math>2^n</math> ולכן <math>n=1=m</math>, כדרוש. עתה נניח ש־<math>n\le m</math> ל־<math>m,n</math> כלשהם ונוכיח שאם חידה עם <math>n+1</math> ו־

נוכיח שתמיד ניתן להסתפק בווקטור שאלות לינאריות (כלומר הן מהצורה <math>X_{i_1}\nleftrightarrow\dots\nleftrightarrow X_{i_k}</math>):'''דוגמה 5:''' יהי <math>n=5,m=3\mathbf q</math> וידוע ש־כך שלכל <math>\mathbf b</math> ניתן למצוא פתרון. ... נתון פסוק לוגי מהצורה <math>X_1\or star X_2=</math> כאשר <math>\star</math> אופרטור בינארי בוליאני כלשהו. יש 4 אפשרויות לבחור <math>X_1,X_2</math> ונניח שב־<math>N</math> מתוכן הערך של הפסוק הוא 1. מספר האפשרויות ל־<math>\mathbf b</math> ו־

במקרה הזה נצטרך להכליל כמה הגדרות ולהגדיר כמה דברים חדשים. נרחיב את יחס השקילות <math>=</math> לתאר שיוויון של מספרים ממשיים בין 0 ל־1. אם תושב <math>X</math> מרגל נסמן <math>X=p</math> עבור קבוע <math>p\in(0,1)</math> כלשהו. האופרטורים <math>\neg,\and,\leftrightarrow,\dots</math> מוגדרים מחדש כמפורט בטבלה משמאל. לפי ההגדרות החדשות <math>X\and Y</math>, למשל, הוא ההסברות שהתושבים <math>X,Y</math> ידברו אמת בהנחה שהתושב <math>X</math> דובר אמת בהסברות <math>X</math> והתושב <math>Y</math> – בהסתברות <math>Y</math>. הגדרות אלה מכלילות את ההגדרות מאלגברה בוליאנית, אך יש כמה כללים שהאופרטורים כבר לא מקיימים. כללי דה־מורגן, למשל, נשמרים, בעוד שלא תמיד מתקיים <math>X\leftrightarrow Y=(X\rightarrow Y)\and(X\leftarrow Y)</math>. לבסוף, נגדיר אופרטור <math>\equivLeftrightarrow</math> ע״י <math>X\equiv Leftrightarrow Y=\begin{cases}1,&X=Y\\0,&\text{else}\end{cases}</math> (בפרט, אם <math>X,Y</math> תושבים אז <math>X\equiv Leftrightarrow Y</math> הוא הערך הבוליאני שמציין אם הם מאותו סוג. אם <math>X,Y</math> אינם מרגלים אז <math>X\equiv Leftrightarrow Y=X\leftrightarrow Y</math>).

(2)&A\leftrightarrow(C\equiv0Leftrightarrow0)&\neq&0\\(3)&B\leftrightarrow(C\not\equiv0nLeftrightarrow0)&\neq&0\end{array}</math>}}:נעיר שמשוואה (1) לא רק נגררת מהעובדה שיש אביר, נוכל ומרגל, אלא שקולה לה. הוכחה: אגף ימין שלה אינו 0 או 1 ולכן לפחות אחד מ־<math>A,B,C</math> מרגל. נניח בלי הגבלת הכלליות ש־<math>A</math> מרגל ולכן <math>p\leftrightarrow B\leftrightarrow C=1-p-(B\leftrightarrow C)+2p(B\leftrightarrow C)=1-p</math>, ומכך נקבל <math>(B\leftrightarrow C)(1-2p)=0</math>. זה צריך להתקיים לכל <math>p\in(0,1)</math> ולכן <math>B\leftrightarrow C=0</math>, דהיינו <math>B+C-2BC=1</math>. חישוב באמצעות נגזרות יראה שלאגף שמאל יש נקודה קריטית אחת ב־ההסתברות ש־<math>B=C=1/2</math>, ואז אמר אמת אם״ם <math>B+C-2BC=1/2\ne1</math>אמר אמת תהא תמיד קטנה מ־1 אם לפחות אחד מהם מרגל. לכן היא מינימום והפתרון אם <math>(B,C)=0</math> נמצא על שפת אז <math>[0,C=1]^2</math>. נניח בלי הגבלת הכלליות ש־ואם <math>B=0,1</math> ונקבל אז <math>C=1,0</math> בהתאמה, כלומר אכן יש אביר אחד, נוכל אחד ומרגל אחד.<!--{{left|<math>\begin{array}{llcl}(1)&A\leftrightarrow B\leftrightarrow C&=&1-p\\(2)&A\rightarrow(C\Leftrightarrow0)&=&1\\(3)&\neg A\rightarrow(C\nLeftrightarrow0)&=&1\\(4)&B\rightarrow(C\nLeftrightarrow0)&=&1\\(5)&\neg B\rightarrow(C\Leftrightarrow0)&=&1\end{array}</math>}}-->

<!---->פותרים כמו באותו אופן כמו במקרה שאין מרגלים, רק שבמקום לבדוק עד 2 סוגים בודקים עד 3.