שינויים

באי ב[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 שאלות של כן/לא הוא יכול האורח לשאול את התושבים על מנת לגלות להסיק את הסוג של כל אחד מהם, אם מותר לו להחליט למי להפנות כל שאלה על סמך התשובות לשאלות ששאל לפניההסוגים שלהם?

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

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

הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (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>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>) כך שהיא תהיה הפיכה.

:'''דוגמה 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}}+\underbrace{\underbrace1_overbrace1^{B\text{ is a knave}}+\underbrace2_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\or 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 pq=\begin{pmatrix}P_1Q_1\\\vdots\\P_mQ_m\end{pmatrix}</math> כווקטור השאלות. ''תשובה'' תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־<math>\mathbf br=\begin{pmatrix}b_1r_1\\\vdots\\b_mr_m\end{pmatrix}</math> את וקטור התשובות. מההגדרות נובע ישירות ש־<math>\mathbf pq=\mathbf br</math>. <math>\mathbf x</math> מוגדר כמקודם, ואז ניתן לחשוב על <math>\mathbf q</math> כעל פונקציה <math>\mathbf x\mapsto\mathbf r</math>.

:'''דוגמה 42.1:''' יש 3 תושבים (<math>m=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 pq=\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\end{pmatrix}</math> , לדוגמה, מאפשר לפתור את החידה. אם נניח, למשל, ש־כי תמיד מתקיים <math>\mathbf bx=\begin{pmatrix}0r_2\\1r_1\end{pmatrix}</math> אזי <math>leftrightarrow r_2\mathbf x=\begin{pmatrix}1r_2\or (r_1\0leftrightarrow r_2)\end{pmatrix}</math>, ובאופן כללי <math>\mathbf x=\begin{pmatrix}b_2r_2\\b_1r_1\leftrightarrow b_2r_2\\r_1\rightarrow r_2\end{pmatrix}</math>.

<!--נוכיח שאם לא בחידות מסוג זה נתונות עובדות אז , ונסמן כ־<math>S</math> את קבוצת הפתרונות <math>n\le mmathbf x</math>: החידה פתירה, כלומר קיים וקטור המקיימים אותן. בד״כ המטרה היא למצוא <math>\mathbf pq</math> כנ״ל כך שלכל חח״ע מ־<math>S</math>, כלומר למצוא שאלות שעבורן לכל וקטור תשובות <math>\mathbf r=\mathbf q(\mathbf bx)</math> ניתן יהיה להסיק את הפתרוןוקטור הסוגים של התושבים, <math>\mathbf x=\mathbf q^{-1}(\mathbf r)</math>. מספר האפשרויות ל

ושניתן להסתפק ==== מערכת עובדות לינאריות ====במקרה זה <math>S=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf b\}</math>. אם שורות המטריצה <math>\mathbf A</math> תלויות לינארית ניתן למחוק כמה מהן (וגם את השורות המתאימות ב־<math>n\mathbf b</math>) כך ששורותיה יהיו בת״ל ו־<math>S</math> לא תשתנה. לכן נניח בה״כ ששורות <math>\mathbf A</math> שאלותבת״ל.

במקרה שאין מרגלים ואין עובדות החידות האלה טריוויאליות – ניתן לשאול כל תושב "האם 1=1?" (או כל שאלה אחרת שהתשובה לה ידועה) ולהסיק את סוגו:'''דוגמה 4. זאת כמובן כאשר מספר השאלות שמותר לשאול הוא לכל הפחות מספר התושבים, מה שחייב להתקיים אם החידה פתירה1: נניח שיש ''' <math>n=4</math> תושבים ו־ונתון{{left|<math>m</math> שאלות וצ״ל ש־<math>n\le mbegin{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>2^n\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}(\mathbf A)}=2^k</math> ולכן <math>n\operatorname{rank}(\mathbf A)=1=mn-k</math>, כדרוש. עתה נניח ש־השורות של <math>n\le mmathbf A</math> ל־בת״ל ולכן יש לה <math>m,n-k</math> כלשהם ונוכיח שאם חידה עם <math>n+1</math> ו־שורות.

:'''דוגמה 54.2:''' עלינו למצוא את הסוגים של כל התושבים בדוגמה 4 במינימום שאלות, כלומר ב־<math>k=n-\operatorname{rank}(\mathbf A)=5,m=32</math> וידוע שאלות (הוכחה ש־<math>k</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\or X_2nleftrightarrow 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 Xm</math> || הוא המספר המינימלי של שאלות הדרוש לפתרון חידת שאלות נתונה ונרצה להוכיח ש־<math>1-X</math>|-| <math>Xm=k=\and Y</math> || <math>XY</math>|-| <math>Xlceil\uparrow Y</math> log_2(|S| <math>1-XY</math>|-| <math>X)\or Yrceil</math> || : תהי <math>X+Y-XY</math>|-| <math>XV=\downarrow Y</math> || <math>1-X-Y+XY</math>|-| <math>X{\rightarrow Y</math> || <math>1-X+XY</math>|-| <math>Xmathbf x:\nrightarrow Y</math> || <math>X-XY</math>|-| <math>X\leftarrow Y</math> || <math>1-Y+XY</math>|-| <math>Xmathbf A\nleftarrow Y</math> || <math>Y-XY</math>|-| <math>Xmathbf x=\leftrightarrow Y</math> || <math>1-X-Y+2XY</math>|-| <math>Xmathbf 0\nleftrightarrow Y</math> || <math>X+Y-2XY</math>|}במקרה הזה נצטרך להכליל כמה הגדרות ולהגדיר כמה דברים חדשים. נרחיב את יחס השקילות <math>=</math> לתאר שיוויון של מספרים ממשיים בין 0 ל־1. אם תושב כך ש־<math>X</math> מרגל נסמן <math>X=p</math> עבור קבוע <math>p\mathbf A\in(\{0,1\}^{(n-k)</math> כלשהו. האופרטורים <math>\neg,\and,\leftrightarrow,\dotstimes n}</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|V|=(X\rightarrow Y)2^{n-\andoperatorname{rank}(X\leftarrow Ymathbf A)}=2^k</math>. לבסוף, נגדיר אופרטור ובפרט קיימת פונקציה <math>f:S\equivto V</math> ע״י חח״ע. תהי <math>X\equiv Y=mathbf Q\in\begin{cases}1,&X=Y\\0,&1\text}^{else}k\end{casestimes n}</math> (בפרט, אם <math>X,Y</math> תושבים אז <math>X\equiv Y</math> הוא הערך הבוליאני שמציין אם הם מאותו סוג. אם <math>X,Y</math> אינם מרגלים אז <math>X\equiv 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{arraypmatrix}{llcl}(1)&A\leftrightarrow B\leftrightarrow C&=&1-p\\(2)&mathbf A\leftrightarrow(C\equiv0)&\neq&0\\(3)&B\leftrightarrow(C\not\equiv0)&\neq&0mathbf Q\end{arraypmatrix}</math>}}:נעיר שמשוואה (1) לא רק נגררת מהעובדה שיש אביר, נוכל ומרגל, אלא שקולה לה. הוכחה: אגף ימין שלה אינו 0 או 1 ולכן לפחות אחד מ־הפיכה ואז <math>A,B,C</math> מרגל. נניח בלי הגבלת הכלליות ש־<math>A</math> מרגל ולכן <math>p\leftrightarrow Bmathbf q':\leftrightarrow C=1-p-(Bmathbf v\leftrightarrow C)+2p(Bmapsto\leftrightarrow C)=1-pmathbf Q\mathbf v</math>, ומכך נקבל חח״ע מ־<math>(B\leftrightarrow C)(1-2p)=0V</math>. זה צריך להתקיים לכל נגדיר <math>p\in(0,1)mathbf q=\mathbf q'\circ f</math> ולכן <math>B\leftrightarrow C=0mathbf q</math>, דהיינו חח״ע מ־<math>B+C-2BC=1S</math>. חישוב באמצעות נגזרות יראה שלאגף שמאל יש נקודה קריטית אחת ב־והיא מורכבת מ־<math>B=C=1/2k</math>שאלות, ואז כלומר <math>B+C-2BC=1/2k\ne1ge m</math>. לכן היא מינימום והפתרון <math>(B,C)</math> נמצא על שפת <math>[0,1]^2</math>. נניח בלי הגבלת הכלליות בעבר הוכחנו ש־<math>B=0,1k\le m</math> ונקבל ולכן <math>Cm=1,0k</math> בהתאמה, כלומר אכן יש אביר אחד, נוכל אחד ומרגל אחד. === חידות ללא שאלות ===<!---->==== פתרון כמערכת משוואות ====<!---->==== פתרון באמצעות ניחוש ====<!---->=== חידות עם שאלות ===<!----> == מקורות והשראות =={{left|* [https://en.wikipedia.org/wiki/Knights_and_Knaves Knights and Knaves]* [https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever The Hardest Logic Puzzle Ever]* [https://en.wikipedia.org/wiki/Fuzzy_logic Fuzzy logic]* [https://en.wikipedia.org/wiki/Many-valued_logic Many-valued logic]* [https://en.wikipedia.org/wiki/Three-valued_logic Three-valued logic]משל}}<!-- סיבוכיות? -->