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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(המשך יבוא)
 
מ (המשך יבוא)
שורה 1: שורה 1:
 
== הבעיה ==
 
== הבעיה ==
באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות בנוגע לאי דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל את הסוג של כמה מהתושבים) על סמך טענות שהתושבים טענו או על סמך שאלות כן/לא שהוא יכול לשאול, ולפעמים גם על סמך כמה עובדות שידועות לו.  
+
באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות (בדרך כלל את הסוג של כמה מהתושבים) על סמך טענות שהתושבים טענו או על סמך שאלות כן/לא שעליו לשאול, ולפעמים גם על סמך כמה עובדות שידועות לו.
  
* '''דוגמה 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> מאותו סוג כמוהו. יש למצוא את הסוג של כל תושב.
+
* '''דוגמה 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>). יש למצוא את הסוג של כל תושב.
 
* '''דוגמה 2:''' האורח נתקל בשלושה תושבים. אחד מהם אביר, אחד נוכל ואחד מרגל. אילו 3 שאלות של כן/לא הוא יכול לשאול על מנת לגלות את הסוג של כל אחד מהם?
 
* '''דוגמה 2:''' האורח נתקל בשלושה תושבים. אחד מהם אביר, אחד נוכל ואחד מרגל. אילו 3 שאלות של כן/לא הוא יכול לשאול על מנת לגלות את הסוג של כל אחד מהם?
  
נרצה ליצור מודל מתמטי לפתרון בעיות מסוג זה.  
+
נרצה ליצור מודל מתמטי לפתרון בעיות מסוג זה.
  
== סימונים ==
+
== סימונים והגדרות ==
באלגברה בוליאנית מסמנים <math>\mathrm T</math> כפסוק אמת ו־<math>\mathrm F</math> כפסוק שקר. באופן דומה, אם תושב <math>A</math> הוא אביר אז נסמן <math>A=\mathrm T</math> ואם נוכל – <math>A=\mathrm F</math>. אם הוא מרגל נסמן <math>A=\mathrm S</math>. אם תושב <math>B</math> יכול להיות מרגל אז נסמן את נכונות הטענה ה־<math>i</math> במספר שלו כ־<math>b_i</math>. כלומר, אם הטענה נכונה נסמן <math>b_i=\mathrm T</math> ואחרת <math>b_i=\mathrm F</math>. מכך נובע שאם הטענה ה־<math>i</math> של <math>B</math> היא <math>P</math> אז <math>b_i\Leftrightarrow P</math>, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול <math>b_i\leftrightarrow P\Leftrightarrow\mathrm T</math>. מובן שאם <math>B</math> אביר או נוכל אז <math>\forall i:\ b_i=B</math>, ולכן אם אנו כבר יודעים שתושב <math>B</math> אינו מרגל אז נסמן את טענותיו פשוט כ־<math>B</math>.
+
באלגברה בוליאנית מסמנים <math>\mathrm T</math> כפסוק אמת ו־<math>\mathrm F</math> כפסוק שקר. באופן דומה, אם תושב <math>A</math> הוא אביר אז נסמנו כ־<math>\mathrm T</math> ואם נוכל – <math>\mathrm F</math>. אם הוא מרגל נסמן <math>\mathrm S</math>. אם תושב <math>B</math> יכול להיות מרגל אז נסמן את נכונות הטענה ה־<math>i</math> במספר שלו כ־<math>b_i</math>. כלומר, אם הטענה נכונה אז <math>b_i\Leftrightarrow\mathrm T</math> ואחרת <math>b_i\Leftrightarrow\mathrm F</math>. מכך נובע שאם הטענה ה־<math>i</math> של <math>B</math> היא <math>P</math> אז <math>b_i\Leftrightarrow P</math>, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול <math>b_i\leftrightarrow P\Leftrightarrow\mathrm T</math>. מובן שאם <math>B</math> אביר או נוכל אז <math>\forall i:\ b_i\Leftrightarrow B</math>, ולכן אם אנו כבר יודעים שתושב <math>B</math> אינו מרגל אז נסמן את טענותיו פשוט כ־<math>B</math>.
  
באמצעות סימונים אלו נפתור את דוגמה 1 כמערכת משוואות פשוטה. <math>A</math> טוען ש־<math>B,C</math> מאותו סוג, כלומר הוא טוען <math>B\leftrightarrow C</math>. לפיכך, מהטענות של <math>B,C</math> ומהעובדה ש־<math>A,C</math> שונים:
+
=== דוגמה ===
 +
באמצעות סימונים אלו נפתור את דוגמה 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&\mathrm T\\
 
