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

גרסה מ־16:10, 28 ביוני 2013

תוכן עניינים

1 הבעיה
2 סימונים והגדרות
- 2.1 דוגמה
3 חידות ללא מרגלים
- 3.1 חידות לינאריות
4 מקורות והשראות

הבעיה

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

דוגמה 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$ הפיכה.

@@ שורה 39: / שורה 39: @@
 הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (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> הפיכה.
-== ראו גם ==
+== מקורות והשראות ==
-* [http://en.wikipedia.org/wiki/Knights_and_Knaves Knights and Knaves] בוויקיפדיה האנגלית.
+{{left|
-* [http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever The Hardest Logic Puzzle Ever] בוויקיפדיה האנגלית.
+* [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]
+}}

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

גרסה מ־16:10, 28 ביוני 2013

תוכן עניינים

הבעיה

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

דוגמה

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

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

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

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים