שינויים
* '''דוגמה 1:''' האורח נתקל בתושבים <math>A,B,C,D</math>. אין מרגלים, וידוע ש־<math>A,C</math> מסוגים שונים. <math>A</math> טוען ש־<math>B,C</math> מאותו סוג, <math>B</math> טוען ש־<math>A</math> אביר ו־<math>C</math> טוען שהוא מאותו סוג כמו <math>D</math>. מה הסוג של כל תושב?
* '''דוגמה 2:''' האורח נתקל בשלושה תושבים. אחד מהם אביר, אחד נוכל ואחד מרגל. אילו 3 שאלות של כן/לא הוא יכול לשאול על מנת לגלות את הסוג של כל אחד מהם, אם מותר לו להחליט למי להפנות כל שאלה על סמך התשובות לשאלות ששאל לפניה?
נרצה ליצור מודל מתמטי לפתרון בעיות מסוג זה.
| 1 || 1 || 1
|}
באלגברה בוליאנית מסמנים <math>1</math> כפסוק אמת ו־<math>0</math> כפסוק שקר. באופן דומה, אם תושב <math>X</math> הוא אביר אז נסמנו כ־<math>1</math> ואם נוכל – <math>0</math>. נעזר בסימון <math>\leftrightarrow</math> לציון אופרטור שקילות לוגית, המוגדר כמפורט בטבלה שמשמאל. <math>\Leftrightarrow</math> הוא יחס שקילות בין כל שני פסוקים שקולים לוגית, כלומר אם ידוע ש־<math>P\leftrightarrow Q</math> נותן 1 אז נוכל לסמן <math>P\Leftrightarrow Q</math>. לפיכך, אם <math>X</math> טוען ש־טענה <math>P</math> אז <math>X\Leftrightarrow P</math>.
'''דוגמה 1.1:''' באמצעות סימונים אלו נציג את ''דוגמה 1'' כמערכת משוואות בוליאניות. <math>A</math> טוען ש־<math>B,C</math> מאותו סוג, כלומר הוא טוען <math>B\leftrightarrow C</math>. מכך נובעת משוואה (1) במערכת המשוואות הבאה. מהטענות של <math>B,C</math> נובעות המשוואות (2) ו־(3), ומהעובדה ש־<math>A,C</math> שונים נובעת משוואה (4):
(3)&D&\Leftrightarrow&1\\
(4)&A\nleftrightarrow C&\Leftrightarrow&1\end{array}</math>}}
כאשר <math>\nleftrightarrow</math> מציין אופרטור XOR, המסומן גם כ־<math>\oplus</math>.
בסימונים אלו נגדיר ''עובדה'' בתור משוואה בוליאנית שנתונה בחידה, כגון <math>A\leftrightarrow C\Leftrightarrow0</math> מ''דוגמה 1''.
=== חידות ללא שאלות ===
ברגע שיש לנו ניסוח מתמטי של החידה כמערכת משוואות קל לפתור אותה. אנו נתעמק בחידות שניתן לפתור כמערכת משוואות לינאריות כיוון שהן נותנות מידע רב יותר על החידה, כפי שנראה בהמשך.
ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2,+,\cdot)</math> ל־<math>(\{0,1\},\nleftrightarrow,\and)</math> ע״י <math>x\mapsto\begin{cases}0,&x=[0]_2\\1,&x=[1]_2\end{cases}</math>. מכך נובע ש־<math>(\{0,1\},\nleftrightarrow,\and)</math> שדה. סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{1,0,1\}</math>) יוגדר בתור <math>P_1\nleftrightarrow\dots\nleftrightarrow P_m</math> ומכפלה <math>\prod_{i=1}^m P_i</math> בתור <math>P_1\and\dots\and P_m</math>. גם כפל מטריצות מוגדר בהתאם.
כעת, אם התושבים הם <math>X_1,\dots,X_n</math> אז נסמן <math>\mathbf x:=\begin{pmatrix}X_1\\\vdots\\X_n\end{pmatrix}</math>. אם כל <math>P_i</math> מייצג נעלם <math>X_j</math> או קבוע <math>1,0</math> אז נוכל להציג כל <math>P_1\nleftrightarrow\dots\nleftrightarrow P_n\Leftrightarrow P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע: לדוגמה, <math>B\leftrightarrow A\leftrightarrow0\Leftrightarrow1</math> מהניסוח המתמטי של ''דוגמה 1'' שקול ל־<math>A\nleftrightarrow B\Leftrightarrow1</math>, כלומר ל־<math>\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow1</math>. לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}\Leftrightarrow\mathbf b</math>.
מנחשים את סוגו של אחד מהתושבים ומציבים במשוואות. אם מגיעים לסתירה אז יש להחליף את הסוג שנבחר ולפתור מחדש, אחרת נקבל מערכת משוואות פשוטה יותר. אם המערכת הזו עוד לא נותנת פתרון יחיד יש להמשיך לנחש עד לפתרון הסופי. אם החלפנו ניחוש ושוב הגענו לסתירה אז אין פתרון.
'''דוגמה 1.4:''' ננחש ש־<math>A</math> מ''דוגמה 1'' הוא אביר. מ־(2) נובע ש־<math>B</math> אביר ומ־(4) ש־<math>C</math> נוכל, אך זה סותר את (1) ולכן <math>A</math> נוכל. הצבה מחדש נותנת ש־<math>B</math> נוכל ו־<math>C,D</math> אבירים, וקיבלנו פתרון יחיד.
באופן כללי זו שיטה קלה יותר. אחד מהחסרונות שלה הוא שקשה למצוא באמצעותה את מספר הפתרונות, מה שעושים ע״י בדיקת היתכנות הסוג השני לכל תושב שניחשנו לו סוג.
=== חידות עם שאלות ===
נגדיר ''שאלה'' כפסוק לוגי שאנחנו יכולים לבחור ושתלוי בסוגים של התושבים, כגון <math>X_1\or X_2</math>. נסמן כ־<math>n</math> את מספר התושבים ונניח שמותר לשאול עד <math>m</math> שאלות כדי להסיק את הסוג של כל אחד מהם. נסמן <math>\mathbf p\Leftrightarrow\begin{pmatrix}P_1\\\vdots\\P_m\end{pmatrix}</math> כווקטור השאלות. ''תשובה'' תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־<math>\mathbf b\Leftrightarrow\begin{pmatrix}b_1\\\vdots\\b_m\end{pmatrix}\in\{0,1\}^m</math> את וקטור התשובות. מההגדרות נובע ישירות ש־<math>\mathbf p\Leftrightarrow\mathbf b</math>. <math>\mathbf x</math> מוגדר כמו מקודם. '''דוגמה 4:''' <math>m=n=2</math> ואין עובדות. וקטור השאלות <math>\mathbf p\Leftrightarrow\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\end{pmatrix}</math> מאפשר לפתור את החידה. אם נניח, למשל, ש־<math>\mathbf b\Leftrightarrow\begin{pmatrix}0\\1\end{pmatrix}</math> אזי <math>\mathbf x\Leftrightarrow\begin{pmatrix}1\\0\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> ו־
== חידות עם מרגלים ==
