שינויים

באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל – לרוב את הסוג של כמה מהתושבים) – על סמך טענות שהתושבים טענו כמה עובדות (שמרביתן מהצורה "תושב <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> שהוא מאותו סוג כמוהו (כמו <math>CD</math>). יש למצוא את מה הסוג של כל תושב.?

== סימונים והגדרות חידות ללא מרגלים =={| class="wikitable" style="direction:ltr; float:left; margin-top: 0;"! <math>P</math> !! <math>Q</math> !! <math>P\leftrightarrow Q</math>|-| 0 || 0 || 1|-| 0 || 1 || 0|-| 1 || 0 || 0|-| 1 || 1 || 1|}באלגברה בוליאנית מסמנים <math>1</math> כפסוק אמת ו־<math>0</math> כפסוק שקר. באופן דומה, אם תושב <math>AX</math> הוא אביר אז נסמנו כ־<math>1</math> ואם נוכל – <math>0</math>. אם הוא מרגל נסמן נעזר בסימון <math>p\leftrightarrow</math>לציון אופרטור שקילות לוגית, המוגדר כמפורט בטבלה שמשמאל. אם תושב <math>B\Leftrightarrow</math> יכול להיות מרגל אז נסמן את נכונות הטענה ה־<math>i</math> במספר שלו כ־<math>b_i</math>. הוא יחס שקילות בין כל שני פסוקים שקולים לוגית, כלומר, אם הטענה נכונה אז ידוע ש־<math>b_iP\Leftrightarrow1leftrightarrow Q</math> ואחרת נותן 1 אז נוכל לסמן <math>b_iP\Leftrightarrow0Leftrightarrow Q</math>. מכך נובע שאם הטענה ה־לפיכך, אם <math>iX</math> של <math>B</math> היא טוען ש־<math>P</math> אז <math>b_iX\Leftrightarrow P</math>, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול <math>b_i\leftrightarrow P\Leftrightarrow1</math>. מובן שאם <math>B</math> אביר או נוכל אז <math>\forall i:\ b_i\Leftrightarrow B</math>, ולכן אם אנו כבר יודעים שתושב <math>B</math> אינו מרגל אז נסמן את טענותיו פשוט כ־<math>B</math>.

=== '''דוגמה ===1.1:''' באמצעות סימונים אלו נפתור נציג את ''דוגמה 1 '' כמערכת משוואות פשוטהבוליאניות. <math>A</math> טוען ש־<math>B,C</math> מאותו סוג, כלומר הוא טוען <math>B\leftrightarrow C</math>. מכך נובעת משוואה (1) במערכת המשוואות הבאה. מהטענות של <math>B,C</math> נובעות המשוואות (2) ו־(3), ומהעובדה ש־<math>A,C</math> שונים נובעת משוואה (4):

(2)&B\leftrightarrow A\leftrightarrow0leftrightarrow1&\Leftrightarrow&1\\

(1)&A\leftrightarrow nleftrightarrow B\leftrightarrow nleftrightarrow C&\Leftrightarrow&1\\(2)&A\leftrightarrow nleftrightarrow B&\Leftrightarrow&0\\

(4)&A\leftrightarrow nleftrightarrow C&\Leftrightarrow&01\end{array}</math>}}עתה נציב את (2) ב־(1) ונקבל <math>0\leftrightarrow C\Leftrightarrow1</math>, כלומר <math>C\Leftrightarrow0</math>. נציב זאת ב־(4) ונקבל <math>A\Leftrightarrow1</math>, ואם נציב את התוצאה ב־(2) נקבל <math>B\Leftrightarrow0</math>. לסיכום, <math>A,D</math> אבירים ו־<math>B,C</math> נוכלים.

