שינויים

== הבעיה ==באי ב[https://en.wikipedia.org/wiki/Knights_and_Knaves חידות אבירים ונוכלים (Knights and Knaves)] מדברים על אי מסוים בו כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי, אך לא נעסוק בהם. החידות בנוגע לאי דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל – לרוב את הסוג של כמה מהתושבים) – על סמך טענות שהתושבים טענו כמה עובדות (שמרביתן מהצורה "תושב <math>X</math> טען ש־<math>P</math>") ו/או על סמך שאלות כן/לא שהוא יכול שעליו לשאול, ולפעמים גם על סמך כמה עובדות שידועות לו.

* '''דוגמה 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 2 שאלות של כן/לא הוא יכול האורח לשאול את התושבים על מנת לגלות להסיק את הסוג של כל אחד מהםהסוגים שלהם?

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

== סימונים ==__תוכן__באלגברה בוליאנית מסמנים <math>\mathrm T</math> כפסוק אמת ו־<math>\mathrm F</math> כפסוק שקר. באופן דומה, אם תושב <math>A</math> הוא אביר אז נסמן <math>A{| class=\mathrm T</math> ואם נוכל – <math>A"wikitable" style=\mathrm F</math>. אם הוא מרגל נסמן <math>A=\mathrm S</math>. אם תושב <math>B</math> יכול להיות מרגל אז נסמן את נכונות הטענה ה־<math>i</math> במספר שלו כ־<math>b_i</math>. כלומר, אם הטענה נכונה נסמן <math>b_i=\mathrm T</math> ואחרת <math>b_i=\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"direction:\ b_i=B</math>, ולכן אם אנו כבר יודעים שתושב <math>B</math> אינו מרגל אז נסמן את טענותיו פשוט כ־<math>B</math>. באמצעות סימונים אלו נפתור את דוגמה 1 כמערכת משוואות פשוטה. <math>A</math> טוען ש־<math>B,C</math> מאותו סוג, כלומר הוא טוען <math>B\leftrightarrow C</math>. לפיכך, מהטענות של <math>B,C</math> ומהעובדה ש־<math>A,C</math> שוניםltr; float:{{left|<math>\begin{array}{llcl}(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&\mathrm T\\(2)&B\leftrightarrow A\leftrightarrow\mathrm F&\Leftrightarrow&\mathrm T\\(3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&\mathrm T\\(4)&A\leftrightarrow C&\Leftrightarrow&\mathrm F\end{array}</math>}}באופן שקול; margin-top:0;"{{left|! <math>\begin{array}{llcl}(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&\mathrm T\\(2)&A\leftrightarrow B&\Leftrightarrow&\mathrm F\\(3)&D&\Leftrightarrow&\mathrm T\\(4)&A\leftrightarrow C&\Leftrightarrow&\mathrm F\end{array}P</math>}}עתה נציב את (2) ב־(1) ונקבל !! <math>\mathrm F\leftrightarrow C\Leftrightarrow\mathrm TQ</math>, כלומר !! <math>CP\Leftrightarrow\mathrm Fleftrightarrow Q</math>. נציב זאת ב־(4) ונקבל <math>A\Leftrightarrow\mathrm T</math>, ואם נציב את התוצאה ב־(2) נקבל <math>B\Leftrightarrow\mathrm F</math>. לסיכום, <math>A,D</math> אבירים ו־<math>B,C</math> נוכלים. == חידות ללא מרגלים ===== חידות לינאריות ==={| class="wikitable" style="float:left; clear:left; direction:ltr;"|+ טבלה 1

| 0 || 0 1 || T || T0

| 0 || 1 || F 0 || F0

| 1 || 0 || F || F|-| 1 || 1 || T || T

{| classבאלגברה בוליאנית מסמנים <math>1</math> כפסוק אמת ו־<math>0</math> כפסוק שקר. נעזר בסימון <math>\leftrightarrow</math> לציון אופרטור שקילות לוגית, המוגדר כמפורט בטבלה שמשמאל. <math>="wikitable" style</math> הוא יחס שקילות בין כל שני פסוקים שקולים לוגית, כלומר אם ידוע ש־<math>P\leftrightarrow Q</math> נותן 1 אז נוכל לסמן <math>P="float:left; clear:left; direction:ltr;"Q</math>. אם תושב <math>X</math> הוא אביר אז נסמן <math>X=1</math> ואם נוכל – <math>X=0</math>. לפיכך, אם <math>X</math> טוען טענה <math>P</math> אז <math>X=P</math>.|+ טבלה 2|-! :'''דוגמה 1.1:''' באמצעות סימונים אלו נציג את ''דוגמה 1'' כמערכת משוואות בוליאניות. <math>xA</math> !! טוען ש־<math>yB,C</math> !! מאותו סוג, כלומר הוא טוען <math>B\varphileftrightarrow C</math>. מכך נובעת משוואה (x\cdot y1)במערכת המשוואות הבאה. מהטענות של <math>B,C</math> !! נובעות המשוואות (2) ו־(3), ומהעובדה ש־<math>A,C</math> שונים נובעת משוואה (4):{{left|<math>\varphibegin{array}{llcl}(x1)&A\orleftrightarrow B\varphileftrightarrow C&=&1\\(y2)&B\leftrightarrow A\leftrightarrow1&=&1\\(3)&C\leftrightarrow C\leftrightarrow D&=&1\\(4)&A\leftrightarrow C&=&0\end{array}</math>}}|-:באופן שקול:{{left| 0 || 0 || T || T<math>\begin{array}{llcl}|-(1)&A\nleftrightarrow B\nleftrightarrow C&=&1\\| (2)&A\nleftrightarrow B&=&0 || \\(3)&D&=&1 || T || T\\|-| (4)&A\nleftrightarrow C&=&1 || 0 || T || T\end{array}</math>}}|-:כאשר <math>\nleftrightarrow</math> מציין אופרטור XOR, המסומן גם כ־<math>\oplus</math>.| בסימונים אלו נגדיר ''עובדה'' בתור משוואה בוליאנית שנתונה בחידה, כגון <math>A\leftrightarrow C=0</math> מ''דוגמה 1 || 1 || F || F''.|}אלו === חידות ללא שאלות ======= פתרון כמערכת משוואות ====ברגע שיש לנו ניסוח מתמטי של החידה כמערכת משוואות אפשר לפתור אותה כפי שעושים באלגברה בוליאנית. נתעמק בחידות שניתן לפתור כמערכת משוואות לינאריות.  ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2,+,\cdot)</math> ל־<math>(\{\mathrm T0,\mathrm F1\},\leftrightarrownleftrightarrow,\orand)</math> ע״י <math>\varphi:x\mapsto\begin{cases}\mathrm T0,&x=[0]_2\\\mathrm F1,&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\{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,\varphi(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\leftrightarrow\dots\leftrightarrow P_n=P_{n+y1}</math> בתור סכום של נעלמים שונים השווה לקבוע: לדוגמה, <math>B\leftrightarrow A\leftrightarrow1=1</math> מהניסוח המתמטי של ''דוגמה 1'' שקול ל־<math>A\nleftrightarrow B=0</math>, כלומר ל־<math>\sum_{X_i\in\{A,B\}}X_i=0</math>. לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}=\mathbf b</math>. :'''דוגמה 1.2:''' ההצגה המטריציונית של ''דוגמה 1'' היא{{left|<math>\underbrace\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x=\underbrace\begin{pmatrix}1\\0\\1\\1\end{pmatrix}_\mathbf b</math>}} הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (Rouché–Capelli)יש פתרון ל־<math>\Leftrightarrowmathbf{Ax}=\varphimathbf b</math> אם״ם <math>\mathbf b\in\operatorname{span}\left\{\operatorname{Col}_i(x\mathbf A)\leftrightarrowright\varphi}_{i=1}^n</math> כאשר <math>\operatorname{Col}_i(y\mathbf A)</math>העמודה ה־<math>i</math> של <math>\mathbf A</math>, ואם כן אז מרחב הפתרונות הוא ממימד <math>n-\operatorname{rank}(\mathbf A)</math>. מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן לחשב את מספר הפתרונות בתור <math>2^{n-\operatorname{rank}(\mathbf A)}</math>. מובן שבד״כ יש רק פתרון אחד, כלומר <math>\operatorname{rank}(\mathbf A)=n</math> ואז, אם ל־<math>\mathbf A</math> יש <math>n</math> שורות אז היא הפיכה. אם לא אז ניתן למחוק כמה שורות של <math>\mathbf A</math> (וגם את השורות המתאימות ב־<math>\mathbf b</math>) כך שהיא תהיה הפיכה. : טבלה '''דוגמה 1.* 3:''' נפתור את ''דוגמה 1''. חישוב פשוט מראה ש־<math>\varphimathbf A</math> הפיכה (ומכאן שיש פתרון יחיד) ו־<math>\mathbf A^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math>. לכן <math>\mathbf x=\cdot ymathbf A^{-1}\mathbf b=\begin{pmatrix}0\\0\\1\\1\end{pmatrix}</math> – התושבים <math>A,B</math> נוכלים ו־<math>C,D</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> אבירים, וקיבלנו פתרון יחיד. באופן כללי זו שיטה קלה יותר. אחד מהחסרונות שלה הוא שקשה למצוא באמצעותה את מספר הפתרונות, מה שעושים ע״י בדיקת היתכנות הסוג השני לכל תושב שניחשנו לו סוג. :'''דוגמה 3:''' האורח נתקל בתושבים <math>A,B,C</math>. <math>A</math> טוען ש־<math>B</math> נוכל וגם <math>C</math> אביר, כלומר <math>A\Leftrightarrowleftrightarrow(\varphineg B\and C)=1</math>. אם ננחש ש־<math>A</math> אביר נקבל פתרון יחיד, אך אם ננחש שהוא נוכל נקבל ש־<math>\neg B\and C=0</math>. במקרה הזה אפשר לנחש ש־<math>B</math> נוכל (ולקבל פתרון יחיד) או אביר (ולקבל שני פתרונות). מספר הפתרונות הוא אם כן <math>\underbrace1_{A\text{ is a knight}}+\underbrace{\overbrace1^{B\text{ is a knave}}+\overbrace2^{B\text{ is a knight}}}_{A\text{ is a knave}}=4</math>. המערכת אינה לינארית ולכן לא ניתן לחשב את מספר הפתרונות באמצעות משפט רושה–קפלי. חיסרון מהותי יותר הוא ששינוי של <math>\mathbf b</math> דורש פתרון מחדש של הבעיה כולה. כמו כן, אנו נעזר בפתרון באמצעות מערכת משוואות לינאריות בחידות שבהן שואלים שאלות. === חידות עם שאלות ===''שאלה'' היא פסוק לוגי שאנחנו יכולים לבחור ותלוי בסוגים של תושבים. למשל, את השאלה "האם <math>X_2</math> אביר?" שמופנת ל־<math>X_1</math> נייצג בתור <math>X_1\leftrightarrow X_2</math>, ואת השאלה "<math>X_1</math>, האם 3=3?" בתור <math>X_1\leftrightarrow1=X_1</math>. נסמן כ־<math>n</math> את מספר התושבים ונניח שמותר לשאול עד <math>m</math> שאלות. נסמן <math>\mathbf q=\begin{pmatrix}Q_1\\\vdots\\Q_m\end{pmatrix}</math> כווקטור השאלות. ''תשובה'' תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־<math>\mathbf r=\begin{pmatrix}r_1\\\vdots\\r_m\end{pmatrix}</math> את וקטור התשובות. מההגדרות נובע ש־<math>\mathbf q=\mathbf r</math>. <math>\mathbf x</math> מוגדר כמקודם, ואז ניתן לחשוב על <math>\mathbf q</math> כעל פונקציה <math>\mathbf x\mapsto\mathbf r</math>. :'''דוגמה 2.1:''' יש 3 תושבים (<math>n=3</math>), מותר לשאול עד 2 שאלות (<math>m=2</math>) ו־<math>X_3</math> טוען ש־<math>X_1</math> ו/או <math>X_2</math> אבירים, דהיינו <math>X_3\leftrightarrow(X_1\orX_2)=1</math>. וקטור השאלות <math>\varphimathbf q=\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\end{pmatrix}</math>, לדוגמה, מאפשר לפתור את החידה כי תמיד מתקיים <math>\mathbf x=\begin{pmatrix}r_2\\r_1\leftrightarrow r_2\\r_2\or (yr_1\leftrightarrow r_2)\end{pmatrix}=\begin{pmatrix}r_2\\r_1\leftrightarrow r_2\\r_1\rightarrow r_2\end{pmatrix}</math>. בחידות מסוג זה נתונות עובדות, ונסמן כ־<math>S</math> את קבוצת הפתרונות <math>\mathbf x</math> המקיימים אותן. בד״כ המטרה היא למצוא <math>\mathbf q</math> חח״ע מ־<math>S</math>, כלומר למצוא שאלות שעבורן לכל וקטור תשובות <math>\mathbf r=\mathbf q(\mathbf x)</math> ניתן יהיה להסיק את וקטור הסוגים של התושבים, <math>\mathbf x=\mathbf q^{-1}(\mathbf r)</math>. יהי <math>k\in\mathbb N\cup\{0\}</math> המספר המינימלי כך ש־<math>|S|\le2^k</math>. נוכיח ש־<math>k\le m</math>: טבלה החידה פתירה, כלומר קיים וקטור שאלות <math>\mathbf q</math> חח״ע מ־<math>S</math>. <math>\mathbf q</math> היא פונקציה על קבוצת וקטורי התשובות ולפיכך יש <math>|S|</math> אפשרויות ל־<math>\mathbf r</math>. מאידך, <math>\mathbf q</math> מורכבת מ־<math>m</math> שאלות ולכל אחת יש עד 2תשובות אפשריות, לכן יש עד <math>2^m</math> אפשרויות ל־<math>\mathbf r</math>, דהיינו <math>2^{k-1}<|S|\le2^m</math>.נקבל <math>k-1<m</math> ולבסוף <math>k\le m</math> כי <math>k,m\in\mathbb Z</math>. {{משל}} ==== מערכת עובדות לינאריות ====במקרה זה <math>S=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf b\}</math>. אם שורות המטריצה <math>\mathbf A</math> תלויות לינארית ניתן למחוק כמה מהן (וגם את השורות המתאימות ב־<math>\mathbf b</math>) כך ששורותיה יהיו בת״ל ו־<math>S</math> לא תשתנה. לכן נניח בה״כ ששורות <math>\mathbf A</math> בת״ל. :'''דוגמה 4.1:''' <math>n=4</math> ונתון{{left|<math>\begin{pmatrix}1&1&1&0\\0&0&0&0\\1&1&0&0\\0&0&1&0\end{pmatrix}\mathbf x=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}</math>}}:השורה השנייה במערכת זו מיותרת והשורה הרביעית היא סכום השורה הראשונה והשלישית. לכן נמחק את שורות 2,4 ונקבל{{left|<math>\underbrace\begin{pmatrix}1&1&1&0\\1&1&0&0\end{pmatrix}_\mathbf A\mathbf x=\underbrace\begin{pmatrix}1\\0\end{pmatrix}_\mathbf b</math>}}

מכך נובע ש־נשים לב שלפי משפט רושה–קפלי <math>|S|=2^{n-\operatorname{rank}(\mathrm T,\mathrm F\mathbf A)}=2^k</math> שדה. נגדיר סכום ולכן <math>\sum_operatorname{i=1rank}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{\mathrm T,\mathrm F\}</math>mathbf A) בתור <math>P_1\leftrightarrow\dots\leftrightarrow P_m=n-k</math> ומכפלה . השורות של <math>\prod_{i=1}^m P_imathbf A</math> בתור בת״ל ולכן יש לה <math>P_1\or\dots\or P_mn-k</math>שורות.

כעת, אם התושבים הם כדי לפתור את החידה נבחר <math>X_1,\dotsmathbf Q\in\{0,X_n1\}^{k\times n}</math> אז נגדיר כך ש־<math>\mathbf x:=\begin{pmatrix}X_1\mathbf A\\vdots\\X_nmathbf Q\end{pmatrix}</math>. אם כל <math>P_i</math> מייצג נעלם <math>X_j</math> או קבוע מטריצה הפיכה, ואז <math>\mathrm T,mathbf q=\mathrm Fmathbf Q\mathbf x</math> אז נוכל להציג כל שרשור ו־<math>P_1\leftrightarrowmathbf x=\dotsbegin{pmatrix}\leftrightarrow P_nmathbf A\Leftrightarrow P_\\mathbf Q\end{pmatrix}^{n+-1}</math> בתור סכום של נעלמים שונים השווה לקבוע. לדוגמה, <math>B\leftrightarrow Abegin{pmatrix}\leftrightarrowmathbf b\mathrm F\Leftrightarrow\mathrm Tmathbf r\end{pmatrix}</math> מפתרון דוגמה 1 שקול ל־. לשם כך צריך להראות שקיימת <math>A\leftrightarrow B\Leftrightarrow\mathrm Fmathbf Q</math>כנ״ל, ששקול ל־אבל זה די טריוויאלי: השורות של <math>\sum_{X_i\in\{mathbf A,B\}}X_i\Leftrightarrow\mathrm F</math>. ביטוי זה ניתן להציג גם כ־בת״ל ולכן הן בסיס לתת־מרחב של <math>\begin{pmatrix0,1\}^{1\mathrm T&\mathrm T&\mathrm F&\mathrm F\end{pmatrixtimes n}\mathbf x\Leftrightarrow\mathrm F</math>, ולכן נוכל להגדיר מטריצת מקדמים ממימד <math>\mathbf Ak</math> ווקטור מקדמים חופשיים <math>\mathbf b<. נבחר בסיס כלשהו ל[http:/math> כך ש־/en.wikipedia.org/wiki/Orthogonal_complement תת־מרחב המשלים האורתוגונלי] לו ונציב את איבריו כשורות מטריצה <math>\mathbf{Ax}\Leftrightarrow\mathbf bQ</math>. למשל, את דוגמה 1 ניתן להציג באופן הבא:{{left|אזי <math>\begin{pmatrix}\mathrm T&mathbf A\mathrm T&\mathrm T&\mathrm F\\\mathrm T&\mathrm T&\mathrm F&\mathrm F\\\mathrm F&\mathrm F&\mathrm F&\mathrm T\\\mathrm T&\mathrm F&\mathrm T&\mathrm Fmathbf Q\end{pmatrix}\beginin\{pmatrix0,1\}A^{(n-k+k)\times n}=\B{0,1\\C\\D\end{pmatrix}\Leftrightarrow\begin^{pmatrix}n\mathrm T\\\mathrm F\\\mathrm T\\\mathrm F\end{pmatrixtimes n}</math>מטריצה ריבועית ששורותיה בת״ל, כלומר היא הפיכה. {{משל}}

הצגה זו מאפשרת לנו :'''דוגמה 4.2:''' עלינו למצוא מה הסוג את הסוגים של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאתהתושבים בדוגמה 4 במינימום שאלות, לפי משפט רושה–קפלי (Rouché–Capelli) יש פתרון ל־כלומר ב־<math>k=n-\mathbfoperatorname{Axrank}=(\mathbf bA)=2</math> אם״ם שאלות (הוכחה ש־<math>k</math> הוא המספר המינימלי הדרוש של שאלות – בהמשך). שני וקטורי שורה שאינם תלויים לינארית ב־<math>\mathbf b\in\operatornamebegin{spanpmatrix}1&1&1&0\left\end{pmatrix},\operatornamebegin{Colpmatrix}_i(1&1&0&0\mathbf A)\right\}_end{i=1pmatrix}^n</math> כאשר הם לדוגמה <math>\operatornamebegin{Colpmatrix}_i(0&0&0&1\mathbf A)end{pmatrix},\begin{pmatrix}1&0&1&0\end{pmatrix}</math> העמודה ה־<math>i</math> של ולכן <math>\mathbf Aq=\begin{pmatrix}X_4\\X_1\nleftrightarrow X_3\end{pmatrix}</math>, ואם כן אז מרחב הפתרונות הוא ממימד וקטור שאלות מתאים. <math>n-\operatornamebegin{rankpmatrix}(\mathbf A)\\\mathbf Q\end{pmatrix}^{-1}=\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math>. מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן אז כמה פתרונות יש. מובן שבד״כ יש רק פתרון אחד לחידות הללו, כלומר והפתרון הכללי הוא <math>\mathbf Ax=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}\begin{pmatrix}1\\0\\\mathbf r\!\!\!\!\!\begin{matrix}&\\&\end{matrix}\end{pmatrix}</math> הפיכה.

== ראו גם == המספר המינימלי של שאלות ====* [httpנניח ש־<math>m</math> הוא המספר המינימלי של שאלות הדרוש לפתרון חידת שאלות נתונה ונרצה להוכיח ש־<math>m=k=\lceil\log_2(|S|)\rceil</math>:תהי <math>V=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf 0\}</math> כך ש־<math>\mathbf A\in\{0,1\}^{(n-k)\times n}</enmath> מטריצה כרצוננו ששורותיה בת״ל.wikipedia.orgלכן <math>|V|=2^{n-\operatorname{rank}(\mathbf A)}=2^k</wikimath> ובפרט קיימת פונקציה <math>f:S\to V</Knights_and_Knaves Knights and Knaves] בוויקיפדיה האנגליתmath> חח״ע.* [httpתהי <math>\mathbf Q\in\{0,1\}^{k\times n}</math> מטריצה כך ש־<math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}</math> הפיכה ואז <math>\mathbf q':\mathbf v\mapsto\mathbf Q\mathbf v</math> חח״ע מ־<math>V</enmath>.wikipediaנגדיר <math>\mathbf q=\mathbf q'\circ f</math> ולכן <math>\mathbf q</math> חח״ע מ־<math>S</math> והיא מורכבת מ־<math>k</math> שאלות, כלומר <math>k\ge m</math>.orgבעבר הוכחנו ש־<math>k\le m</wikimath> ולכן <math>m=k</The_Hardest_Logic_Puzzle_Ever The Hardest Logic Puzzle Ever] בוויקיפדיה האנגליתmath>.{{משל}}