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

גרסה אחרונה מ־15:23, 6 באוגוסט 2013

בחידות אבירים ונוכלים (Knights and Knaves) מדברים על אי מסוים בו כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי, אך לא נעסוק בהם. החידות דנות באורח באי המנסה להסיק מספר מסקנות – לרוב את הסוג של כמה מהתושבים – על סמך כמה עובדות (שמרביתן מהצורה "תושב $X$ טען ש־ $P$ ") ו/או על סמך שאלות כן/לא שעליו לשאול.

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

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

תוכן עניינים

1 חידות ללא שאלות
- 1.1 פתרון כמערכת משוואות
- 1.2 פתרון באמצעות ניחוש
2 חידות עם שאלות
- 2.1 מערכת עובדות לינאריות
- 2.2 המספר המינימלי של שאלות

$P$	$Q$	$P\leftrightarrow Q$
0	0	1
0	1	0
1	0	0
1	1	1

באלגברה בוליאנית מסמנים $1$ כפסוק אמת ו־ $0$ כפסוק שקר. נעזר בסימון $\leftrightarrow$ לציון אופרטור שקילות לוגית, המוגדר כמפורט בטבלה שמשמאל. $=$ הוא יחס שקילות בין כל שני פסוקים שקולים לוגית, כלומר אם ידוע ש־ $P\leftrightarrow Q$ נותן 1 אז נוכל לסמן $P=Q$ . אם תושב $X$ הוא אביר אז נסמן $X=1$ ואם נוכל – $X=0$ . לפיכך, אם $X$ טוען טענה $P$ אז $X=P$ .

דוגמה 1.1: באמצעות סימונים אלו נציג את דוגמה 1 כמערכת משוואות בוליאניות.

A

טוען ש־

B,C

מאותו סוג, כלומר הוא טוען

B\leftrightarrow C

. מכך נובעת משוואה (1) במערכת המשוואות הבאה. מהטענות של

B,C

נובעות המשוואות (2) ו־(3), ומהעובדה ש־

A,C

שונים נובעת משוואה (4):

\begin{array}{llcl} (1)&A\leftrightarrow B\leftrightarrow C&=&1\\ (2)&B\leftrightarrow A\leftrightarrow1&=&1\\ (3)&C\leftrightarrow C\leftrightarrow D&=&1\\ (4)&A\leftrightarrow C&=&0\end{array}

באופן שקול:

\begin{array}{llcl} (1)&A\nleftrightarrow B\nleftrightarrow C&=&1\\ (2)&A\nleftrightarrow B&=&0\\ (3)&D&=&1\\ (4)&A\nleftrightarrow C&=&1\end{array}

כאשר

\nleftrightarrow

מציין אופרטור XOR, המסומן גם כ־

\oplus

.

בסימונים אלו נגדיר עובדה בתור משוואה בוליאנית שנתונה בחידה, כגון $A\leftrightarrow C=0$ מדוגמה 1.

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

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

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

ניצור איזומורפיזם מהשדה $(\mathbb Z_2,+,\cdot)$ ל־ $(\{0,1\},\nleftrightarrow,\and)$ ע״י $x\mapsto\begin{cases}0,&x=[0]_2\\1,&x=[1]_2\end{cases}$ . מכך נובע ש־ $(\{0,1\},\nleftrightarrow,\and)$ שדה. סכום $\sum_{i=1}^m P_i$ (כאשר $\forall i:\ P_i\in\{0,1\}$ ) יוגדר בתור $P_1\nleftrightarrow\dots\nleftrightarrow P_m$ ומכפלה $\prod_{i=1}^m P_i$ בתור $P_1\and\dots\and P_m$ . גם כפל מטריצות מוגדר בהתאם.

כעת, אם התושבים הם $X_1,\dots,X_n$ אז נסמן $\mathbf x:=\begin{pmatrix}X_1\\\vdots\\X_n\end{pmatrix}$ . אם כל $P_i$ מייצג נעלם $X_j$ או קבוע $1,0$ אז נוכל להציג כל $P_1\leftrightarrow\dots\leftrightarrow P_n=P_{n+1}$ בתור סכום של נעלמים שונים השווה לקבוע: לדוגמה, $B\leftrightarrow A\leftrightarrow1=1$ מהניסוח המתמטי של דוגמה 1 שקול ל־ $A\nleftrightarrow B=0$ , כלומר ל־ $\sum_{X_i\in\{A,B\}}X_i=0$ . לכן נוכל להגדיר מטריצת מקדמים $\mathbf A$ ווקטור מקדמים חופשיים $\mathbf b$ כך ש־ $\mathbf{Ax}=\mathbf b$ .

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

