שינויים

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

* '''דוגמה 2:''' האורח נתקל בשלושה תושבים. , ואחד מהם טוען שלפחות אחד מהם משני התושבים האחרים הוא אביר, אחד נוכל ואחד מרגל. אילו 3 2 שאלות של כן/לא הוא יכול האורח לשאול את התושבים על מנת לגלות להסיק את הסוג של כל אחד מהם, אם מותר לו להחליט למי להפנות כל שאלה על סמך התשובות לשאלות ששאל לפניההסוגים שלהם?

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

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

:'''דוגמה 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}}+\overbraceunderbrace{\underbrace1_overbrace1^{B\text{ is a knave}}+\underbrace2_overbrace2^{B\text{ is a knight}}}^_{A\text{ is a knave}}=4</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\leftrightarrow X_1\leftrightarrow X_1\leftrightarrow 1leftrightarrow1=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>.

:'''דוגמה 42.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\or X_2)=1</math>. וקטור השאלות <math>\mathbf 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 (r_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> בת״ל ונסמן את מספר השורות ב־<math>k</math>.

:'''דוגמה 54.1:''' <math>n=4</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>|S|=2^{n-\operatorname{rank}(\mathbf A)}=2^{n-k}</math> פתרונות אפשריים. החידה פתירה, כלומר קיים וקטור שאלות ולכן <math>\mathbf q'</math> כך שלכל וקטור תשובות <math>operatorname{rank}(\mathbf r'</math> מתאים קיים פתרון <math>\mathbf x</math> יחיד המקיים <math>\mathbf q'A)=\mathbf r'</math>. לפיכך יש <math>2^{n-k}</math> אפשרויות ל־<math>\mathbf r'</math>. מאידך, ב־השורות של <math>\mathbf q'A</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\in\{0,1\}^{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</math> כנ״ל, אבל זה די טריוויאלי: השורות של <math>\mathbf A</math> בת״ל ולכן הן בסיס לתת־מרחב של <math>\{0,1\}^{1\times n}</math> ממימד <math>k</math>. נבחר בסיס כלשהו ל[http://en.wikipedia.org/wiki/Orthogonal_complement תת־מרחב המשלים האורתוגונלי] לו ונציב את איבריו כשורות מטריצה <math>\mathbf Q</math>. אזי <math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}\in\{0,1\}^{(k+n-k+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>. :'''דוגמה 54.2:''' עלינו למצוא את הסוגים של כל התושבים בדוגמה 5 במינימום שאלות, כלומר ב־<math>mk=n-k=4-2\operatorname{rank}(\mathbf A)=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>. ==== מערכת עובדות לא לינאריות ==== == חידות עם מרגלים =={| class="wikitable" style="direction:ltr; float:left; margin-top:0;"! אופרטור !! ערך|-| <math>\neg X</math> || <math>1-X</math>|-| <math>X\and Y</math> || <math>XY</math>|-| <math>X\uparrow Y</math> || <math>1-XY</math>|-| <math>X\or Y</math> || <math>X+Y-XY</math>|-| <math>X\downarrow Y</math> || <math>1-X-Y+XY</math>|-| <math>X\rightarrow Y</math> || <math>1-X+XY</math>|-| <math>X\nrightarrow Y</math> || <math>X-XY</math>|-| <math>X\leftarrow Y</math> || <math>1-Y+XY</math>|-| <math>X\nleftarrow Y</math> || <math>Y-XY</math>|-| <math>X\leftrightarrow Y</math> || <math>1-X-Y+2XY</math>|-| <math>X\nleftrightarrow Y</math> || <math>X+Y-2XY</math>|}במקרה הזה נצטרך להכליל כמה הגדרות ולהגדיר כמה דברים חדשים. נרחיב את יחס השקילות <math>=</math> לתאר שיוויון של מספרים ממשיים בין 0 ל־1. אם תושב <math>X</math> מרגל נסמן <math>X=p</math> עבור קבוע <math>p\in(0,1)</math> כלשהו. האופרטורים <math>\neg,\and,\leftrightarrow,\dots</math> מוגדרים מחדש כמפורט בטבלה משמאל. לפי ההגדרות החדשות <math>X\and Y</math>, למשל, הוא ההסברות שהתושבים <math>X,Y</math> ידברו אמת בהנחה שהתושב <math>X</math> דובר אמת בהסברות <math>X</math> והתושב <math>Y</math> – בהסתברות <math>Y</math>. הגדרות אלה מכלילות את ההגדרות מאלגברה בוליאנית, אך יש כמה כללים שהאופרטורים כבר לא מקיימים. כללי דה־מורגן, למשל, נשמרים, בעוד שלא תמיד מתקיים <math>X\leftrightarrow Y=(X\rightarrow Y)\and(X\leftarrow Y)</math>. לבסוף, נגדיר אופרטור <math>\Leftrightarrow</math> ע״י <math>X\Leftrightarrow Y=\begin{cases}1,&X=Y\\0,&\text{else}\end{cases}</math> (בפרט, אם <math>X,Y</math> תושבים אז <math>X\Leftrightarrow Y</math> הוא הערך הבוליאני שמציין אם הם מאותו סוג. אם <math>X,Y</math> אינם מרגלים אז <math>X\Leftrightarrow Y=X\leftrightarrow Y</math>). :'''דוגמה 6:''' האורח נתקל בתושבים <math>A,B,C</math>. אחד מהם אביר, אחד נוכל ואחד מרגל. <math>A</math> טוען ש־<math>C</math> נוכל, ו־<math>B</math> טוען ש־<math>A</math> שיקר הרגע. לכן מתקיים:{{left|<math>\begin{array}{llcl}(1)&A\leftrightarrow B\leftrightarrow C&=&1-p\\(2)&A\leftrightarrow(C\Leftrightarrow0)&\neq&0\\(3)&B\leftrightarrow(C\nLeftrightarrow0)&\neq&0\end{array}</math>}}:נעיר שמשוואה (1) לא רק נגררת מהעובדה שיש אביר, נוכל ומרגל, אלא שקולה לה. הוכחה: אגף ימין שלה אינו 0 או 1 ולכן לפחות אחד מ־<math>A,B,C</math> מרגל. נניח בלי הגבלת הכלליות ש־<math>A</math> מרגל ולכן <math>p\leftrightarrow B\leftrightarrow C=1-p-(B\leftrightarrow C)+2p(B\leftrightarrow C)=1-p</math>, ומכך נקבל <math>(B\leftrightarrow C)(1-2p)=0</math>. זה צריך להתקיים לכל <math>p\in(0,1)</math> ולכן <math>B\leftrightarrow C=0</math>. ההסתברות ש־<math>B</math> אמר אמת אם״ם <math>C</math> אמר אמת תהא תמיד קטנה מ־1 אם לפחות אחד מהם מרגל. אם <math>B=0</math> אז <math>C=1</math> ואם <math>B=1</math> אז <math>C=0</math>, כלומר אכן יש אביר אחד, נוכל אחד ומרגל אחד.<!--{{left|<math>\begin{array}{llcl}(1)&A\leftrightarrow B\leftrightarrow C&=&1-p\\(2)&A\rightarrow(C\Leftrightarrow0)&=&1\\(3)&\neg A\rightarrow(C\nLeftrightarrow0)&=&1\\(4)&B\rightarrow(C\nLeftrightarrow0)&=&1\\(5)&\neg B\rightarrow(C\Leftrightarrow0)&=&1\end{array}</math>}}-->=== חידות ללא שאלות ===<!---->==== פתרון כמערכת משוואות ====<!---->==== פתרון באמצעות ניחוש ====פותרים כמו באותו אופן כמו במקרה שאין מרגלים, רק שבמקום לבדוק עד 2 סוגים בודקים עד 3. === חידות עם שאלות ===<!---->

== מקורות והשראות == המספר המינימלי של שאלות ===={{left|* [https:נניח ש־<math>m</math> הוא המספר המינימלי של שאלות הדרוש לפתרון חידת שאלות נתונה ונרצה להוכיח ש־<math>m=k=\lceil\log_2(|S|)\rceil</en.wikipedia.org/wiki/Knights_and_Knaves Knights and Knaves]* [httpsmath>:תהי <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</wiki/The_Hardest_Logic_Puzzle_Ever The Hardest Logic Puzzle Ever]* [httpsmath> ובפרט קיימת פונקציה <math>f:S\to V<//enmath> חח״ע.wikipedia.orgתהי <math>\mathbf Q\in\{0,1\}^{k\times n}</wikimath> מטריצה כך ש־<math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}</Fuzzy_logic Fuzzy logic]* [httpsmath> הפיכה ואז <math>\mathbf q':\mathbf v\mapsto\mathbf Q\mathbf v</math> חח״ע מ־<math>V</enmath>.wikipedia.orgנגדיר <math>\mathbf q=f^{-1}\circ\mathbf q'\circ f</wikimath> ולכן <math>\mathbf q</Many-valued_logic Many-valued logic]* [https:math> חח״ע מ־<math>S</math> והיא מורכבת מ־<math>k</en.wikipediamath> שאלות, כלומר <math>k\ge m</math>.orgבעבר הוכחנו ש־<math>k\le m</wikimath> ולכן <math>m=k</Three-valued_logic Three-valued logic]math>. {{משל}}<!-- סיבוכיות? -->