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

בכיתה יש 10 ילדים, ממוספרים מ 1 עד 10, ויש 20 כיסאות ממוספרים מ 1 עד 20. הילדים, לפי הסדר, מתיישבים אחד אחד, כל אחד בכיסא אקראי פנוי. (בהתחלה ילד מספר 1, יושב בכיסא אקראי, אחרי זה ילד מספר 2 יושב בכיסא אקראי מתוך ה 19 כיסאות הפנויים, וכך הלאה עד שכל הילדים התיישבו). אם ילד מספר $i$ התיישב בכיסא $i$, אז נגיד שהילד התיישב במקום הנכון. נסמן ב $X$ את מספר הילדים שהתיישבו במקום נכון. סעיף א: (10 נק') הוכח שההסתברות שהילד ה $i$ יישב במקום הנכון היא $\frac{1}{20}$. סעיף ב: (5 נק') חשבו את $E[X]$. סעיף ג: (10 נק') חשבו את $Var[X]$.

רמז: חשבו על מרחב המדגם של כל הסידורים האפשריים של 10 ילדים ב-20 כיסאות. השתמשו במשתני אינדיקטור ובליניאריות התוחלת כדי לחשב את התוחלת והשונות.

פתרון: ### סעיף א: הוכחת ההסתברות כדי לחשב את ההסתברות שהילד ה-$i$ יישב במקום הנכון (כלומר, בכיסא מספר $i$), נגדיר את **מרחב ההסתברות** שלנו. התהליך הוא ש-10 ילדים מתיישבים בזה אחר זה ב-20 כיסאות. לילד הראשון יש 20 אפשרויות, לשני 19, וכן הלאה עד לילד העשירי שלו יש 11 אפשרויות. לכן, מספר הדרכים השונות שבהן כל הילדים יכולים להתיישב הוא: $|\Omega| = 20 \cdot 19 \cdot \ldots \cdot (20-10+1) = 20 \cdot 19 \cdot \ldots \cdot 11 = P(20, 10) = \frac{20!}{(20-10)!} = \frac{20!}{10!}$ אלו הן כל התוצאות האפשריות במרחב המדגם, ואנו מניחים שלכל תוצאה כזו יש הסתברות שווה. כעת, נחשב את מספר התוצאות שבהן ילד מספר $i$ יושב בכיסא מספר $i$. נקבע את מקומו של ילד $i$ בכיסא $i$. כעת נותרו 9 ילדים ו-19 כיסאות פנויים. מספר הדרכים לסדר את 9 הילדים הנותרים ב-19 הכיסאות הפנויים הוא: $N(A_i) = P(19, 9) = \frac{19!}{(19-9)!} = \frac{19!}{10!}$ ההסתברות שילד $i$ יישב בכיסא $i$, המסומנת $P(A_i)$, היא היחס בין מספר התוצאות הרצויות למספר התוצאות הכולל: $P(A_i) = \frac{N(A_i)}{|\Omega|} = \frac{P(19, 9)}{P(20, 10)} = \frac{\frac{19!}{10!}}{\frac{20!}{10!}} = \frac{19!}{20!} = \frac{1}{20}$ התוצאה אינה תלויה ב-$i$, ולכן ההסתברות שילד כלשהו (מ-1 עד 10) יישב במקומו הנכון היא $\frac{1}{20}$. $\blacksquare$ ### סעיף ב: חישוב התוחלת נסמן ב-$X$ את מספר הילדים שהתיישבו במקום הנכון. $X$ הוא **משתנה מקרי בדיד**. ניתן לבטא את $X$ כסכום של משתנים מקריים אינדיקטורים: $X = \sum_{i=1}^{10} I_i$ כאשר $I_i$ הוא **משתנה אינדיקטור** המקבל ערך 1 אם ילד $i$ יושב בכיסא $i$, ו-0 אחרת. כלומר, $I_i = 1$ אם המאורע $A_i$ מתרחש. נשתמש בתכונת **ליניאריות התוחלת**: $E[X] = E[\sum_{i=1}^{10} I_i] = \sum_{i=1}^{10} E[I_i]$ התוחלת של משתנה אינדיקטור היא ההסתברות למאורע שהוא מייצג: $E[I_i] = 1 \cdot P(I_i=1) + 0 \cdot P(I_i=0) = P(A_i)$ מסעיף א', אנו יודעים כי $P(A_i) = \frac{1}{20}$ לכל $i=1, \ldots, 10$. לכן, התוחלת של $X$ היא: $E[X] = \sum_{i=1}^{10} \frac{1}{20} = 10 \cdot \frac{1}{20} = \frac{1}{2}$ ### סעיף ג: חישוב השונות כדי לחשב את ה**שונות** של $X$, נשתמש בנוסחה $Var(X) = E[X^2] - (E[X])^2$. את $E[X]$ כבר חישבנו, $E[X] = \frac{1}{2}$, ולכן $(E[X])^2 = \frac{1}{4}$. נותר לחשב את $E[X^2]$. $X^2 = (\sum_{i=1}^{10} I_i)^2 = (I_1 + I_2 + \ldots + I_{10})^2 = \sum_{i=1}^{10} I_i^2 + \sum_{i \neq j} I_i I_j$ נשתמש בליניאריות התוחלת שוב: $E[X^2] = E[\sum_{i=1}^{10} I_i^2 + \sum_{i \neq j} I_i I_j] = \sum_{i=1}^{10} E[I_i^2] + \sum_{i \neq j} E[I_i I_j]$ ראשית, עבור משתנה אינדיקטור, $I_i^2 = I_i$, ולכן $E[I_i^2] = E[I_i] = \frac{1}{20}$. הסכום הראשון הוא: $\sum_{i=1}^{10} E[I_i^2] = 10 \cdot \frac{1}{20} = \frac{1}{2}$. כעת, נחשב את $E[I_i I_j]$ עבור $i \neq j$. זהו ערך **השונות המשותפת** (בתוספת מכפלת התוחלות). מכיוון ש-$I_i I_j$ הוא גם משתנה אינדיקטור (הוא 1 אם גם ילד $i$ וגם ילד $j$ יושבים במקומם), תוחלתו היא ההסתברות ששני המאורעות יקרו יחד: $E[I_i I_j] = P(A_i \cap A_j)$ במאורע $A_i \cap A_j$, ילד $i$ יושב בכיסא $i$ וילד $j$ יושב בכיסא $j$. נקבע את שני הילדים הללו במקומותיהם. נותרו 8 ילדים ו-18 כיסאות פנויים. מספר הדרכים לסדר את 8 הילדים הנותרים ב-18 הכיסאות הפנויים הוא $P(18, 8) = \frac{18!}{10!}$. לכן, ההסתברות היא: $P(A_i \cap A_j) = \frac{P(18, 8)}{P(20, 10)} = \frac{\frac{18!}{10!}}{\frac{20!}{10!}} = \frac{18!}{20!} = \frac{1}{20 \cdot 19} = \frac{1}{380}$ בסכום $\sum_{i \neq j} E[I_i I_j]$, יש $10 \times 9 = 90$ זוגות סדורים $(i, j)$ כך ש-$i \neq j$. הסכום השני הוא: $\sum_{i \neq j} E[I_i I_j] = 90 \cdot \frac{1}{380} = \frac{9}{38}$. נחבר את שני הסכומים כדי למצוא את $E[X^2]$: $E[X^2] = \frac{1}{2} + \frac{9}{38} = \frac{19}{38} + \frac{9}{38} = \frac{28}{38} = \frac{14}{19}$ לבסוף, נחשב את השונות: $Var(X) = E[X^2] - (E[X])^2 = \frac{14}{19} - (\frac{1}{2})^2 = \frac{14}{19} - \frac{1}{4} = \frac{56 - 19}{76} = \frac{37}{76}$