\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=\underbrace\begin{pmatrix}1\\0\\1\\1\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)$ . מכאן נובע שאנו יכולים לבדוק האם קיים פתרון לחידה, ואם כן לחשב את מספר הפתרונות בתור $2^{n-\operatorname{rank}(\mathbf A)}$ . מובן שבד״כ יש רק פתרון אחד, כלומר $\operatorname{rank}(\mathbf A)=n$ ואז, אם ל־ $\mathbf A$ יש $n$ שורות אז היא הפיכה. אם לא אז ניתן למחוק כמה שורות של $\mathbf A$ (וגם את השורות המתאימות ב־ $\mathbf b$ ) כך שהיא תהיה הפיכה.

דוגמה 1.3: נפתור את דוגמה 1. חישוב פשוט מראה ש־

\mathbf A

הפיכה (ומכאן שיש פתרון יחיד) ו־

\mathbf A^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}

. לכן

\mathbf x=\mathbf A^{-1}\mathbf b=\begin{pmatrix}0\\0\\1\\1\end{pmatrix}

– התושבים

A,B

נוכלים ו־

C,D

אבירים.

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

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

דוגמה 1.4: ננחש ש־

A

מדוגמה 1 הוא אביר. מ־(2) נובע ש־

B

אביר ומ־(4) ש־

C

נוכל, אך זה סותר את (1) ולכן

A

נוכל. הצבה מחדש נותנת ש־

B

נוכל ו־

C,D

אבירים, וקיבלנו פתרון יחיד.

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

דוגמה 3: האורח נתקל בתושבים

A,B,C

.

A

טוען ש־

B

נוכל וגם

C

אביר, כלומר

A\leftrightarrow(\neg B\and C)=1

. אם ננחש ש־

A

אביר נקבל פתרון יחיד, אך אם ננחש שהוא נוכל נקבל ש־

\neg B\and C=0

. במקרה הזה אפשר לנחש ש־

B

נוכל (ולקבל פתרון יחיד) או אביר (ולקבל שני פתרונות). מספר הפתרונות הוא אם כן

\underbrace1_{A\text{ is a knight}}+\underbrace{\overbrace1^{B\text{ is a knave}}+\overbrace2^{B\text{ is a knight}}}_{A\text{ is a knave}}=4

. המערכת אינה לינארית ולכן לא ניתן לחשב את מספר הפתרונות באמצעות משפט רושה–קפלי.

חיסרון מהותי יותר הוא ששינוי של $\mathbf b$ דורש פתרון מחדש של הבעיה כולה. כמו כן, אנו נעזר בפתרון באמצעות מערכת משוואות לינאריות בחידות שבהן שואלים שאלות.

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

שאלה היא פסוק לוגי שאנחנו יכולים לבחור ותלוי בסוגים של תושבים. למשל, את השאלה "האם $X_2$ אביר?" שמופנת ל־ $X_1$ נייצג בתור $X_1\leftrightarrow X_2$ , ואת השאלה " $X_1$ , האם 3=3?" בתור $X_1\leftrightarrow1=X_1$ . נסמן כ־ $n$ את מספר התושבים ונניח שמותר לשאול עד $m$ שאלות. נסמן $\mathbf q=\begin{pmatrix}Q_1\\\vdots\\Q_m\end{pmatrix}$ כווקטור השאלות. תשובה תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־ $\mathbf r=\begin{pmatrix}r_1\\\vdots\\r_m\end{pmatrix}$ את וקטור התשובות. מההגדרות נובע ש־ $\mathbf q=\mathbf r$ . $\mathbf x$ מוגדר כמקודם, ואז ניתן לחשוב על $\mathbf q$ כעל פונקציה $\mathbf x\mapsto\mathbf r$ .

דוגמה 2.1: יש 3 תושבים (

n=3

), מותר לשאול עד 2 שאלות (

m=2

) ו־

X_3

טוען ש־

X_1

ו/או

X_2

אבירים, דהיינו

X_3\leftrightarrow(X_1\or X_2)=1

. וקטור השאלות

\mathbf q=\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\end{pmatrix}

, לדוגמה, מאפשר לפתור את החידה כי תמיד מתקיים

\mathbf x=\begin{pmatrix}r_2\\r_1\leftrightarrow r_2\\r_2\or (r_1\leftrightarrow r_2)\end{pmatrix}=\begin{pmatrix}r_2\\r_1\leftrightarrow r_2\\r_1\rightarrow r_2\end{pmatrix}

.