=== חידות ללא מרגלים שאלות ====== חידות לינאריות = פתרון כמערכת משוואות ====אלו חידות ברגע שיש לנו ניסוח מתמטי של החידה כמערכת משוואות קל לפתור אותה. אנו נתעמק בחידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2כיוון שהן נותנות מידע רב יותר על החידה,+,\cdot)</math> ל־<math>(\{1,0\},\leftrightarrow,\or)</math> ע״י <math>\neg:x\mapsto\begin{cases}1,&x=0\\0,&x=1\end{cases}</math>כפי שנראה בהמשך. נראה שזהו אכן איזומורפיזם:* חח״ע ועל – טריוויאליים.* <math>\neg(x+y)\Leftrightarrow\neg(x\nleftrightarrow y)\Leftrightarrow x\leftrightarrow y\Leftrightarrow\neg x\leftrightarrow\neg y</math>* <math>\neg(x\cdot y)\Leftrightarrow\neg(x\and y)\Leftrightarrow\neg x\or\neg y</math>

ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2,+,\cdot)</math> ל־<math>(\{0,1\},\nleftrightarrow,\and)</math> ע״י <math>x\mapsto\begin{cases}0,&x=[0]_2\\1,&x=[1]_2\end{cases}</math>. מכך נובע ש־<math>(\{1,0,1\},\leftrightarrownleftrightarrow,\orand)</math> שדה. נגדיר סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{1,0\}</math>) יוגדר בתור <math>P_1\leftrightarrownleftrightarrow\dots\leftrightarrow nleftrightarrow P_m</math> ומכפלה <math>\prod_{i=1}^m P_i</math> בתור <math>P_1\orand\dots\or and P_m</math>. גם כפל מטריצות מוגדר בהתאם.

כעת, אם התושבים הם <math>X_1,\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\leftrightarrownleftrightarrow\dots\leftrightarrow nleftrightarrow P_n\Leftrightarrow P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע (: לדוגמה, <math>B\leftrightarrow A\leftrightarrow0\Leftrightarrow1</math> מפתרון מהניסוח המתמטי של ''דוגמה 1 '' שקול ל־<math>A\leftrightarrow nleftrightarrow B\Leftrightarrow0Leftrightarrow1</math>, ששקול כלומר ל־<math>\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow0Leftrightarrow1</math>). לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}\Leftrightarrow\mathbf b</math>. למשל, את דוגמה 1 ניתן להציג באופן הבא:{{left|<math>\underbrace\begin{pmatrix}0&0&0&1\\0&0&1&1\\1&1&1&0\\0&1&0&1\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x\Leftrightarrow\underbrace\begin{pmatrix}1\\0\\1\\0\end{pmatrix}_\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\Leftrightarrow\underbrace\begin{pmatrix}1\\0\\1\\1\end{pmatrix}_\mathbf b</math>}} הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (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>\mathbf A</math> הפיכה. '''דוגמה 1.3:''' נפתור את ''דוגמה 1''. חישוב פשוט מראה ש־<math>\mathbf A</math> הפיכה (ומכאן שיש פתרון יחיד) ו־<math>\mathbf A^{-1}\Leftrightarrow\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math>. לכן <math>\mathbf x\Leftrightarrow\mathbf A^{-1}\mathbf b\Leftrightarrow\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\leftrightarrow(\neg B\and C)\Leftrightarrow1</math>. אם ננחש ש־<math>A</math> אביר נקבל פתרון יחיד, אך אם ננחש שהוא נוכל נקבל ש־<math>\neg B\and C\Leftrightarrow0</math>. במקרה הזה אפשר לנחש ש־<math>B</math> נוכל (ולקבל פתרון יחיד) או אביר (ולקבל שני פתרונות). מספר הפתרונות הוא אם כן <math>\underbrace1_{A\text{ is a knight}}+\underbrace{\underbrace1_{B\text{ is a knave}}+\underbrace2_{B\text{ is a knight}}}_{A\text{ is a knave}}=4</math>. זו מערכת לא לינארית ולכן לא ניתן לפתור אותה בשיטה של רושה–קפלי. חיסרון מהותי יותר הוא ששינוי של <math>\mathbf b</math> דורש פתרון מחדש של הבעיה כולה. <!---->כמו כן, הפתרון לא נותן לנו את התובנות שקיבלנו מפתרון כמערכת משוואות לינאריות, תובנות שיעזרו לנו בחידות שבהן שואלים שאלות. <!----> === חידות עם שאלות ===במקרה שאין מרגלים ואין עובדות החידות האלה טריוויאליות – ניתן לשאול כל תושב "האם 1=1?" (או כל שאלה אחרת שהתשובה לה ידועה) ולהסיק את סוגו. זאת כמובן כאשר מספר השאלות שמותר לשאול הוא לכל הפחות מספר התושבים, מה שחייב להתקיים אם החידה פתירה: אם יש <math>n</math> תושבים אז יש <math>2^n</math> אפשרויות לחלוקת הסוגים שלהם. <!----> == חידות עם מרגלים ==<!---->=== חידות ללא שאלות ===<!---->==== פתרון כמערכת משוואות ====<!---->==== פתרון באמצעות ניחוש ====<!---->=== חידות עם שאלות ===<!---->