שינויים

:'''דוגמה 3:''' האורח נתקל בתושבים <math>A,B,C</math>, שאינם מרגלים. <math>A</math> טוען ש־<math>B</math> נוכל וגם <math>C</math> אביר, כלומר <math>A\leftrightarrow(\neg 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}}+\underbraceoverbrace{\underbrace1_{B\text{ is a knave}}+\underbrace2_{B\text{ is a knight}}}_^{A\text{ is a knave}}=4</math>. המערכת אינה לינארית ולכן אינה פתירה לפני באמצעות משפט רושה–קפלי.

חיסרון מהותי יותר הוא ששינוי של <math>\mathbf b</math> דורש פתרון מחדש של הבעיה כולה. <!---->כמו כן, הפתרון לא נותן לנו את התובנות שקיבלנו מפתרון כמערכת אנו נעזר בפתרון באמצעות מערכת משוואות לינאריות, תובנות שיעזרו לנו בחידות שבהן שואלים שאלות. <!---->

''שאלה'' היא פסוק לוגי שאנחנו יכולים לבחור, תלוי בסוגים של תושבים והוא מהצורה <math>X_i\leftrightarrow P</math> עבור פסוק לוגי <math>P</math> כרצוננו. למשל, את השאלה "האם <math>X_2</math> אביר?" שמופנת ל־<math>X_1</math> נייצג בתור <math>X_1\leftrightarrow X_2</math>. נסמן כ־<math>n</math> את מספר התושבים ונניח שמותר לשאול עד <math>m</math> שאלות. נסמן <math>\mathbf q=\begin{pmatrix}Q_1\\\vdots\\Q_m\end{pmatrix}</math> כווקטור השאלות. ''תשובה'' תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־<math>\mathbf br=\begin{pmatrix}b_1r_1\\\vdots\\b_mr_m\end{pmatrix}</math> את וקטור התשובות. <math>\mathbf x</math> מוגדר כמקודם. מההגדרות נובע שאם <math>\mathbf x</math> הפתרון הנכון אז <math>\mathbf q=\mathbf br</math>.

:'''דוגמה 4:''' יש 3 תושבים (<math>m=2,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\or X_2)=1</math>. וקטור השאלות <math>\mathbf q=\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 br=\begin{pmatrix}0\\1\end{pmatrix}</math> אזי <math>\mathbf x=\begin{pmatrix}1\\0\\1\end{pmatrix}</math>, ובאופן כללי <math>\mathbf x=\begin{pmatrix}b_2r_2\\b_1r_1\leftrightarrow b_2r_2\\b_1r_1\or b_2r_2\end{pmatrix}</math>.

<!--חידה בסיסית מסוג זה תבקש למצוא שאלות כך שניתן יהיה להסיק את סוגם של כל התושבים. נוכיח שתמיד ניתן להסתפק בווקטור שאלות כך ש־<math>\forall i:\ \exists j:\ Q_i=X_j</math>: פתרון אפשרי יוגדר כפתרון <math>\mathbf x</math> שמקיים את העובדות הנתונות. כל פתרון אפשרי ייתן החידה פתירה, כלומר קיים וקטור שאלות <math>\mathbf q</math> כך שלכל וקטור תשובות <math>\mathbf r</math> מתאים קיים פתרון <math>\mathbf x</math> יחידהמקיים <math>\mathbf q=\mathbf r</math>. לפיכך, לכן אם יש <math>N</math> פתרונות אפשריים אז יש <math>N</math> אפשרויות ל־<math>\mathbf br</math>. החידה פתירהב־<math>\mathbf q</math> יש <math>m</math> שאלות ולכל אחת יש עד 2 תשובות אפשריות, לכן קיים יש עד <math>2^m</math> אפשרויות ל־<math>\mathbf qr</math> כך שלכל , דהיינו <math>N\le2^m</math>. עתה יהי <math>l</math> האורך המינימלי של וקטור שאלות מהצורה <math>\mathbf bq'=\begin{pmatrix}X_{i_1}\\\vdots\\X_{i_l}\end{pmatrix}</math> שפותר את החידה וצריך להוכיח ש־<math>l\le m</math> ניתן למצוא פתרון.

נוכיח שתמיד ניתן להסתפק בווקטור שאלות לינאריות (כלומר הן מהצורה לפי המינימליות של <math>X_{i_1}\nleftrightarrow\dots\nleftrightarrow X_{i_k}l</math>): יהי נובע ש־<math>\mathbf q2^{l-1}</math> כך שלכל <math>\mathbf bN</math> ניתן למצוא פתרון. ... נתון פסוק לוגי מהצורה לכן <math>X_1\star X_22^{l-1}</math> כאשר <math>N\starle2^m</math> אופרטור בינארי בוליאני כלשהו. יש 4 אפשרויות לבחור <math>X_1,X_2לפיכך </math> ונניח שב־l-1<math>Nm</math> מתוכן הערך של הפסוק הוא 1. מספר האפשרויות ל־ולבסוף <math>l\mathbf ble m</math>. {{משל}}-->

-->חידה בסיסית מסוג זה תבקש למצוא נותר לפתח שיטה שתמצא וקטור שאלות כך שניתן יהיה להסיק את סוגם של הפותר כל התושביםחידה. במקרה שאין  ==== מערכת עובדות החידות האלה טריוויאליות – ניתן לשאול כל תושב "האם 1לינאריות =1?" ===במקרה זה העובדות הנתונות בשאלה יוצרות מערכת משוואות לינאריות <math>\mathbf A\mathbf x=\mathbf b</math>. אם שורות המטריצה <math>\mathbf A</math> תלויות לינארית ניתן למחוק כמה שורות ממנה (וגם את השורות המתאימות מ־<math>X_i\leftrightarrow1mathbf b</math>) ולהסיק את סוגוכך ששורותיה יהיו בת״ל ומרחב הפתרונות לא יישתנה. זאת כמובן כאשר מספר השאלות שמותר לשאול הוא לכל הפחות לכן נניח בה״כ ששורות <math>\mathbf A</math> בת״ל ונסמן את מספר התושבים, מה שחייב להתקייםהשורות ב־<math>k</math>. : אין עובדות, '''דוגמה 5.1:''' <math>n=4</math> ונתון{{left|<math>\begin{pmatrix}1&1&0&0\\0&0&0&0\\0&1&1&0\\1&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&0&0\\0&1&1&0\end{pmatrix}_\mathbf A\mathbf x=\underbrace\begin{pmatrix}1\\0\end{pmatrix}_\mathbf b</math> הוא לכל היותר }}:שורות <math>2\mathbf A</math> בת״ל ומרחב הפתרונות לא גדל (ובוודאי לא קטן), כדרוש. כדי לפתור את החידה נבחר <math>\mathbf Q\in\{0,1\}^m{(n-k)\times n}</math> כך ש־<math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}</math> מטריצה הפיכה, ואז <math>\mathbf q=\mathbf Q\mathbf x</math> ו־<math>\mathbf x=\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}^{-1}\begin{pmatrix}\mathbf b\\\mathbf r\end{pmatrix}</math>. כל נוכיח שהאורך של <math>\mathbf q=\mathbf Q\mathbf x</math> אינו עולה על <math>m</math>, כלומר לא שאלנו יותר מדי שאלות: פתרון אפשרי יוגדר כפתרון <math>\mathbf x</math> ייתן שמקיים את העובדות הנתונות. לפי משפט רושה–קפלי יש <math>2^{n-\operatorname{rank}(\mathbf A)}=2^{n-k}</math> פתרונות אפשריים. החידה פתירה, כלומר קיים וקטור שאלות <math>\mathbf q'</math> כך שלכל וקטור תשובות יחיד, לכן מספר האפשרויות ל־<math>\mathbf r'</math> מתאים קיים פתרון <math>\mathbf x</math> שווה למספר האפשרויות יחיד המקיים <math>\mathbf q'=\mathbf r'</math>. לפיכך יש <math>2^{n-k}</math> אפשרויות ל־<math>\mathbf br'</math>. כמו כןמאידך, מספר הפתרונות האפשריים הוא ב־<math>\mathbf q'</math> יש <math>m</math> שאלות ולכל אחת יש עד 2 תשובות אפשריות, לכן יש עד <math>2^nm</math> אפשרויות ל־<math>\mathbf r'</math>, לפיכך דהיינו <math>2^{n-k}\le2^m</math> ולבסוף ולכן <math>n-k\le m</math>, כדרוש. {{משל}} עתה נותר להראות שקיימת <math>\mathbf Q</math> כנ״ל, אבל זה די טריוויאלי: השורות של <math>\mathbf A</math> בת״ל ולכן הן בסיס לתת־מרחב של <math>\{0,1\}^{1\times n}</math> ממימד <math>k</math>. נבחר בסיס כלשהו לתת־מרחב המשלים האורתוגונלי לו ([http://en.wikipedia.org/wiki/Orthogonal_complement Orthogonal complement]) ונציב את איבריו כשורות מטריצה <math>\mathbf Q</math>. אזי <math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}\in\{0,1\}^{(k+n-k)\times n}=\{0,1\}^{n\times n}</math> מטריצה ריבועית ששורותיה בת״ל, כלומר היא הפיכה. {{משל}} ==== מערכת עובדות לא לינאריות ====