בחידות מסוג זה נתונות עובדות, ונסמן כ־ $S$ את קבוצת הפתרונות $\mathbf x$ המקיימים אותן. בד״כ המטרה היא למצוא $\mathbf q$ חח״ע מ־ $S$ , כלומר למצוא שאלות שעבורן לכל וקטור תשובות $\mathbf r=\mathbf q(\mathbf x)$ ניתן יהיה להסיק את וקטור הסוגים של התושבים, $\mathbf x=\mathbf q^{-1}(\mathbf r)$ .

יהי $k\in\mathbb N\cup\{0\}$ המספר המינימלי כך ש־ $|S|\le2^k$ . נוכיח ש־ $k\le m$ : החידה פתירה, כלומר קיים וקטור שאלות $\mathbf q$ חח״ע מ־ $S$ . $\mathbf q$ היא פונקציה על קבוצת וקטורי התשובות ולפיכך יש $|S|$ אפשרויות ל־ $\mathbf r$ . מאידך, $\mathbf q$ מורכבת מ־ $m$ שאלות ולכל אחת יש עד 2 תשובות אפשריות, לכן יש עד $2^m$ אפשרויות ל־ $\mathbf r$ , דהיינו $2^{k-1}<|S|\le2^m$ . נקבל $k-1<m$ ולבסוף $k\le m$ כי $k,m\in\mathbb Z$ . $\blacksquare$

מערכת עובדות לינאריות

במקרה זה $S=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf b\}$ . אם שורות המטריצה $\mathbf A$ תלויות לינארית ניתן למחוק כמה מהן (וגם את השורות המתאימות ב־ $\mathbf b$ ) כך ששורותיה יהיו בת״ל ו־ $S$ לא תשתנה. לכן נניח בה״כ ששורות $\mathbf A$ בת״ל.

דוגמה 4.1:

n=4

ונתון

\begin{pmatrix}1&1&1&0\\0&0&0&0\\1&1&0&0\\0&0&1&0\end{pmatrix}\mathbf x=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}

השורה השנייה במערכת זו מיותרת והשורה הרביעית היא סכום השורה הראשונה והשלישית. לכן נמחק את שורות 2,4 ונקבל

\underbrace\begin{pmatrix}1&1&1&0\\1&1&0&0\end{pmatrix}_\mathbf A\mathbf x=\underbrace\begin{pmatrix}1\\0\end{pmatrix}_\mathbf b

נשים לב שלפי משפט רושה–קפלי $|S|=2^{n-\operatorname{rank}(\mathbf A)}=2^k$ ולכן $\operatorname{rank}(\mathbf A)=n-k$ . השורות של $\mathbf A$ בת״ל ולכן יש לה $n-k$ שורות.

כדי לפתור את החידה נבחר $\mathbf Q\in\{0,1\}^{k\times n}$ כך ש־ $\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}$ מטריצה הפיכה, ואז $\mathbf q=\mathbf Q\mathbf x$ ו־ $\mathbf x=\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}^{-1}\begin{pmatrix}\mathbf b\\\mathbf r\end{pmatrix}$ . לשם כך צריך להראות שקיימת $\mathbf Q$ כנ״ל, אבל זה די טריוויאלי: השורות של $\mathbf A$ בת״ל ולכן הן בסיס לתת־מרחב של $\{0,1\}^{1\times n}$ ממימד $k$ . נבחר בסיס כלשהו לתת־מרחב המשלים האורתוגונלי לו ונציב את איבריו כשורות מטריצה $\mathbf Q$ . אזי $\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}\in\{0,1\}^{(n-k+k)\times n}=\{0,1\}^{n\times n}$ מטריצה ריבועית ששורותיה בת״ל, כלומר היא הפיכה. $\blacksquare$

דוגמה 4.2: עלינו למצוא את הסוגים של כל התושבים בדוגמה 4 במינימום שאלות, כלומר ב־

k=n-\operatorname{rank}(\mathbf A)=2

שאלות (הוכחה ש־

k

הוא המספר המינימלי הדרוש של שאלות – בהמשך). שני וקטורי שורה שאינם תלויים לינארית ב־

\begin{pmatrix}1&1&1&0\end{pmatrix},\begin{pmatrix}1&1&0&0\end{pmatrix}

הם לדוגמה

\begin{pmatrix}0&0&0&1\end{pmatrix},\begin{pmatrix}1&0&1&0\end{pmatrix}

ולכן

\mathbf q=\begin{pmatrix}X_4\\X_1\nleftrightarrow X_3\end{pmatrix}

וקטור שאלות מתאים.

\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}^{-1}=\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}

והפתרון הכללי הוא

\mathbf x=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}\begin{pmatrix}1\\0\\\mathbf r\!\!\!\!\!\begin{matrix}&\\&\end{matrix}\end{pmatrix}

.

המספר המינימלי של שאלות

