שינויים

באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות בנוגע לאי דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל את הסוג של כמה מהתושבים) על סמך טענות שהתושבים טענו או על סמך שאלות כן/לא שהוא יכול שעליו לשאול, ולפעמים גם על סמך כמה עובדות שידועות לו.

* '''דוגמה 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> מאותו סוג כמוהו(כמו <math>C</math>). יש למצוא את הסוג של כל תושב.

נרצה ליצור מודל מתמטי לפתרון בעיות מסוג זה.

== סימונים והגדרות ==באלגברה בוליאנית מסמנים <math>\mathrm T</math> כפסוק אמת ו־<math>\mathrm F</math> כפסוק שקר. באופן דומה, אם תושב <math>A</math> הוא אביר אז נסמן נסמנו כ־<math>A=\mathrm T</math> ואם נוכל – <math>A=\mathrm F</math>. אם הוא מרגל נסמן <math>A=\mathrm S</math>. אם תושב <math>B</math> יכול להיות מרגל אז נסמן את נכונות הטענה ה־<math>i</math> במספר שלו כ־<math>b_i</math>. כלומר, אם הטענה נכונה נסמן אז <math>b_i=\Leftrightarrow\mathrm T</math> ואחרת <math>b_i=\Leftrightarrow\mathrm F</math>. מכך נובע שאם הטענה ה־<math>i</math> של <math>B</math> היא <math>P</math> אז <math>b_i\Leftrightarrow P</math>, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול <math>b_i\leftrightarrow P\Leftrightarrow\mathrm T</math>. מובן שאם <math>B</math> אביר או נוכל אז <math>\forall i:\ b_i=\Leftrightarrow B</math>, ולכן אם אנו כבר יודעים שתושב <math>B</math> אינו מרגל אז נסמן את טענותיו פשוט כ־<math>B</math>.

=== דוגמה ===באמצעות סימונים אלו נפתור את דוגמה 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):

מכך נובע ש־<math>\{\mathrm T,\mathrm F\}</math> שדה. נגדיר סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{\mathrm T,\mathrm F\}</math>) בתור <math>P_1\leftrightarrow\dots\leftrightarrow P_m</math> ומכפלה <math>\prod_{i=1}^m P_i</math> בתור <math>P_1\or\dots\or 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>\mathrm T,\mathrm F</math> אז נוכל להציג כל שרשור <math>P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע. לדוגמה, <math>B\leftrightarrow A\leftrightarrow\mathrm F\Leftrightarrow\mathrm T</math> מפתרון דוגמה 1 שקול ל־<math>A\leftrightarrow B\Leftrightarrow\mathrm F</math>, ששקול ל־<math>\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow\mathrm F</math>. ביטוי זה ניתן להציג גם כ־<math>\begin{pmatrix}\mathrm T&\mathrm T&\mathrm F&\mathrm F\end{pmatrix}\mathbf x\Leftrightarrow\mathrm F</math>, ולכן לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}\Leftrightarrow\mathbf b</math>. למשל, את דוגמה 1 ניתן להציג באופן הבא:{{left|<math>\underbrace\begin{pmatrix}\mathrm TF&\mathrm TF&\mathrm TF&\mathrm FT\\\mathrm TF&\mathrm TF&\mathrm FT&\mathrm FT\\\mathrm FT&\mathrm FT&\mathrm FT&\mathrm TF\\\mathrm F&\mathrm T&\mathrm F&\mathrm T&\mathrm F\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x\Leftrightarrow\underbrace\begin{pmatrix}\mathrm T\\\mathrm F\\\mathrm T\\\mathrm F\end{pmatrix}_\mathbf b</math>}}

הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (Rouché–Capelli) יש פתרון ל־<math>\mathbf{Ax}=\mathbf b</math> אם״ם <math>\mathbf b\in\operatorname{span}\left\{\operatorname{Col}_i(\mathbf A)\right\}_{i=1}^n</math> כאשר <math>\operatorname{Col}_i(\mathbf A)</math> העמודה ה־<math>i</math> של <math>\mathbf A</math>, ואם כן אז מרחב הפתרונות הוא ממימד <math>n-\operatorname{rank}(\mathbf A)</math>. מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן אז כמה פתרונות יש. מובן שבד״כ יש רק פתרון אחד לחידות הללו, כלומר <math>\mathbf A</math> הפיכה.