(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&\mathrm T\\
שורה 57: שורה 58:
 
* <math>\varphi(x\cdot y)\Leftrightarrow\varphi(x)\or\varphi(y)</math>: טבלה 2.
 
* <math>\varphi(x\cdot y)\Leftrightarrow\varphi(x)\or\varphi(y)</math>: טבלה 2.
  
מכך נובע ש־<math>\{\mathrm T,\mathrm F\}</math> שדה. נגדיר סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{\mathrm T,\mathrm F\}</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>.
+
מכך נובע ש־<math>\{\mathrm T,\mathrm F\}</math> שדה. נגדיר סכום <math>\sum_{i=1}^m P_i</math> (כאשר <math>\forall i:\ P_i\in\{\mathrm T,\mathrm F\}</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>. כפל מטריצות מוגדר בהתאם.
  
כעת, אם התושבים הם <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>\mathrm T,\mathrm F</math> אז נוכל להציג כל שרשור <math>P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע. לדוגמה, <math>B\leftrightarrow A\leftrightarrow\mathrm F\Leftrightarrow\mathrm T</math> מפתרון דוגמה 1 שקול ל־<math>A\leftrightarrow B\Leftrightarrow\mathrm F</math>, ששקול ל־<math>\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow\mathrm F</math>. ביטוי זה ניתן להציג גם כ־<math>\begin{pmatrix}\mathrm T&\mathrm T&\mathrm F&\mathrm F\end{pmatrix}\mathbf x\Leftrightarrow\mathrm F</math>, ולכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}\Leftrightarrow\mathbf b</math>. למשל, את דוגמה 1 ניתן להציג באופן הבא:
+
כעת, אם התושבים הם <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>\mathrm T,\mathrm F</math> אז נוכל להציג כל שרשור <math>P_1\leftrightarrow\dots\leftrightarrow P_n\Leftrightarrow P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע. לדוגמה, <math>B\leftrightarrow A\leftrightarrow\mathrm F\Leftrightarrow\mathrm T</math> מפתרון דוגמה 1 שקול ל־<math>A\leftrightarrow B\Leftrightarrow\mathrm F</math>, ששקול ל־<math>\sum_{X_i\in\{A,B\}}X_i\Leftrightarrow\mathrm F</math>. לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}\Leftrightarrow\mathbf b</math>. למשל, את דוגמה 1 ניתן להציג באופן הבא:
{{left|<math>\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}</math>}}
+
{{left|<math>\underbrace\begin{pmatrix}\mathrm F&\mathrm F&\mathrm F&\mathrm T\\\mathrm F&\mathrm F&\mathrm T&\mathrm T\\\mathrm T&\mathrm T&\mathrm T&\mathrm F\\\mathrm F&\mathrm T&\mathrm F&\mathrm T\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x\Leftrightarrow\underbrace\begin{pmatrix}\mathrm T\\\mathrm F\\\mathrm T\\\mathrm F\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>\mathbf A</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>\mathbf A</math> הפיכה.
  
 
== ראו גם ==
 
== ראו גם ==
 
* [http://en.wikipedia.org/wiki/Knights_and_Knaves Knights and Knaves] בוויקיפדיה האנגלית.
 
* [http://en.wikipedia.org/wiki/Knights_and_Knaves Knights and Knaves] בוויקיפדיה האנגלית.
 
* [http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever The Hardest Logic Puzzle Ever] בוויקיפדיה האנגלית.
 
* [http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever The Hardest Logic Puzzle Ever] בוויקיפדיה האנגלית.

גרסה מ־17:37, 15 ביוני 2013

הבעיה

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

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

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

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

באלגברה בוליאנית מסמנים \mathrm T כפסוק אמת ו־\mathrm F כפסוק שקר. באופן דומה, אם תושב A הוא אביר אז נסמנו כ־\mathrm T ואם נוכל – \mathrm F. אם הוא מרגל נסמן \mathrm S. אם תושב B יכול להיות מרגל אז נסמן את נכונות הטענה ה־i במספר שלו כ־b_i. כלומר, אם הטענה נכונה אז b_i\Leftrightarrow\mathrm T ואחרת b_i\Leftrightarrow\mathrm F. מכך נובע שאם הטענה ה־i של B היא P אז b_i\Leftrightarrow P, ומסיבות שיובנו בהמשך נעדיף את הסימון השקול b_i\leftrightarrow P\Leftrightarrow\mathrm T. מובן שאם 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&\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. לכן נוכל להגדיר מטריצת מקדמים \mathbf A ווקטור מקדמים חופשיים \mathbf b כך ש־\mathbf{Ax}\Leftrightarrow\mathbf b. למשל, את דוגמה 1 ניתן להציג באופן הבא:

\underbrace\begin{pmatrix}\mathrm F&\mathrm F&\mathrm F&\mathrm T\\\mathrm F&\mathrm F&\mathrm T&\mathrm T\\\mathrm T&\mathrm T&\mathrm T&\mathrm F\\\mathrm F&\mathrm T&\mathrm F&\mathrm T\end{pmatrix}_\mathbf A\underbrace\begin{pmatrix}A\\B\\C\\D\end{pmatrix}_\mathbf x\Leftrightarrow\underbrace\begin{pmatrix}\mathrm T\\\mathrm F\\\mathrm T\\\mathrm F\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). מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן אז כמה פתרונות יש. מובן שבד״כ יש רק פתרון אחד, כלומר \mathbf A הפיכה.

ראו גם