נניח ש־ $m$ הוא המספר המינימלי של שאלות הדרוש לפתרון חידת שאלות נתונה ונרצה להוכיח ש־ $m=k=\lceil\log_2(|S|)\rceil$ : תהי $V=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf 0\}$ כך ש־ $\mathbf A\in\{0,1\}^{(n-k)\times n}$ מטריצה כרצוננו ששורותיה בת״ל. לכן $|V|=2^{n-\operatorname{rank}(\mathbf A)}=2^k$ ובפרט קיימת פונקציה $f:S\to V$ חח״ע. תהי $\mathbf Q\in\{0,1\}^{k\times n}$ מטריצה כך ש־ $\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}$ הפיכה ואז $\mathbf q':\mathbf v\mapsto\mathbf Q\mathbf v$ חח״ע מ־ $V$ . נגדיר $\mathbf q=\mathbf q'\circ f$ ולכן $\mathbf q$ חח״ע מ־ $S$ והיא מורכבת מ־ $k$ שאלות, כלומר $k\ge m$ . בעבר הוכחנו ש־ $k\le m$ ולכן $m=k$ . $\blacksquare$

@@ שורה 1: / שורה 1: @@
-== הבעיה ==
+ב[https://en.wikipedia.org/wiki/Knights_and_Knaves חידות אבירים ונוכלים (Knights and Knaves)] מדברים על אי מסוים בו כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי, אך לא נעסוק בהם. החידות דנות באורח באי המנסה להסיק מספר מסקנות – לרוב את הסוג של כמה מהתושבים – על סמך כמה עובדות (שמרביתן מהצורה "תושב <math>X</math> טען ש־<math>P</math>") ו/או על סמך שאלות כן/לא שעליו לשאול.
-באי מסוים כל התושבים הם או אבירים, הדוברים תמיד אמת, או נוכלים, אשר תמיד משקרים. בחלק מהבעיות מוסיפים סוג נוסף – מרגלים, שעונים אמת או שקר באקראי. החידות דנות באורח באי המנסה להסיק מספר מסקנות – לרוב את הסוג של כמה מהתושבים – על סמך כמה עובדות (שמרביתן מהצורה "תושב <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>. מה הסוג של כל תושב?
+* '''דוגמה 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:''' האורח נתקל בשלושה תושבים, והשלישי שבהם טוען שלפחות אחד משני התושבים האחרים הוא אביר. אילו 2 שאלות כן/לא יכול האורח לשאול את התושבים על מנת להסיק את הסוגים שלהם?
-נרצה ליצור מודל מתמטי לפתרון בעיות מסוג זה.
+ניצור מודל מתמטי לפתרון בעיות מסוג זה.
-== חידות ללא מרגלים ==
+__תוכן__
-{| class="wikitable" style="direction:ltr; float:left; margin-top: 0;"
+{| class="wikitable" style="direction:ltr; float:left; margin-top:0;"
 ! <math>P</math> !! <math>Q</math> !! <math>P\leftrightarrow Q</math>
 |-
@@ שורה 19: / שורה 18: @@
 | 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>.
+באלגברה בוליאנית מסמנים <math>1</math> כפסוק אמת ו־<math>0</math> כפסוק שקר. נעזר בסימון <math>\leftrightarrow</math> לציון אופרטור שקילות לוגית, המוגדר כמפורט בטבלה שמשמאל. <math>=</math> הוא יחס שקילות בין כל שני פסוקים שקולים לוגית, כלומר אם ידוע ש־<math>P\leftrightarrow Q</math> נותן 1 אז נוכל לסמן <math>P=Q</math>. אם תושב <math>X</math> הוא אביר אז נסמן <math>X=1</math> ואם נוכל – <math>X=0</math>. לפיכך, אם <math>X</math> טוען טענה <math>P</math> אז <math>X=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.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):
 {{left|<math>\begin{array}{llcl}
-(1)&A\leftrightarrow B\leftrightarrow C&\Leftrightarrow&1\\
+(1)&A\leftrightarrow B\leftrightarrow C&=&1\\
-(2)&B\leftrightarrow A\leftrightarrow1&\Leftrightarrow&1\\
+(2)&B\leftrightarrow A\leftrightarrow1&=&1\\
-(3)&C\leftrightarrow C\leftrightarrow D&\Leftrightarrow&1\\
+(3)&C\leftrightarrow C\leftrightarrow D&=&1\\
-(4)&A\leftrightarrow C&\Leftrightarrow&0\end{array}</math>}}
+(4)&A\leftrightarrow C&=&0\end{array}</math>}}
-באופן שקול:
+:באופן שקול:
 {{left|<math>\begin{array}{llcl}
-(1)&A\nleftrightarrow B\nleftrightarrow C&\Leftrightarrow&1\\
+(1)&A\nleftrightarrow B\nleftrightarrow C&=&1\\
-(2)&A\nleftrightarrow B&\Leftrightarrow&0\\
+(2)&A\nleftrightarrow B&=&0\\
-(3)&D&\Leftrightarrow&1\\
+(3)&D&=&1\\
-(4)&A\nleftrightarrow C&\Leftrightarrow&1\end{array}</math>}}
+(4)&A\nleftrightarrow C&=&1\end{array}</math>}}
-כאשר <math>\nleftrightarrow</math> מציין אופרטור XOR, המסומן גם כ־<math>\oplus</math>.
+:כאשר <math>\nleftrightarrow</math> מציין אופרטור XOR, המסומן גם כ־<math>\oplus</math>.
-בסימונים אלו נגדיר ''עובדה'' בתור משוואה בוליאנית שנתונה בחידה, כגון <math>A\leftrightarrow C\Leftrightarrow0</math> מ''דוגמה 1''.
+בסימונים אלו נגדיר ''עובדה'' בתור משוואה בוליאנית שנתונה בחידה, כגון <math>A\leftrightarrow C=0</math> מ''דוגמה 1''.
 === חידות ללא שאלות ===
 ==== פתרון כמערכת משוואות ====
