משתמש:אור שחף/עבודה ב"שימושי המתמטיקה ביומיום"
הבעיה
באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל את הסוג של כמה מהתושבים) על סמך טענות שהתושבים טענו או על סמך שאלות כן/לא שעליו לשאול, ולפעמים גם על סמך כמה עובדות שידועות לו.
- דוגמה 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{ 1 }[/math] כפסוק אמת ו־[math]\displaystyle{ 0 }[/math] כפסוק שקר. באופן דומה, אם תושב [math]\displaystyle{ A }[/math] הוא אביר אז נסמנו כ־[math]\displaystyle{ 1 }[/math] ואם נוכל – [math]\displaystyle{ 0 }[/math]. אם הוא מרגל נסמן [math]\displaystyle{ p }[/math]. אם תושב [math]\displaystyle{ B }[/math] יכול להיות מרגל אז נסמן את נכונות הטענה ה־[math]\displaystyle{ i }[/math] במספר שלו כ־[math]\displaystyle{ b_i }[/math]. כלומר, אם הטענה נכונה אז [math]\displaystyle{ b_i\Leftrightarrow1 }[/math] ואחרת [math]\displaystyle{ b_i\Leftrightarrow0 }[/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\Leftrightarrow1 }[/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{ 0\leftrightarrow C\Leftrightarrow1 }[/math], כלומר [math]\displaystyle{ C\Leftrightarrow0 }[/math]. נציב זאת ב־(4) ונקבל [math]\displaystyle{ A\Leftrightarrow1 }[/math], ואם נציב את התוצאה ב־(2) נקבל [math]\displaystyle{ B\Leftrightarrow0 }[/math]. לסיכום, [math]\displaystyle{ A,D }[/math] אבירים ו־[math]\displaystyle{ B,C }[/math] נוכלים.
חידות ללא מרגלים
חידות לינאריות
אלו חידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה [math]\displaystyle{ (\mathbb Z_2,+,\cdot) }[/math] ל־[math]\displaystyle{ (\{1,0\},\leftrightarrow,\or) }[/math] ע״י [math]\displaystyle{ \neg:x\mapsto\begin{cases}1,&x=0\\0,&x=1\end{cases} }[/math]. נראה שזהו אכן איזומורפיזם:
- חח״ע ועל – טריוויאליים.
- [math]\displaystyle{ \neg(x+y)\Leftrightarrow\neg(x\nleftrightarrow y)\Leftrightarrow x\leftrightarrow y\Leftrightarrow\neg x\leftrightarrow\neg y }[/math]
- [math]\displaystyle{ \neg(x\cdot y)\Leftrightarrow\neg(x\and y)\Leftrightarrow\neg x\or\neg y }[/math]
מכך נובע ש־[math]\displaystyle{ (\{1,0\},\leftrightarrow,\or) }[/math] שדה. נגדיר סכום [math]\displaystyle{ \sum_{i=1}^m P_i }[/math] (כאשר [math]\displaystyle{ \forall i:\ P_i\in\{1,0\} }[/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{ 1,0 }[/math] אז נוכל להציג כל [math]\displaystyle{ P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1} }[/math] בתור סכום של נעלמים שונים השווה לקבוע (לדוגמה, [math]\displaystyle{ B\leftrightarrow A\leftrightarrow0\Leftrightarrow1 }[/math] מפתרון דוגמה 1 שקול ל־[math]\displaystyle{ A\leftrightarrow B\Leftrightarrow0 }[/math], ששקול ל־[math]\displaystyle{ \sum_{X_i\in\{A,B\}}X_i\Leftrightarrow0 }[/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{ 2^{n-\operatorname{rank}(\mathbf A)} }[/math]. מובן שבד״כ יש רק פתרון אחד, כלומר [math]\displaystyle{ \mathbf A }[/math] הפיכה.