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

מתוך Math-Wiki
מ (טיוטה)
אין תקציר עריכה
שורה 1: שורה 1:
== הבעיה ==
== הבעיה ==
באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל את הסוג של כמה מהתושבים) על סמך טענות שהתושבים טענו או על סמך שאלות כן/לא שעליו לשאול, ולפעמים גם על סמך כמה עובדות שידועות לו.
באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות – לרוב את הסוג של כמה מהתושבים – על סמך כמה עובדות (שמרביתן מהצורה "תושב <math>X</math> טען ש־<math>P</math>") ו/או על סמך שאלות כן/לא שעליו לשאול.


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


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


== סימונים והגדרות ==
== חידות ללא מרגלים ==
באלגברה בוליאנית מסמנים <math>1</math> כפסוק אמת ו־<math>0</math> כפסוק שקר. באופן דומה, אם תושב <math>A</math> הוא אביר אז נסמנו כ־<math>1</math> ואם נוכל – <math>0</math>. אם הוא מרגל נסמן <math>p</math>. אם תושב <math>B</math> יכול להיות מרגל אז נסמן את נכונות הטענה ה־<math>i</math> במספר שלו כ־<math>b_i</math>. כלומר, אם הטענה נכונה אז <math>b_i\Leftrightarrow1</math> ואחרת <math>b_i\Leftrightarrow0</math>. מכך נובע שאם הטענה ה־<math>i</math> של <math>B</math> היא <math>P</math> אז <math>b_i\Leftrightarrow P</math>, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול <math>b_i\leftrightarrow P\Leftrightarrow1</math>. מובן שאם <math>B</math> אביר או נוכל אז <math>\forall i:\ b_i\Leftrightarrow B</math>, ולכן אם אנו כבר יודעים שתושב <math>B</math> אינו מרגל אז נסמן את טענותיו פשוט כ־<math>B</math>.
{| class="wikitable" style="direction:ltr; float:left; margin-top: 0;"
! <math>P</math> !! <math>Q</math> !! <math>P\leftrightarrow Q</math>
|-
| 0 || 0 || 1
|-
| 0 || 1 || 0
|-
| 1 || 0 || 0
|-
| 1 || 1 || 1
|}
באלגברה בוליאנית מסמנים <math>1</math> כפסוק אמת ו־<math>0</math> כפסוק שקר. באופן דומה, אם תושב <math>X</math> הוא אביר אז נסמנו כ־<math>1</math> ואם נוכל – <math>0</math>. נעזר בסימון <math>\leftrightarrow</math> לציון אופרטור שקילות לוגית, המוגדר כמפורט בטבלה שמשמאל. <math>\Leftrightarrow</math> הוא יחס שקילות בין כל שני פסוקים שקולים לוגית, כלומר אם ידוע ש־<math>P\leftrightarrow Q</math> נותן 1 אז נוכל לסמן <math>P\Leftrightarrow Q</math>. לפיכך, אם <math>X</math> טוען ש־<math>P</math> אז <math>X\Leftrightarrow P</math>.


