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