משתמש:אור שחף/עבודה ב"שימושי המתמטיקה ביומיום"

הבעיה

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

• דוגמה 1: האורח נתקל בתושבים $A,B,C,D$. אין מרגלים, וידוע ש־$A,C$ מסוגים שונים. $A$ טוען ש־$B,C$ מאותו סוג, $B$ טוען ש־$A$ נוכל ו־$C$ טוען ש־$D$ מאותו סוג כמוהו (כמו $C$). יש למצוא את הסוג של כל תושב.
• דוגמה 2: האורח נתקל בשלושה תושבים. אחד מהם אביר, אחד נוכל ואחד מרגל. אילו 3 שאלות של כן/לא הוא יכול לשאול על מנת לגלות את הסוג של כל אחד מהם?

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

סימונים והגדרות

באלגברה בוליאנית מסמנים $1$ כפסוק אמת ו־$0$ כפסוק שקר. באופן דומה, אם תושב $A$ הוא אביר אז נסמנו כ־$1$ ואם נוכל – $0$. אם הוא מרגל נסמן $p$. אם תושב $B$ יכול להיות מרגל אז נסמן את נכונות הטענה ה־$i$ במספר שלו כ־$b_i$. כלומר, אם הטענה נכונה אז $b_i\Leftrightarrow1$ ואחרת $b_i\Leftrightarrow0$. מכך נובע שאם הטענה ה־$i$ של $B$ היא $P$ אז $b_i\Leftrightarrow P$, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול $b_i\leftrightarrow P\Leftrightarrow1$. מובן שאם $B$ אביר או נוכל אז $\forall i:\ b_i\Leftrightarrow B$, ולכן אם אנו כבר יודעים שתושב $B$ אינו מרגל אז נסמן את טענותיו פשוט כ־$B$.

דוגמה

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

$\begin{array}{llcl} (1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\ (2)&B\leftrightarrow A\leftrightarrow0&\Leftrightarrow&1\\ (3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&1\\ (4)&A\leftrightarrow C&\Leftrightarrow&0\end{array}$

באופן שקול:

$\begin{array}{llcl} (1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\ (2)&A\leftrightarrow B&\Leftrightarrow&0\\ (3)&D&\Leftrightarrow&1\\ (4)&A\leftrightarrow C&\Leftrightarrow&0\end{array}$

עתה נציב את (2) ב־(1) ונקבל $0\leftrightarrow C\Leftrightarrow1$, כלומר $C\Leftrightarrow0$. נציב זאת ב־(4) ונקבל $A\Leftrightarrow1$, ואם נציב את התוצאה ב־(2) נקבל $B\Leftrightarrow0$. לסיכום, $A,D$ אבירים ו־$B,C$ נוכלים.

חידות ללא מרגלים

חידות לינאריות

אלו חידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה $(\mathbb Z_2,+,\cdot)$ ל־$(\{1,0\},\leftrightarrow,\or)$ ע״י $\neg:x\mapsto\begin{cases}1,&x=0\\0,&x=1\end{cases}$. נראה שזהו אכן איזומורפיזם:

• חח״ע ועל – טריוויאליים.
• $\neg(x+y)\Leftrightarrow\neg(x\nleftrightarrow y)\Leftrightarrow x\leftrightarrow y\Leftrightarrow\neg x\leftrightarrow\neg y$
• $\neg(x\cdot y)\Leftrightarrow\neg(x\and y)\Leftrightarrow\neg x\or\neg y$

מכך נובע ש־$(\{1,0\},\leftrightarrow,\or)$ שדה. נגדיר סכום $\sum_{i=1}^m P_i$ (כאשר $\forall i:\ P_i\in\{1,0\}$) בתור $P_1\leftrightarrow\dots\leftrightarrow P_m$ ומכפלה $\prod_{i=1}^m P_i$ בתור $P_1\or\dots\or P_m$. כפל מטריצות מוגדר בהתאם.

כעת, אם התושבים הם $X_1,\dots,X_n$ אז נגדיר $\mathbf x:=\begin{pmatrix}X_1\\\vdots\\X_n\end{pmatrix}$. אם כל $P_i$ מייצג נעלם $X_j$ או קבוע $1,0$ אז נוכל להציג כל $P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1}$ בתור סכום של נעלמים שונים השווה לקבוע (לדוגמה, $B\leftrightarrow A\leftrightarrow0\Leftrightarrow1$ מפתרון דוגמה 1 שקול ל־$A\leftrightarrow B\Leftrightarrow0$, ששקול ל־$\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow0$). לכן נוכל להגדיר מטריצת מקדמים $\mathbf A$ ווקטור מקדמים חופשיים $\mathbf b$ כך ש־$\mathbf{Ax}\Leftrightarrow\mathbf b$. למשל, את דוגמה 1 ניתן להציג באופן הבא:

$\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$

הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (Rouché–Capelli) יש פתרון ל־$\mathbf{Ax}=\mathbf b$ אם״ם $\mathbf b\in\operatorname{span}\left\{\operatorname{Col}_i(\mathbf A)\right\}_{i=1}^n$ כאשר $\operatorname{Col}_i(\mathbf A)$ העמודה ה־$i$ של $\mathbf A$, ואם כן אז מרחב הפתרונות הוא ממימד $n-\operatorname{rank}(\mathbf A)$. מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן אז לחשב את מספר הפתרונות בתור $2^{n-\operatorname{rank}(\mathbf A)}$. מובן שבד״כ יש רק פתרון אחד, כלומר $\mathbf A$ הפיכה.

מקורות והשראות

• Knights and Knaves
• The Hardest Logic Puzzle Ever
• Fuzzy logic
• Many-valued logic
• Three-valued logic