=== דוגמה ===
'''דוגמה 1.1:''' באמצעות סימונים אלו נציג את ''דוגמה 1'' כמערכת משוואות בוליאניות. <math>A</math> טוען ש־<math>B,C</math> מאותו סוג, כלומר הוא טוען <math>B\leftrightarrow C</math>. מכך נובעת משוואה (1) במערכת המשוואות הבאה. מהטענות של <math>B,C</math> נובעות המשוואות (2) ו־(3), ומהעובדה ש־<math>A,C</math> שונים נובעת משוואה (4):
באמצעות סימונים אלו נפתור את דוגמה 1 כמערכת משוואות פשוטה. <math>A</math> טוען ש־<math>B,C</math> מאותו סוג, כלומר הוא טוען <math>B\leftrightarrow C</math>. מכך נובעת משוואה (1) במערכת המשוואות הבאה. מהטענות של <math>B,C</math> נובעות המשוואות (2) ו־(3), ומהעובדה ש־<math>A,C</math> שונים נובעת משוואה (4):
{{left|<math>\begin{array}{llcl}
{{left|<math>\begin{array}{llcl}
(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\
(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\
(2)&B\leftrightarrow A\leftrightarrow0&\Leftrightarrow&1\\
(2)&B\leftrightarrow A\leftrightarrow1&\Leftrightarrow&1\\
(3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&1\\
(3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&1\\
(4)&A\leftrightarrow C&\Leftrightarrow&0\end{array}</math>}}
(4)&A\leftrightarrow C&\Leftrightarrow&0\end{array}</math>}}
באופן שקול:
באופן שקול:
{{left|<math>\begin{array}{llcl}
{{left|<math>\begin{array}{llcl}
(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\
(1)&A\nleftrightarrow B\nleftrightarrow C&\Leftrightarrow&1\\
(2)&A\leftrightarrow B&\Leftrightarrow&0\\
(2)&A\nleftrightarrow B&\Leftrightarrow&0\\
(3)&D&\Leftrightarrow&1\\
(3)&D&\Leftrightarrow&1\\
(4)&A\leftrightarrow C&\Leftrightarrow&0\end{array}</math>}}
(4)&A\nleftrightarrow C&\Leftrightarrow&1\end{array}</math>}}
עתה נציב את (2) ב־(1) ונקבל <math>0\leftrightarrow C\Leftrightarrow1</math>, כלומר <math>C\Leftrightarrow0</math>. נציב זאת ב־(4) ונקבל <math>A\Leftrightarrow1</math>, ואם נציב את התוצאה ב־(2) נקבל <math>B\Leftrightarrow0</math>. לסיכום, <math>A,D</math> אבירים ו־<math>B,C</math> נוכלים.
 
=== חידות ללא שאלות ===
==== פתרון כמערכת משוואות ====
ברגע שיש לנו ניסוח מתמטי של החידה כמערכת משוואות קל לפתור אותה. אנו נתעמק בחידות שניתן לפתור כמערכת משוואות לינאריות כיוון שהן נותנות מידע רב יותר על החידה, כפי שנראה בהמשך.
 
ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2,+,\cdot)</math> ל־<math>(\{0,1\},\nleftrightarrow,\and)</math> ע״י <math>x\mapsto\begin{cases}0,&x=[0]_2\\1,&x=[1]_2\end{cases}</math>. מכך נובע ש־<math>(\{0,1\},\nleftrightarrow,\and)</math> שדה. סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{1,0\}</math>) יוגדר בתור <math>P_1\nleftrightarrow\dots\nleftrightarrow P_m</math> ומכפלה <math>\prod_{i=1}^m P_i</math> בתור <math>P_1\and\dots\and P_m</math>. גם כפל מטריצות מוגדר בהתאם.
 
כעת, אם התושבים הם <math>X_1,\dots,X_n</math> אז נסמן <math>\mathbf x:=\begin{pmatrix}X_1\\\vdots\\X_n\end{pmatrix}</math>. אם כל <math>P_i</math> מייצג נעלם <math>X_j</math> או קבוע <math>1,0</math> אז נוכל להציג כל <math>P_1\nleftrightarrow\dots\nleftrightarrow P_n\Leftrightarrow P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע: לדוגמה, <math>B\leftrightarrow A\leftrightarrow0\Leftrightarrow1</math> מהניסוח המתמטי של ''דוגמה 1'' שקול ל־<math>A\nleftrightarrow B\Leftrightarrow1</math>, כלומר ל־<math>\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow1</math>. לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}\Leftrightarrow\mathbf b</math>.
 
'''דוגמה 1.2:''' ההצגה המטריציונית של ''דוגמה 1'' היא
{{left|<math>\underbrace\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x\Leftrightarrow\underbrace\begin{pmatrix}1\\0\\1\\1\end{pmatrix}_\mathbf b</math>}}
 
הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (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> הפיכה.
 
'''דוגמה 1.3:''' נפתור את ''דוגמה 1''. חישוב פשוט מראה ש־<math>\mathbf A</math> הפיכה (ומכאן שיש פתרון יחיד) ו־<math>\mathbf A^{-1}\Leftrightarrow\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math>. לכן <math>\mathbf x\Leftrightarrow\mathbf A^{-1}\mathbf b\Leftrightarrow\begin{pmatrix}0\\0\\1\\1\end{pmatrix}</math> – התושבים <math>A,B</math> נוכלים ו־<math>C,D</math> אבירים.
 
==== פתרון באמצעות ניחוש ====
מנחשים את סוגו של אחד מהתושבים ומציבים במשוואות. אם מגיעים לסתירה אז יש להחליף את הסוג שנבחר ולפתור מחדש, אחרת נקבל מערכת משוואות פשוטה יותר. אם המערכת הזו עוד לא נותנת פתרון יחיד יש להמשיך לנחש עד לפתרון הסופי. אם החלפנו ניחוש ושוב הגענו לסתירה אז אין פתרון.
 
'''דוגמה 1.4:''' ננחש ש־<math>A</math> מ''דוגמה 1'' הוא אביר. מ־(2) נובע ש־<math>B</math> אביר ומ־(4) ש־<math>C</math> נוכל, אך זה סותר את (1) ולכן <math>A</math> נוכל. הצבה מחדש נותנת ש־<math>B</math> נוכל ו־<math>C,D</math> אבירים.
 
באופן כללי זו שיטה קלה יותר. אחד מהחסרונות שלה הוא שקשה למצוא באמצעותה את מספר הפתרונות, מה שעושים ע״י בדיקת היתכנות הסוג השני לכל תושב שניחשנו לו סוג.
 
'''דוגמה 3:''' האורח נתקל בתושבים <math>A,B,C</math>, שאינם מרגלים. <math>A</math> טוען ש־<math>B</math> נוכל וש־<math>C</math> אביר, כלומר <math>A\leftrightarrow(\neg B\and C)\Leftrightarrow1</math>. אם ננחש ש־<math>A</math> אביר נקבל פתרון יחיד, אך אם ננחש שהוא נוכל נקבל ש־<math>\neg B\and C\Leftrightarrow0</math>. במקרה הזה אפשר לנחש ש־<math>B</math> נוכל (ולקבל פתרון יחיד) או אביר (ולקבל שני פתרונות). מספר הפתרונות הוא אם כן <math>\underbrace1_{A\text{ is a knight}}+\underbrace{\underbrace1_{B\text{ is a knave}}+\underbrace2_{B\text{ is a knight}}}_{A\text{ is a knave}}=4</math>. זו מערכת לא לינארית ולכן לא ניתן לפתור אותה בשיטה של רושה–קפלי.


== חידות ללא מרגלים ==
חיסרון מהותי יותר הוא ששינוי של <math>\mathbf b</math> דורש פתרון מחדש של הבעיה כולה. <!---->כמו כן, הפתרון לא נותן לנו את התובנות שקיבלנו מפתרון כמערכת משוואות לינאריות, תובנות שיעזרו לנו בחידות שבהן שואלים שאלות. <!---->
=== חידות לינאריות ===
אלו חידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2,+,\cdot)</math> ל־<math>(\{1,0\},\leftrightarrow,\or)</math> ע״י <math>\neg:x\mapsto\begin{cases}1,&x=0\\0,&x=1\end{cases}</math>. נראה שזהו אכן איזומורפיזם:
* חח״ע ועל – טריוויאליים.
* <math>\neg(x+y)\Leftrightarrow\neg(x\nleftrightarrow y)\Leftrightarrow x\leftrightarrow y\Leftrightarrow\neg x\leftrightarrow\neg y</math>
* <math>\neg(x\cdot y)\Leftrightarrow\neg(x\and y)\Leftrightarrow\neg x\or\neg y</math>


מכך נובע ש־<math>(\{1,0\},\leftrightarrow,\or)</math> שדה. נגדיר סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{1,0\}</math>) בתור <math>P_1\leftrightarrow\dots\leftrightarrow P_m</math> ומכפלה <math>\prod_{i=1}^m P_i</math> בתור <math>P_1\or\dots\or P_m</math>. כפל מטריצות מוגדר בהתאם.
=== חידות עם שאלות ===
במקרה שאין מרגלים ואין עובדות החידות האלה טריוויאליות – ניתן לשאול כל תושב "האם 1=1?" (או כל שאלה אחרת שהתשובה לה ידועה) ולהסיק את סוגו. זאת כמובן כאשר מספר השאלות שמותר לשאול הוא לכל הפחות מספר התושבים, מה שחייב להתקיים אם החידה פתירה: אם יש <math>n</math> תושבים אז יש <math>2^n</math> אפשרויות לחלוקת הסוגים שלהם.


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


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


== מקורות והשראות ==
== מקורות והשראות ==
שורה 47: שורה 84:
* [https://en.wikipedia.org/wiki/Three-valued_logic Three-valued logic]
* [https://en.wikipedia.org/wiki/Three-valued_logic Three-valued logic]
}}
}}
<!-- סיבוכיות? -->

