שאלת מבחן בהסתברות - האוניברסיטה הפתוחה 2022 - קומבינטוריקה

2 גברים, ששמותיהם אבי ובני, ו- $n - 2$ נשים מתיישבים באקראי בשורה. הניחו כי $n \geq 4$. יהיו: $X$ = מספר הנשים שיושבות ליד אבי $Y$ = מספר הנשים שיושבות ליד בני א. (6 נק') מיצאו את פונקציית ההסתברות של $X$. ב. (6 נק') עבור $n = 6$, חשבו את השונות של $X$. ג. (6 נק') האם $X$ ו- $Y$, המוגדרים בתחילת השאלה, בלתי-תלויים זה בזה? ד. (7 נק') חשבו את: 1. $P\{X = 0, Y = 1\}$ 2. $P\{X = 1, Y = 2\}$ הערה: רק בסעיף ב מניחים כי $n = 6$. ביתר הסעיפים הכוונה היא לערך כללי של $n$.

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

פתרון: מרחב המדגם $\Omega$ הוא קבוצת כל התמורות האפשריות של $n$ האנשים בשורה. גודל מרחב המדגם הוא $|\Omega|=n!$. כל סידור הוא בעל הסתברות שווה. **א. פונקציית ההסתברות של $X$** $X$ הוא המשתנה המקרי הסופר את מספר הנשים היושבות ליד אבי. $X$ יכול לקבל את הערכים $0, 1, 2$. **חישוב $P(X=2)$**: כדי ש- $X=2$, אבי חייב לשבת בין שתי נשים. 1. נבחר 2 נשים מתוך $n-2$ הנשים, ונושיב אותן משני צדדיו של אבי. יש $P(n-2, 2) = (n-2)(n-3)$ דרכים לעשות זאת (הסדר משנה). 2. נתייחס לקבוצה (אישה, אבי, אישה) כאל "בלוק" אחד. כעת עלינו לסדר בלוק זה יחד עם $n-3$ האנשים הנותרים (בני ו-$n-4$ נשים). ישנם $n-2$ "פריטים" לסדר, ולכן $(n-2)!$ סידורים אפשריים. מספר הסידורים המקיימים $X=2$ הוא $(n-2)(n-3) \times (n-2)!$. לכן, ההסתברות היא: $$P(X=2) = \frac{(n-2)(n-3)(n-2)!}{n!} = \frac{(n-2)(n-3)}{n(n-1)}$$ **חישוב $P(X=0)$**: כדי ש- $X=0$, אף אישה לא יושבת ליד אבי. מכיוון שיש רק גבר אחד נוסף (בני), הדבר ייתכן רק אם אבי יושב בקצה השורה, ובני יושב לידו. 1. ישנן 2 אפשרויות למקם את ה"בלוק" (אבי, בני) בקצה: (אבי, בני, ...) או (..., בני, אבי). 2. בכל אחת מהאפשרויות, יש לסדר את $n-2$ הנשים ב-$n-2$ המקומות הנותרים. יש $(n-2)!$ דרכים לעשות זאת. מספר הסידורים המקיימים $X=0$ הוא $2 \times (n-2)!$. לכן, ההסתברות היא: $$P(X=0) = \frac{2(n-2)!}{n!} = \frac{2}{n(n-1)}$$ **חישוב $P(X=1)$**: ההסתברות $P(X=1)$ משלימה ל-1 את סכום ההסתברויות שחישבנו: $$P(X=1) = 1 - P(X=0) - P(X=2) = 1 - \frac{2}{n(n-1)} - \frac{(n-2)(n-3)}{n(n-1)}$$ $$= \frac{n(n-1) - 2 - (n^2-5n+6)}{n(n-1)} = \frac{n^2-n-2-n^2+5n-6}{n(n-1)} = \frac{4n-8}{n(n-1)} = \frac{4(n-2)}{n(n-1)}$$ לסיכום, פונקציית ההסתברות של $X$ היא: $$ P(X=k) = \begin{cases} \frac{2}{n(n-1)} & k=0 \\ \frac{4(n-2)}{n(n-1)} & k=1 \\ \frac{(n-2)(n-3)}{n(n-1)} & k=2 \\ 0 & \text{אחרת} \end{cases} $$ **ב. שונות $X$ עבור $n=6$** נציב $n=6$ בפונקציית ההסתברות: $P(X=0) = \frac{2}{6 \cdot 5} = \frac{2}{30}$ $P(X=1) = \frac{4(6-2)}{6 \cdot 5} = \frac{16}{30}$ $P(X=2) = \frac{(6-2)(6-3)}{6 \cdot 5} = \frac{4 \cdot 3}{30} = \frac{12}{30}$ (נשים לב שסכום ההסתברויות הוא $\frac{2+16+12}{30}=1$). נחשב את **התוחלת** של $X$: $$E[X] = \sum_{k=0}^{2} k \cdot P(X=k) = 0 \cdot \frac{2}{30} + 1 \cdot \frac{16}{30} + 2 \cdot \frac{12}{30} = \frac{16+24}{30} = \frac{40}{30} = \frac{4}{3}$$ נחשב את התוחלת של $X^2$: $$E[X^2] = \sum_{k=0}^{2} k^2 \cdot P(X=k) = 0^2 \cdot \frac{2}{30} + 1^2 \cdot \frac{16}{30} + 2^2 \cdot \frac{12}{30} = \frac{16+48}{30} = \frac{64}{30} = \frac{32}{15}$$ ה**שונות** היא: $$V(X) = E[X^2] - (E[X])^2 = \frac{32}{15} - \left(\frac{4}{3}\right)^2 = \frac{32}{15} - \frac{16}{9} = \frac{3 \cdot 32 - 5 \cdot 16}{45} = \frac{96-80}{45} = \frac{16}{45}$$ **ג. אי-תלות המשתנים $X$ ו-$Y$** המשתנים $X$ ו-$Y$ **תלויים** זה בזה. כדי להוכיח זאת, מספיק להראות דוגמה נגדית אחת שבה $P(X=i, Y=j) \neq P(X=i)P(Y=j)$. נבחן את המקרה $n=4$. במקרה זה יש 2 גברים (אבי ובני) ו-2 נשים ($W_1, W_2$). פונקציית ההסתברות של $X$ (ומסימטריה גם של $Y$) עבור $n=4$ היא: $P(X=2) = \frac{(4-2)(4-3)}{4 \cdot 3} = \frac{2}{12} = \frac{1}{6}$ $P(Y=0) = P(X=0) = \frac{2}{4 \cdot 3} = \frac{2}{12} = \frac{1}{6}$ נחשב את ההסתברות המותנית $P(Y=0|X=2)$. המאורע $X=2$ פירושו שאבי יושב בין שתי הנשים. הסידורים האפשריים היחידים הם תמורה של הבלוק $(W_1, A, W_2)$ ושל בני. הסידורים הם: $(W_1,A,W_2),B$ ו-$B,(W_1,A,W_2)$ (וכן עם החלפת הנשים). בכל סידור כזה, בני בהכרח יושב ליד אחת הנשים. לדוגמה, בסידור $B,W_1,A,W_2$, שכנו היחיד של בני הוא $W_1$. לכן, מספר הנשים שיושבות ליד בני הוא 1, כלומר $Y=1$. מכאן, אם $X=2$, אז $Y$ חייב להיות 1. לכן $P(Y=0|X=2)=0$. אבל $P(Y=0) = 1/6$. מאחר ש-$P(Y=0|X=2) \neq P(Y=0)$, המשתנים $X$ ו-$Y$ תלויים. $\blacksquare$ **ד. חישוב הסתברויות משותפות** 1. **$P(X=0, Y=1)$** המאורע $X=0$ מתרחש כאשר אבי יושב בקצה השורה, ובני לידו (כפי שראינו בסעיף א'). ישנן שתי תצורות כלליות: א) $(A, B, P_3, \dots, P_n)$: אבי במקום 1, בני במקום 2. ב) $(P_1, \dots, P_{n-2}, B, A)$: בני במקום $n-1$, אבי במקום $n$. נבחן את שכניו של בני בכל תצורה. בתצורה א), שכניו של בני הם אבי (גבר) והאדם במקום 3. מכיוון שכל שאר $n-2$ האנשים הם נשים, האדם במקום 3 הוא בהכרח אישה. לכן, לבני יש בדיוק אישה אחת שיושבת לידו, כלומר $Y=1$. בתצורה ב), שכניו של בני הם אבי (גבר) והאדם במקום $n-2$. גם כאן, האדם במקום $n-2$ הוא בהכרח אישה, ולכן $Y=1$. במילים אחרות, המאורע $X=0$ גורר את המאורע $Y=1$. לכן, המאורע $\{X=0, Y=1\}$ זהה למאורע $\{X=0\}$. $$P(X=0, Y=1) = P(X=0) = \frac{2}{n(n-1)}$$ 2. **$P(X=1, Y=2)$** אנו מחפשים את מספר הסידורים שבהם $Y=2$ (בני יושב בין שתי נשים) וגם $X=1$ (אבי יושב ליד אישה אחת בדיוק). - נתחיל מהתנאי $Y=2$. נבחר 2 נשים מתוך $n-2$ שיישבו ליד בני. יש $P(n-2, 2) = (n-2)(n-3)$ דרכים לעשות זאת. ניצור את ה"בלוק" $U_B = (\text{אישה, בני, אישה})$. - כעת יש לסדר את הבלוק $U_B$, את אבי, ואת $n-4$ הנשים הנותרות. אלו הם $1+1+(n-4) = n-2$ "פריטים". - ננתח את סביבתו של אבי בסידור של $n-2$ הפריטים הללו. כל פריט שאינו אבי ($U_B$ או אישה בודדת) מתחיל ונגמר באישה. לכן, אם אבי ימוקם בין שני פריטים אחרים, הוא יהיה מוקף בשתי נשים, מה שיגרום ל-$X=2$. - הדרך היחידה שבה $X=1$ היא אם לאבי יש רק שכן אחד בסידור של הפריטים. זה קורה אם ורק אם אבי ממוקם באחד משני הקצוות של שורת הפריטים. במקרה זה, שכנו היחיד יהיה או הבלוק $U_B$ או אישה, ובכל מקרה הוא יישב ליד אישה אחת בדיוק. - לכן, עלינו לספור את הסידורים של $n-2$ הפריטים שבהם אבי נמצא בקצה. - מספר הדרכים לבחור וליצור את הבלוק $U_B$ הוא $(n-2)(n-3)$. - מספר הדרכים לסדר את $n-2$ הפריטים כך שאבי בקצה: יש 2 אפשרויות לקצה, ולאחר מיקום אבי, יש $(n-3)!$ דרכים לסדר את $n-3$ הפריטים הנותרים. כלומר $2(n-3)!$ סידורים. - מספר הסידורים הכולל המקיים את שני התנאים הוא: $(n-2)(n-3) \times 2(n-3)!$. - ההסתברות היא: $$P(X=1, Y=2) = \frac{2(n-2)(n-3)(n-3)!}{n!} = \frac{2(n-2)(n-3)}{n(n-1)(n-2)} = \frac{2(n-3)}{n(n-1)}$$