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

גרסה מ־16:26, 15 ביוני 2013

תוכן עניינים

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

הבעיה

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

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

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

סימונים

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

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

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

באופן שקול:

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

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

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

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

טבלה 1
$x$	$y$	$\varphi(x+y)$	$\varphi(x)\leftrightarrow\varphi(y)$
0	0	T	T
0	1	F	F
1	0	F	F
1	1	T	T

טבלה 2
$x$	$y$	$\varphi(x\cdot y)$	$\varphi(x)\or\varphi(y)$
0	0	T	T
0	1	T	T
1	0	T	T
1	1	F	F

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

חח״ע ועל – טריוויאליים.
$\varphi(x+y)\Leftrightarrow\varphi(x)\leftrightarrow\varphi(y)$ : טבלה 1.
$\varphi(x\cdot y)\Leftrightarrow\varphi(x)\or\varphi(y)$ : טבלה 2.

מכך נובע ש־ $\{\mathrm T,\mathrm F\}$ שדה. נגדיר סכום $\sum_{i=1}^m P_i$ (כאשר $\forall i:\ P_i\in\{\mathrm T,\mathrm F\}$ ) בתור $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$ או קבוע $\mathrm T,\mathrm F$ אז נוכל להציג כל שרשור $P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1}$ בתור סכום של נעלמים שונים השווה לקבוע. לדוגמה, $B\leftrightarrow A\leftrightarrow\mathrm F\Leftrightarrow\mathrm T$ מפתרון דוגמה 1 שקול ל־ $A\leftrightarrow B\Leftrightarrow\mathrm F$ , ששקול ל־ $\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow\mathrm F$ . ביטוי זה ניתן להציג גם כ־ $\begin{pmatrix}\mathrm T&\mathrm T&\mathrm F&\mathrm F\end{pmatrix}\mathbf x\Leftrightarrow\mathrm F$ , ולכן נוכל להגדיר מטריצת מקדמים $\mathbf A$ ווקטור מקדמים חופשיים $\mathbf b$ כך ש־ $\mathbf{Ax}\Leftrightarrow\mathbf b$ . למשל, את דוגמה 1 ניתן להציג באופן הבא:

\begin{pmatrix}\mathrm T&\mathrm T&\mathrm T&\mathrm F\\\mathrm T&\mathrm T&\mathrm F&\mathrm F\\\mathrm F&\mathrm F&\mathrm F&\mathrm T\\\mathrm T&\mathrm F&\mathrm T&\mathrm F\end{pmatrix}\begin{pmatrix}A\\B\\C\\D\end{pmatrix}\Leftrightarrow\begin{pmatrix}\mathrm T\\\mathrm F\\\mathrm T\\\mathrm F\end{pmatrix}

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