גרסה מ־21:53, 20 ביולי 2013

הבעיה

באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות – לרוב את הסוג של כמה מהתושבים – על סמך כמה עובדות (שמרביתן מהצורה "תושב [math]\displaystyle{ X }[/math] טען ש־[math]\displaystyle{ P }[/math]") ו/או על סמך שאלות כן/לא שעליו לשאול.

  • דוגמה 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]. מה הסוג של כל תושב?
  • דוגמה 2: האורח נתקל בשלושה תושבים. אחד מהם אביר, אחד נוכל ואחד מרגל. אילו 3 שאלות של כן/לא הוא יכול לשאול על מנת לגלות את הסוג של כל אחד מהם?

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

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

[math]\displaystyle{ P }[/math] [math]\displaystyle{ Q }[/math] [math]\displaystyle{ P\leftrightarrow Q }[/math]
0 0 1
0 1 0
1 0 0
1 1 1

באלגברה בוליאנית מסמנים [math]\displaystyle{ 1 }[/math] כפסוק אמת ו־[math]\displaystyle{ 0 }[/math] כפסוק שקר. באופן דומה, אם תושב [math]\displaystyle{ X }[/math] הוא אביר אז נסמנו כ־[math]\displaystyle{ 1 }[/math] ואם נוכל – [math]\displaystyle{ 0 }[/math]. נעזר בסימון [math]\displaystyle{ \leftrightarrow }[/math] לציון אופרטור שקילות לוגית, המוגדר כמפורט בטבלה שמשמאל. [math]\displaystyle{ \Leftrightarrow }[/math] הוא יחס שקילות בין כל שני פסוקים שקולים לוגית, כלומר אם ידוע ש־[math]\displaystyle{ P\leftrightarrow Q }[/math] נותן 1 אז נוכל לסמן [math]\displaystyle{ P\Leftrightarrow Q }[/math]. לפיכך, אם [math]\displaystyle{ X }[/math] טוען ש־[math]\displaystyle{ P }[/math] אז [math]\displaystyle{ X\Leftrightarrow P }[/math].

דוגמה 1.1: באמצעות סימונים אלו נציג את דוגמה 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):

[math]\displaystyle{ \begin{array}{llcl} (1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\ (2)&B\leftrightarrow A\leftrightarrow1&\Leftrightarrow&1\\ (3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&1\\ (4)&A\leftrightarrow C&\Leftrightarrow&0\end{array} }[/math]

באופן שקול:

[math]\displaystyle{ \begin{array}{llcl} (1)&A\nleftrightarrow B\nleftrightarrow C&\Leftrightarrow&1\\ (2)&A\nleftrightarrow B&\Leftrightarrow&0\\ (3)&D&\Leftrightarrow&1\\ (4)&A\nleftrightarrow C&\Leftrightarrow&1\end{array} }[/math]

חידות ללא שאלות

פתרון כמערכת משוואות

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

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

דוגמה 1.2: ההצגה המטריציונית של דוגמה 1 היא

[math]\displaystyle{ \underbrace\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x\Leftrightarrow\underbrace\begin{pmatrix}1\\0\\1\\1\end{pmatrix}_\mathbf b }[/math]

הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (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] הפיכה.

דוגמה 1.3: נפתור את דוגמה 1. חישוב פשוט מראה ש־[math]\displaystyle{ \mathbf A }[/math] הפיכה (ומכאן שיש פתרון יחיד) ו־[math]\displaystyle{ \mathbf A^{-1}\Leftrightarrow\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix} }[/math]. לכן [math]\displaystyle{ \mathbf x\Leftrightarrow\mathbf A^{-1}\mathbf b\Leftrightarrow\begin{pmatrix}0\\0\\1\\1\end{pmatrix} }[/math] – התושבים [math]\displaystyle{ A,B }[/math] נוכלים ו־[math]\displaystyle{ C,D }[/math] אבירים.

פתרון באמצעות ניחוש

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

דוגמה 1.4: ננחש ש־[math]\displaystyle{ A }[/math] מדוגמה 1 הוא אביר. מ־(2) נובע ש־[math]\displaystyle{ B }[/math] אביר ומ־(4) ש־[math]\displaystyle{ C }[/math] נוכל, אך זה סותר את (1) ולכן [math]\displaystyle{ A }[/math] נוכל. הצבה מחדש נותנת ש־[math]\displaystyle{ B }[/math] נוכל ו־[math]\displaystyle{ C,D }[/math] אבירים.

באופן כללי זו שיטה קלה יותר. אחד מהחסרונות שלה הוא שקשה למצוא באמצעותה את מספר הפתרונות, מה שעושים ע״י בדיקת היתכנות הסוג השני לכל תושב שניחשנו לו סוג.

דוגמה 3: האורח נתקל בתושבים [math]\displaystyle{ A,B,C }[/math], שאינם מרגלים. [math]\displaystyle{ A }[/math] טוען ש־[math]\displaystyle{ B }[/math] נוכל וש־[math]\displaystyle{ C }[/math] אביר, כלומר [math]\displaystyle{ A\leftrightarrow(\neg B\and C)\Leftrightarrow1 }[/math]. אם ננחש ש־[math]\displaystyle{ A }[/math] אביר נקבל פתרון יחיד, אך אם ננחש שהוא נוכל נקבל ש־[math]\displaystyle{ \neg B\and C\Leftrightarrow0 }[/math]. במקרה הזה אפשר לנחש ש־[math]\displaystyle{ B }[/math] נוכל (ולקבל פתרון יחיד) או אביר (ולקבל שני פתרונות). מספר הפתרונות הוא אם כן [math]\displaystyle{ \underbrace1_{A\text{ is a knight}}+\underbrace{\underbrace1_{B\text{ is a knave}}+\underbrace2_{B\text{ is a knight}}}_{A\text{ is a knave}}=4 }[/math]. זו מערכת לא לינארית ולכן לא ניתן לפתור אותה בשיטה של רושה–קפלי.

חיסרון מהותי יותר הוא ששינוי של [math]\displaystyle{ \mathbf b }[/math] דורש פתרון מחדש של הבעיה כולה. כמו כן, הפתרון לא נותן לנו את התובנות שקיבלנו מפתרון כמערכת משוואות לינאריות, תובנות שיעזרו לנו בחידות שבהן שואלים שאלות.

חידות עם שאלות

במקרה שאין מרגלים ואין עובדות החידות האלה טריוויאליות – ניתן לשאול כל תושב "האם 1=1?" (או כל שאלה אחרת שהתשובה לה ידועה) ולהסיק את סוגו. זאת כמובן כאשר מספר השאלות שמותר לשאול הוא לכל הפחות מספר התושבים, מה שחייב להתקיים אם החידה פתירה: אם יש [math]\displaystyle{ n }[/math] תושבים אז יש [math]\displaystyle{ 2^n }[/math] אפשרויות לחלוקת הסוגים שלהם.


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

חידות ללא שאלות

פתרון כמערכת משוואות

פתרון באמצעות ניחוש

חידות עם שאלות

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


אוחזר מתוך "https://math-wiki.com/index.php?title=משתמש:אור_שחף/עבודה_ב%22שימושי_המתמטיקה_ביומיום%22&oldid=36217"