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

מתוך Math-Wiki
מ (המשך יבוא)
מ (טיוטה)
שורה 8: שורה 8:


== סימונים והגדרות ==
== סימונים והגדרות ==
באלגברה בוליאנית מסמנים <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>.
באלגברה בוליאנית מסמנים <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>.


=== דוגמה ===
=== דוגמה ===
באמצעות סימונים אלו נפתור את דוגמה 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&\mathrm T\\
(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\
(2)&B\leftrightarrow A\leftrightarrow\mathrm F&\Leftrightarrow&\mathrm T\\
(2)&B\leftrightarrow A\leftrightarrow0&\Leftrightarrow&1\\
(3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&\mathrm T\\
(3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&1\\
(4)&A\leftrightarrow C&\Leftrightarrow&\mathrm F\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&\mathrm T\\
(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\
(2)&A\leftrightarrow B&\Leftrightarrow&\mathrm F\\
(2)&A\leftrightarrow B&\Leftrightarrow&0\\
(3)&D&\Leftrightarrow&\mathrm T\\
(3)&D&\Leftrightarrow&1\\
(4)&A\leftrightarrow C&\Leftrightarrow&\mathrm F\end{array}</math>}}
(4)&A\leftrightarrow C&\Leftrightarrow&0\end{array}</math>}}
עתה נציב את (2) ב־(1) ונקבל <math>\mathrm F\leftrightarrow C\Leftrightarrow\mathrm T</math>, כלומר <math>C\Leftrightarrow\mathrm F</math>. נציב זאת ב־(4) ונקבל <math>A\Leftrightarrow\mathrm T</math>, ואם נציב את התוצאה ב־(2) נקבל <math>B\Leftrightarrow\mathrm F</math>. לסיכום, <math>A,D</math> אבירים ו־<math>B,C</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> נוכלים.


== חידות ללא מרגלים ==
== חידות ללא מרגלים ==
=== חידות לינאריות ===
=== חידות לינאריות ===
{| class="wikitable" style="float:left; clear:left; direction:ltr;"
אלו חידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה <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>. נראה שזהו אכן איזומורפיזם:
|+ טבלה 1
|-
! <math>x</math> !! <math>y</math> !! <math>\varphi(x+y)</math> !! <math>\varphi(x)\leftrightarrow\varphi(y)</math>
|-
| 0 || 0 || T || T
|-
| 0 || 1 || F || F
|-
| 1 || 0 || F || F
|-
| 1 || 1 || T || T
|}
{| class="wikitable" style="float:left; clear:left; direction:ltr;"
|+ טבלה 2
|-
! <math>x</math> !! <math>y</math> !! <math>\varphi(x\cdot y)</math> !! <math>\varphi(x)\or\varphi(y)</math>
|-
| 0 || 0 || T || T
|-
| 0 || 1 || T || T
|-
| 1 || 0 || T || T
|-
| 1 || 1 || F || F
|}
אלו חידות שניתן לפתור כמערכת משוואות לינאריות. ניצור איזומורפיזם מהשדה <math>(\mathbb Z_2,+,\cdot)</math> ל־<math>(\{\mathrm T,\mathrm F\},\leftrightarrow,\or)</math> ע״י <math>\varphi:x\mapsto\begin{cases}\mathrm T,&x=0\\\mathrm F,&x=1\end{cases}</math>. נראה שזהו אכן איזומורפיזם:
* חח״ע ועל – טריוויאליים.
* חח״ע ועל – טריוויאליים.
* <math>\varphi(x+y)\Leftrightarrow\varphi(x)\leftrightarrow\varphi(y)</math>: טבלה 1.
* <math>\neg(x+y)\Leftrightarrow\neg(x\nleftrightarrow y)\Leftrightarrow x\leftrightarrow y\Leftrightarrow\neg x\leftrightarrow\neg y</math>
* <math>\varphi(x\cdot y)\Leftrightarrow\varphi(x)\or\varphi(y)</math>: טבלה 2.
* <math>\neg(x\cdot y)\Leftrightarrow\neg(x\and y)\Leftrightarrow\neg x\or\neg y</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>(\{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>. כפל מטריצות מוגדר בהתאם.


כעת, אם התושבים הם <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 ניתן להציג באופן הבא:
כעת, אם התושבים הם <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}\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>}}
{{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>\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>2^{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:34, 27 ביוני 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{ 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):

[math]\displaystyle{ \begin{array}{llcl} (1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\ (2)&B\leftrightarrow A\leftrightarrow0&\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\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\ (2)&A\leftrightarrow B&\Leftrightarrow&0\\ (3)&D&\Leftrightarrow&1\\ (4)&A\leftrightarrow C&\Leftrightarrow&0\end{array} }[/math]

עתה נציב את (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 ניתן להציג באופן הבא:

[math]\displaystyle{ \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]\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] הפיכה.

ראו גם

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