משתמש:אור שחף/עבודה ב"שימושי המתמטיקה ביומיום"
הבעיה
באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל את הסוג של כמה מהתושבים) על סמך טענות שהתושבים טענו או על סמך שאלות כן/לא שעליו לשאול, ולפעמים גם על סמך כמה עובדות שידועות לו.
- דוגמה 1: האורח נתקל בתושבים [math]\displaystyle{ A,B,C,D }[/math]. אין מרגלים, וידוע ש־[math]\displaystyle{ A,C }[/math] מסוגים שונים. [math]\displaystyle{ A }[/math] טוען ש־[math]\displaystyle{ B,C }[/math] מאותו סוג, [math]\displaystyle{ B }[/math] טוען ש־[math]\displaystyle{ A }[/math] נוכל ו־[math]\displaystyle{ C }[/math] טוען ש־[math]\displaystyle{ D }[/math] מאותו סוג כמוהו (כמו [math]\displaystyle{ C }[/math]). יש למצוא את הסוג של כל תושב.
- דוגמה 2: האורח נתקל בשלושה תושבים. אחד מהם אביר, אחד נוכל ואחד מרגל. אילו 3 שאלות של כן/לא הוא יכול לשאול על מנת לגלות את הסוג של כל אחד מהם?
נרצה ליצור מודל מתמטי לפתרון בעיות מסוג זה.
סימונים והגדרות
באלגברה בוליאנית מסמנים [math]\displaystyle{ \mathrm T }[/math] כפסוק אמת ו־[math]\displaystyle{ \mathrm F }[/math] כפסוק שקר. באופן דומה, אם תושב [math]\displaystyle{ A }[/math] הוא אביר אז נסמנו כ־[math]\displaystyle{ \mathrm T }[/math] ואם נוכל – [math]\displaystyle{ \mathrm F }[/math]. אם הוא מרגל נסמן [math]\displaystyle{ \mathrm S }[/math]. אם תושב [math]\displaystyle{ B }[/math] יכול להיות מרגל אז נסמן את נכונות הטענה ה־[math]\displaystyle{ i }[/math] במספר שלו כ־[math]\displaystyle{ b_i }[/math]. כלומר, אם הטענה נכונה אז [math]\displaystyle{ b_i\Leftrightarrow\mathrm T }[/math] ואחרת [math]\displaystyle{ b_i\Leftrightarrow\mathrm F }[/math]. מכך נובע שאם הטענה ה־[math]\displaystyle{ i }[/math] של [math]\displaystyle{ B }[/math] היא [math]\displaystyle{ P }[/math] אז [math]\displaystyle{ b_i\Leftrightarrow P }[/math], ומסיבות שיובנו בהמשך נעדיף את הסימון השקול [math]\displaystyle{ b_i\leftrightarrow P\Leftrightarrow\mathrm T }[/math]. מובן שאם [math]\displaystyle{ B }[/math] אביר או נוכל אז [math]\displaystyle{ \forall i:\ b_i\Leftrightarrow B }[/math], ולכן אם אנו כבר יודעים שתושב [math]\displaystyle{ B }[/math] אינו מרגל אז נסמן את טענותיו פשוט כ־[math]\displaystyle{ B }[/math].
דוגמה
באמצעות סימונים אלו נפתור את דוגמה 1 כמערכת משוואות פשוטה. [math]\displaystyle{ A }[/math] טוען ש־[math]\displaystyle{ B,C }[/math] מאותו סוג, כלומר הוא טוען [math]\displaystyle{ B\leftrightarrow C }[/math]. מכך נובעת משוואה (1) במערכת המשוואות הבאה. מהטענות של [math]\displaystyle{ B,C }[/math] נובעות המשוואות (2) ו־(3), ומהעובדה ש־[math]\displaystyle{ A,C }[/math] שונים נובעת משוואה (4):
באופן שקול:
עתה נציב את (2) ב־(1) ונקבל [math]\displaystyle{ \mathrm F\leftrightarrow C\Leftrightarrow\mathrm T }[/math], כלומר [math]\displaystyle{ C\Leftrightarrow\mathrm F }[/math]. נציב זאת ב־(4) ונקבל [math]\displaystyle{ A\Leftrightarrow\mathrm T }[/math], ואם נציב את התוצאה ב־(2) נקבל [math]\displaystyle{ B\Leftrightarrow\mathrm F }[/math]. לסיכום, [math]\displaystyle{ A,D }[/math] אבירים ו־[math]\displaystyle{ B,C }[/math] נוכלים.
חידות ללא מרגלים
חידות לינאריות
| [math]\displaystyle{ x }[/math] | [math]\displaystyle{ y }[/math] | [math]\displaystyle{ \varphi(x+y) }[/math] | [math]\displaystyle{ \varphi(x)\leftrightarrow\varphi(y) }[/math] |
|---|---|---|---|
| 0 | 0 | T | T |
| 0 | 1 | F | F |
| 1 | 0 | F | F |
| 1 | 1 | T | T |
| [math]\displaystyle{ x }[/math] | [math]\displaystyle{ y }[/math] | [math]\displaystyle{ \varphi(x\cdot y) }[/math] | [math]\displaystyle{ \varphi(x)\or\varphi(y) }[/math] |
|---|---|---|---|
| 0 | 0 | T | T |
| 0 | 1 | T | T |
| 1 | 0 | T | T |
| 1 | 1 | F | F |
אלו חידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה [math]\displaystyle{ (\mathbb Z_2,+,\cdot) }[/math] ל־[math]\displaystyle{ (\{\mathrm T,\mathrm F\},\leftrightarrow,\or) }[/math] ע״י [math]\displaystyle{ \varphi:x\mapsto\begin{cases}\mathrm T,&x=0\\\mathrm F,&x=1\end{cases} }[/math]. נראה שזהו אכן איזומורפיזם:
- חח״ע ועל – טריוויאליים.
- [math]\displaystyle{ \varphi(x+y)\Leftrightarrow\varphi(x)\leftrightarrow\varphi(y) }[/math]: טבלה 1.
- [math]\displaystyle{ \varphi(x\cdot y)\Leftrightarrow\varphi(x)\or\varphi(y) }[/math]: טבלה 2.
מכך נובע ש־[math]\displaystyle{ \{\mathrm T,\mathrm F\} }[/math] שדה. נגדיר סכום [math]\displaystyle{ \sum_{i=1}^m P_i }[/math] (כאשר [math]\displaystyle{ \forall i:\ P_i\in\{\mathrm T,\mathrm F\} }[/math]) בתור [math]\displaystyle{ P_1\leftrightarrow\dots\leftrightarrow P_m }[/math] ומכפלה [math]\displaystyle{ \prod_{i=1}^m P_i }[/math] בתור [math]\displaystyle{ P_1\or\dots\or P_m }[/math]. כפל מטריצות מוגדר בהתאם.
כעת, אם התושבים הם [math]\displaystyle{ X_1,\dots,X_n }[/math] אז נגדיר [math]\displaystyle{ \mathbf x:=\begin{pmatrix}X_1\\\vdots\\X_n\end{pmatrix} }[/math]. אם כל [math]\displaystyle{ P_i }[/math] מייצג נעלם [math]\displaystyle{ X_j }[/math] או קבוע [math]\displaystyle{ \mathrm T,\mathrm F }[/math] אז נוכל להציג כל שרשור [math]\displaystyle{ P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1} }[/math] בתור סכום של נעלמים שונים השווה לקבוע. לדוגמה, [math]\displaystyle{ B\leftrightarrow A\leftrightarrow\mathrm F\Leftrightarrow\mathrm T }[/math] מפתרון דוגמה 1 שקול ל־[math]\displaystyle{ A\leftrightarrow B\Leftrightarrow\mathrm F }[/math], ששקול ל־[math]\displaystyle{ \sum_{X_i\in\{A,B\}}X_i\Leftrightarrow\mathrm F }[/math]. לכן נוכל להגדיר מטריצת מקדמים [math]\displaystyle{ \mathbf A }[/math] ווקטור מקדמים חופשיים [math]\displaystyle{ \mathbf b }[/math] כך ש־[math]\displaystyle{ \mathbf{Ax}\Leftrightarrow\mathbf b }[/math]. למשל, את דוגמה 1 ניתן להציג באופן הבא:
הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (Rouché–Capelli) יש פתרון ל־[math]\displaystyle{ \mathbf{Ax}=\mathbf b }[/math] אם״ם [math]\displaystyle{ \mathbf b\in\operatorname{span}\left\{\operatorname{Col}_i(\mathbf A)\right\}_{i=1}^n }[/math] כאשר [math]\displaystyle{ \operatorname{Col}_i(\mathbf A) }[/math] העמודה ה־[math]\displaystyle{ i }[/math] של [math]\displaystyle{ \mathbf A }[/math], ואם כן אז מרחב הפתרונות הוא ממימד [math]\displaystyle{ n-\operatorname{rank}(\mathbf A) }[/math]. מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן אז כמה פתרונות יש. מובן שבד״כ יש רק פתרון אחד, כלומר [math]\displaystyle{ \mathbf A }[/math] הפיכה.
ראו גם
- Knights and Knaves בוויקיפדיה האנגלית.
- The Hardest Logic Puzzle Ever בוויקיפדיה האנגלית.