-ברגע שיש לנו ניסוח מתמטי של החידה כמערכת משוואות קל לפתור אותה. אנו נתעמק בחידות שניתן לפתור כמערכת משוואות לינאריות כיוון שהן נותנות מידע רב יותר על החידה, כפי שנראה בהמשך.
+ברגע שיש לנו ניסוח מתמטי של החידה כמערכת משוואות אפשר לפתור אותה כפי שעושים באלגברה בוליאנית. נתעמק בחידות שניתן לפתור כמערכת משוואות לינאריות.
 ניצור איזומורפיזם מהשדה <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\{0,1\}</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>.
+כעת, אם התושבים הם <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=P_{n+1}</math> בתור סכום של נעלמים שונים השווה לקבוע: לדוגמה, <math>B\leftrightarrow A\leftrightarrow1=1</math> מהניסוח המתמטי של ''דוגמה 1'' שקול ל־<math>A\nleftrightarrow B=0</math>, כלומר ל־<math>\sum_{X_i\in\{A,B\}}X_i=0</math>. לכן נוכל להגדיר מטריצת מקדמים <math>\mathbf A</math> ווקטור מקדמים חופשיים <math>\mathbf b</math> כך ש־<math>\mathbf{Ax}=\mathbf b</math>.
-'''דוגמה 1.2:''' ההצגה המטריציונית של ''דוגמה 1'' היא
+:'''דוגמה 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>}}
+{{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=\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> הפיכה.
+הצגה זו מאפשרת לנו למצוא מה הסוג של כל תושב ע״י פתרון מערכת משוואות לינאריות. יתרה מזאת, לפי משפט רושה–קפלי (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>\operatorname{rank}(\mathbf A)=n</math> ואז, אם ל־<math>\mathbf A</math> יש <math>n</math> שורות אז היא הפיכה. אם לא אז ניתן למחוק כמה שורות של <math>\mathbf A</math> (וגם את השורות המתאימות ב־<math>\mathbf b</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.3:''' נפתור את ''דוגמה 1''. חישוב פשוט מראה ש־<math>\mathbf A</math> הפיכה (ומכאן שיש פתרון יחיד) ו־<math>\mathbf A^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math>. לכן <math>\mathbf x=\mathbf A^{-1}\mathbf b=\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> אבירים, וקיבלנו פתרון יחיד.
+:'''דוגמה 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>. זו מערכת לא לינארית ולכן לא ניתן לפתור אותה בשיטה של רושה–קפלי.
+:'''דוגמה 3:''' האורח נתקל בתושבים <math>A,B,C</math>. <math>A</math> טוען ש־<math>B</math> נוכל וגם <math>C</math> אביר, כלומר <math>A\leftrightarrow(\neg B\and C)=1</math>. אם ננחש ש־<math>A</math> אביר נקבל פתרון יחיד, אך אם ננחש שהוא נוכל נקבל ש־<math>\neg B\and C=0</math>. במקרה הזה אפשר לנחש ש־<math>B</math> נוכל (ולקבל פתרון יחיד) או אביר (ולקבל שני פתרונות). מספר הפתרונות הוא אם כן <math>\underbrace1_{A\text{ is a knight}}+\underbrace{\overbrace1^{B\text{ is a knave}}+\overbrace2^{B\text{ is a knight}}}_{A\text{ is a knave}}=4</math>. המערכת אינה לינארית ולכן לא ניתן לחשב את מספר הפתרונות באמצעות משפט רושה–קפלי.
-חיסרון מהותי יותר הוא ששינוי של <math>\mathbf b</math> דורש פתרון מחדש של הבעיה כולה. <!---->כמו כן, הפתרון לא נותן לנו את התובנות שקיבלנו מפתרון כמערכת משוואות לינאריות, תובנות שיעזרו לנו בחידות שבהן שואלים שאלות. <!---->
+חיסרון מהותי יותר הוא ששינוי של <math>\mathbf b</math> דורש פתרון מחדש של הבעיה כולה. כמו כן, אנו נעזר בפתרון באמצעות מערכת משוואות לינאריות בחידות שבהן שואלים שאלות.
 === חידות עם שאלות ===
-נגדיר ''שאלה'' כפסוק לוגי שאנחנו יכולים לבחור ושתלוי בסוגים של התושבים, כגון <math>X_1\or X_2</math>. נסמן כ־<math>n</math> את מספר התושבים ונניח שמותר לשאול עד <math>m</math> שאלות כדי להסיק את הסוג של כל אחד מהם. נסמן <math>\mathbf p\Leftrightarrow\begin{pmatrix}P_1\\\vdots\\P_m\end{pmatrix}</math> כווקטור השאלות. ''תשובה'' תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־<math>\mathbf b\Leftrightarrow\begin{pmatrix}b_1\\\vdots\\b_m\end{pmatrix}\in\{0,1\}^m</math> את וקטור התשובות. מההגדרות נובע ישירות ש־<math>\mathbf p\Leftrightarrow\mathbf b</math>. <math>\mathbf x</math> מוגדר כמו מקודם.
+''שאלה'' היא פסוק לוגי שאנחנו יכולים לבחור ותלוי בסוגים של תושבים. למשל, את השאלה "האם <math>X_2</math> אביר?" שמופנת ל־<math>X_1</math> נייצג בתור <math>X_1\leftrightarrow X_2</math>, ואת השאלה "<math>X_1</math>, האם 3=3?" בתור <math>X_1\leftrightarrow1=X_1</math>. נסמן כ־<math>n</math> את מספר התושבים ונניח שמותר לשאול עד <math>m</math> שאלות. נסמן <math>\mathbf q=\begin{pmatrix}Q_1\\\vdots\\Q_m\end{pmatrix}</math> כווקטור השאלות. ''תשובה'' תוגדר כערך בוליאני השקול לוגית לשאלה ששאלנו, ונסמן ב־<math>\mathbf r=\begin{pmatrix}r_1\\\vdots\\r_m\end{pmatrix}</math> את וקטור התשובות. מההגדרות נובע ש־<math>\mathbf q=\mathbf r</math>. <math>\mathbf x</math> מוגדר כמקודם, ואז ניתן לחשוב על <math>\mathbf q</math> כעל פונקציה <math>\mathbf x\mapsto\mathbf r</math>.
-'''דוגמה 4:''' <math>m=n=2</math> ואין עובדות. וקטור השאלות <math>\mathbf p\Leftrightarrow\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\end{pmatrix}</math> מאפשר לפתור את החידה. אם נניח, למשל, ש־<math>\mathbf b\Leftrightarrow\begin{pmatrix}0\\1\end{pmatrix}</math> אזי <math>\mathbf x\Leftrightarrow\begin{pmatrix}1\\0\end{pmatrix}</math>.
+:'''דוגמה 2.1:''' יש 3 תושבים (<math>n=3</math>), מותר לשאול עד 2 שאלות (<math>m=2</math>) ו־<math>X_3</math> טוען ש־<math>X_1</math> ו/או <math>X_2</math> אבירים, דהיינו <math>X_3\leftrightarrow(X_1\or X_2)=1</math>. וקטור השאלות <math>\mathbf q=\begin{pmatrix}X_1\leftrightarrow X_2\\X_1\end{pmatrix}</math>, לדוגמה, מאפשר לפתור את החידה כי תמיד מתקיים <math>\mathbf x=\begin{pmatrix}r_2\\r_1\leftrightarrow r_2\\r_2\or (r_1\leftrightarrow r_2)\end{pmatrix}=\begin{pmatrix}r_2\\r_1\leftrightarrow r_2\\r_1\rightarrow r_2\end{pmatrix}</math>.
-<!--
+בחידות מסוג זה נתונות עובדות, ונסמן כ־<math>S</math> את קבוצת הפתרונות <math>\mathbf x</math> המקיימים אותן. בד״כ המטרה היא למצוא <math>\mathbf q</math> חח״ע מ־<math>S</math>, כלומר למצוא שאלות שעבורן לכל וקטור תשובות <math>\mathbf r=\mathbf q(\mathbf x)</math> ניתן יהיה להסיק את וקטור הסוגים של התושבים, <math>\mathbf x=\mathbf q^{-1}(\mathbf r)</math>.
-נוכיח שאם לא נתונות עובדות אז <math>n\le m</math>: החידה פתירה, כלומר קיים וקטור <math>\mathbf p</math> כנ״ל כך שלכל <math>\mathbf b</math> ניתן להסיק את הפתרון. מספר האפשרויות ל
+יהי <math>k\in\mathbb N\cup\{0\}</math> המספר המינימלי כך ש־<math>|S|\le2^k</math>. נוכיח ש־<math>k\le m</math>: החידה פתירה, כלומר קיים וקטור שאלות <math>\mathbf q</math> חח״ע מ־<math>S</math>. <math>\mathbf q</math> היא פונקציה על קבוצת וקטורי התשובות ולפיכך יש <math>|S|</math> אפשרויות ל־<math>\mathbf r</math>. מאידך, <math>\mathbf q</math> מורכבת מ־<math>m</math> שאלות ולכל אחת יש עד 2 תשובות אפשריות, לכן יש עד <math>2^m</math> אפשרויות ל־<math>\mathbf r</math>, דהיינו <math>2^{k-1}<|S|\le2^m</math>. נקבל <math>k-1<m</math> ולבסוף <math>k\le m</math> כי <math>k,m\in\mathbb Z</math>. {{משל}}
+==== מערכת עובדות לינאריות ====
+במקרה זה <math>S=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf b\}</math>. אם שורות המטריצה <math>\mathbf A</math> תלויות לינארית ניתן למחוק כמה מהן (וגם את השורות המתאימות ב־<math>\mathbf b</math>) כך ששורותיה יהיו בת״ל ו־<math>S</math> לא תשתנה. לכן נניח בה״כ ששורות <math>\mathbf A</math> בת״ל.
-ושניתן להסתפק ב־<math>n</math> שאלות לינאריות
+:'''דוגמה 4.1:''' <math>n=4</math> ונתון
+{{left|<math>\begin{pmatrix}1&1&1&0\\0&0&0&0\\1&1&0&0\\0&0&1&0\end{pmatrix}\mathbf x=\begin{pmatrix}1\\0\\0\\1\end{pmatrix}</math>}}
+:השורה השנייה במערכת זו מיותרת והשורה הרביעית היא סכום השורה הראשונה והשלישית. לכן נמחק את שורות 2,4 ונקבל
+{{left|<math>\underbrace\begin{pmatrix}1&1&1&0\\1&1&0&0\end{pmatrix}_\mathbf A\mathbf x=\underbrace\begin{pmatrix}1\\0\end{pmatrix}_\mathbf b</math>}}
-במקרה שאין מרגלים ואין עובדות החידות האלה טריוויאליות – ניתן לשאול כל תושב "האם 1=1?" (או כל שאלה אחרת שהתשובה לה ידועה) ולהסיק את סוגו. זאת כמובן כאשר מספר השאלות שמותר לשאול הוא לכל הפחות מספר התושבים, מה שחייב להתקיים אם החידה פתירה: נניח שיש <math>n</math> תושבים ו־<math>m</math> שאלות וצ״ל ש־<math>n\le m</math>. לא נתונות עובדות על התושבים ולכן כל אחד מהם יכול להיות מכל סוג, כלומר יש <math>2^n</math> פתרונות אפשריים.
+נשים לב שלפי משפט רושה–קפלי <math>|S|=2^{n-\operatorname{rank}(\mathbf A)}=2^k</math> ולכן <math>\operatorname{rank}(\mathbf A)=n-k</math>. השורות של <math>\mathbf A</math> בת״ל ולכן יש לה <math>n-k</math> שורות.
-מספר הפתרונות האפשריים שווה גם ל־<math>2^n</math> ולכן <math>n=1=m</math>, כדרוש. עתה נניח ש־<math>n\le m</math> ל־<math>m,n</math> כלשהם ונוכיח שאם חידה עם <math>n+1</math> ו־
+כדי לפתור את החידה נבחר <math>\mathbf Q\in\{0,1\}^{k\times n}</math> כך ש־<math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}</math> מטריצה הפיכה, ואז <math>\mathbf q=\mathbf Q\mathbf x</math> ו־<math>\mathbf x=\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}^{-1}\begin{pmatrix}\mathbf b\\\mathbf r\end{pmatrix}</math>. לשם כך צריך להראות שקיימת <math>\mathbf Q</math> כנ״ל, אבל זה די טריוויאלי: השורות של <math>\mathbf A</math> בת״ל ולכן הן בסיס לתת־מרחב של <math>\{0,1\}^{1\times n}</math> ממימד <math>k</math>. נבחר בסיס כלשהו ל[http://en.wikipedia.org/wiki/Orthogonal_complement תת־מרחב המשלים האורתוגונלי] לו ונציב את איבריו כשורות מטריצה <math>\mathbf Q</math>. אזי <math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}\in\{0,1\}^{(n-k+k)\times n}=\{0,1\}^{n\times n}</math> מטריצה ריבועית ששורותיה בת״ל, כלומר היא הפיכה. {{משל}}
--->
+:'''דוגמה 4.2:''' עלינו למצוא את הסוגים של כל התושבים בדוגמה 4 במינימום שאלות, כלומר ב־<math>k=n-\operatorname{rank}(\mathbf A)=2</math> שאלות (הוכחה ש־<math>k</math> הוא המספר המינימלי הדרוש של שאלות – בהמשך). שני וקטורי שורה שאינם תלויים לינארית ב־<math>\begin{pmatrix}1&1&1&0\end{pmatrix},\begin{pmatrix}1&1&0&0\end{pmatrix}</math> הם לדוגמה <math>\begin{pmatrix}0&0&0&1\end{pmatrix},\begin{pmatrix}1&0&1&0\end{pmatrix}</math> ולכן <math>\mathbf q=\begin{pmatrix}X_4\\X_1\nleftrightarrow X_3\end{pmatrix}</math> וקטור שאלות מתאים. <math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}^{-1}=\begin{pmatrix}1&1&1&0\\1&1&0&0\\0&0&0&1\\1&0&1&0\end{pmatrix}^{-1}=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}</math> והפתרון הכללי הוא <math>\mathbf x=\begin{pmatrix}1&1&0&1\\1&0&0&1\\1&1&0&0\\0&0&1&0\end{pmatrix}\begin{pmatrix}1\\0\\\mathbf r\!\!\!\!\!\begin{matrix}&\\&\end{matrix}\end{pmatrix}</math>.
-== חידות עם מרגלים ==
+==== המספר המינימלי של שאלות ====
-<!---->
+נניח ש־<math>m</math> הוא המספר המינימלי של שאלות הדרוש לפתרון חידת שאלות נתונה ונרצה להוכיח ש־<math>m=k=\lceil\log_2(|S|)\rceil</math>: תהי <math>V=\{\mathbf x:\ \mathbf A\mathbf x=\mathbf 0\}</math> כך ש־<math>\mathbf A\in\{0,1\}^{(n-k)\times n}</math> מטריצה כרצוננו ששורותיה בת״ל. לכן <math>|V|=2^{n-\operatorname{rank}(\mathbf A)}=2^k</math> ובפרט קיימת פונקציה <math>f:S\to V</math> חח״ע. תהי <math>\mathbf Q\in\{0,1\}^{k\times n}</math> מטריצה כך ש־<math>\begin{pmatrix}\mathbf A\\\mathbf Q\end{pmatrix}</math> הפיכה ואז <math>\mathbf q':\mathbf v\mapsto\mathbf Q\mathbf v</math> חח״ע מ־<math>V</math>. נגדיר <math>\mathbf q=\mathbf q'\circ f</math> ולכן <math>\mathbf q</math> חח״ע מ־<math>S</math> והיא מורכבת מ־<math>k</math> שאלות, כלומר <math>k\ge m</math>. בעבר הוכחנו ש־<math>k\le m</math> ולכן <math>m=k</math>. {{משל}}
-=== חידות ללא שאלות ===
-<!---->
-==== פתרון כמערכת משוואות ====
-<!---->
-==== פתרון באמצעות ניחוש ====
-<!---->
-=== חידות עם שאלות ===
-<!---->
-== מקורות והשראות ==
-{{left|
-* [https://en.wikipedia.org/wiki/Knights_and_Knaves Knights and Knaves]
-* [https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever The Hardest Logic Puzzle Ever]
-* [https://en.wikipedia.org/wiki/Fuzzy_logic Fuzzy logic]
-* [https://en.wikipedia.org/wiki/Many-valued_logic Many-valued logic]
-* [https://en.wikipedia.org/wiki/Three-valued_logic Three-valued logic]
-}}
-<!-- סיבוכיות? -->

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

גרסה אחרונה מ־15:23, 6 באוגוסט 2013

תוכן עניינים

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

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

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

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

מערכת עובדות לינאריות

המספר המינימלי של שאלות

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים