שינויים
/* חידות עם שאלות */
=== חידות עם שאלות ===
''שאלה'' היא פסוק לוגי שאנחנו יכולים לבחור, תלוי בסוגים של תושבים והוא מהצורה <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 r=\begin{pmatrix}r_1\\\vdots\\r_m\end{pmatrix}</math> את וקטור התשובות. מההגדרות נובע ש־<math>\mathbf xq=\mathbf r</math> מוגדר כמקודם. מההגדרות נובע שאם <math>\mathbf x</math> הפתרון הנכון אז <math>\mathbf q=\mathbf r</math>מוגדר כמקודם.
:'''דוגמה 4:''' יש 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\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 r=\begin{pmatrix}0\\1\end{pmatrix}</math> אזי <math>\mathbf x=\begin{pmatrix}1\\0\\1\end{pmatrix}</math>, ובאופן כללי <math>\mathbf x=\begin{pmatrix}r_2\\r_1\leftrightarrow r_2\\r_1\or r_2\end{pmatrix}</math>.
נותר לפתח שיטה שתמצא וקטור שאלות הפותר כל חידה.
:'''דוגמה 5.1:''' <math>n=4</math> ונתון
{{left|<math>\begin{pmatrix}1&1&01&0\\0&0&0&0\\0&1&1&0&0\\10&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&01&0\\0&1&1&0&0\end{pmatrix}_\mathbf A\mathbf x=\underbrace\begin{pmatrix}1\\0\end{pmatrix}_\mathbf b</math>}}:שורות לפיכך <math>\mathbf Ak=2</math> בת״ל ומרחב הפתרונות לא גדל (ובוודאי לא קטן), כדרוש.
כדי לפתור את החידה נבחר <math>\mathbf Q\in\{0,1\}^{(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 r'</math>. מאידך, ב־<math>\mathbf q'</math> יש <math>m</math> שאלות ולכל אחת יש עד 2 תשובות אפשריות, לכן יש עד <math>2^m</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> מטריצה ריבועית ששורותיה בת״ל, כלומר היא הפיכה. {{משל}} נניח ש־<math>m</math> המספר ''המינימלי'' של שאלות שדרושות על מנת לפתור את החידה. בפסקה שלפני הקודמת הוכחנו ש־<math>n-k\le m</math> וכיוון ש־<math>\mathbf q=\mathbf Q\mathbf x</math> וקטור שאלות מאורך <math>n-k</math> הפותר את הבעיה נובע ש־<math>n-k\ge m</math>. כלומר, <math>m=n-k</math>. :'''דוגמה 5.2:''' עלינו למצוא את הסוגים של כל התושבים בשאלה 5 במינימום שאלות, כלומר ב־<math>m=n-k=4-2=2</math> שאלות. שני וקטורי שורה שאינם תלויים לינארית ב־<math>\begin{pmatrix}1&1&1&0\end{pmatrix},\begin{pmatrix}1&1&0&0\end{pmatrix}</math> הם לדוגמה <math>\begin{pmatrix}0&0&0&1\end{pmatrix},\begin{pmatrix}1&0&1&0\end{pmatrix}</math> ולכן <math>\mathbf q=\begin{pmatrix}X_4\\X_1\nleftrightarrow X_3\end{pmatrix}</math> וקטור שאלות מתאים. <math>\begin{pmatrix}\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 x=\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>.
==== מערכת עובדות לא לינאריות ====
