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

שאלה 2 ילד קטן מקליד את 22 האותיות העבריות מ-א' עד ת' (ללא אותיות סופיות) בסדר אקראי, כך שכל אחת מ22- האותיות מופיעה בדיוק פעם אחת ברצף ההקלדה. א. מהי ההסתברות שבהקלדת האותיות א', ב' ו-ג' תופענה עד (וכולל) למקום העשירי? (שלוש האותיות לא חייבות להופיע במקומות סמוכים או בסדר מסוים). ב. מהי ההסתברות שברצף ההקלדה האותיות ד' ו-ה' תופענה לפני האותיות צ' ו-ק'? ג. מהי ההסתברות שברצף ההקלדה תופיע לפחות אחת משלוש המילים "נמל", "ספה" ו"רשת"?

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

פתרון: **מרחב ההסתברות** בכל הסעיפים הוא מרחב כל התמורות (סידורים) האפשריות של 22 האותיות. גודל מרחב המדגם הוא $|\Omega| = 22!$. כל תמורה היא בעלת הסתברות שווה, $\frac{1}{22!}$. ### סעיף א' אנו רוצים למצוא את ההסתברות שהאותיות א', ב', ו-ג' תופענה עד (וכולל) המקום העשירי. נפתור זאת בגישה **קומבינטורית**. במקום לספור את כלל הסידורים, נתמקד רק במיקומים של שלוש האותיות הספציפיות: א', ב', ג'. ישנן $\binom{22}{3}$ דרכים לבחור 3 מיקומים עבור האותיות א', ב', ג' מתוך 22 המיקומים האפשריים. מכיוון שהסידור הכללי אקראי, כל קבוצת מיקומים כזו היא שוות-הסתברות. המאורע הרצוי, $A$, הוא ששלוש האותיות הללו יופיעו במקומות שנמצאים בתוך עשרת המקומות הראשונים. מספר הדרכים לבחור 3 מיקומים מתוך 10 המקומות הראשונים הוא $\binom{10}{3}$. לכן, ההסתברות המבוקשת היא היחס בין מספר האפשרויות הרצויות לסך האפשרויות: $$ P(A) = \frac{\text{מספר הדרכים לבחור 3 מקומות מתוך ה-10 הראשונים}}{\text{מספר הדרכים לבחור 3 מקומות מתוך 22}} = \frac{\binom{10}{3}}{\binom{22}{3}} $$ נחשב את הערכים: $$ \binom{10}{3} = \frac{10!}{3!7!} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 10 \cdot 3 \cdot 4 = 120 $$ $$ \binom{22}{3} = \frac{22!}{3!19!} = \frac{22 \cdot 21 \cdot 20}{3 \cdot 2 \cdot 1} = 11 \cdot 7 \cdot 20 = 1540 $$ ההסתברות היא: $$ P(A) = \frac{120}{1540} = \frac{12}{154} = \frac{6}{77} $$ ### סעיף ב' אנו רוצים למצוא את ההסתברות שהאותיות ד' ו-ה' תופענה לפני האותיות צ' ו-ק'. נתמקד בסדר היחסי של ארבע האותיות הללו בלבד: ד', ה', צ', ק'. בשל האקראיות של סידור כל 22 האותיות, כל סדר יחסי של תת-קבוצה של אותיות הוא שווה-הסתברות. ישנם $4!$ סידורים יחסיים אפשריים לארבע האותיות ד', ה', צ', ק'. $$ 4! = 24 $$ המאורע הרצוי, $B$, הוא שהאותיות ד' ו-ה' מופיעות לפני צ' ו-ק'. זה אומר שבסידור היחסי של ארבע האותיות, שני המקומות הראשונים מאוכלסים על ידי ד' ו-ה' (בסדר כלשהו), ושני המקומות האחרונים מאוכלסים על ידי צ' ו-ק' (בסדר כלשהו). * מספר הדרכים לסדר את ד' ו-ה' בשני המקומות הראשונים הוא $2! = 2$. * מספר הדרכים לסדר את צ' ו-ק' בשני המקומות האחרונים הוא $2! = 2$. סה"כ, מספר הסידורים היחסיים הרצויים הוא $2! \cdot 2! = 4$. ההסתברות המבוקשת היא היחס בין מספר הסידורים הרצויים לסך הסידורים האפשריים: $$ P(B) = \frac{2! \cdot 2!}{4!} = \frac{4}{24} = \frac{1}{6} $$ ### סעיף ג' אנו רוצים למצוא את ההסתברות שתופיע לפחות אחת מהמילים "נמל", "ספה", "רשת". נגדיר את המאורעות הבאים: * $A_1$: המילה "נמל" מופיעה ברצף. * $A_2$: המילה "ספה" מופיעה ברצף. * $A_3$: המילה "רשת" מופיעה ברצף. אנו מחפשים את $P(A_1 \cup A_2 \cup A_3)$. נשתמש ב**עקרון ההכלה וההפרדה**: $$ P(A_1 \cup A_2 \cup A_3) = \sum_{i=1}^3 P(A_i) - \sum_{1 \le i < j \le 3} P(A_i \cap A_j) + P(A_1 \cap A_2 \cap A_3) $$ נשים לב שכל האותיות בשלוש המילים הן שונות זו מזו. **חישוב $P(A_i)$**: כדי לחשב את $P(A_1)$, נתייחס לרצף "נמל" כאל "בלוק" אחד. כעת עלינו לסדר $22-3+1 = 20$ פריטים (19 האותיות הנותרות + הבלוק "נמל"). מספר התמורות הללו הוא $20!$. לכן, $P(A_1) = \frac{20!}{22!} = \frac{1}{22 \cdot 21} = \frac{1}{462}$. מסימטריה, $P(A_1) = P(A_2) = P(A_3)$. לכן, $\sum P(A_i) = 3 \cdot \frac{20!}{22!}$. **חישוב $P(A_i \cap A_j)$**: כדי לחשב את $P(A_1 \cap A_2)$, נתייחס ל"נמל" ול"ספה" כשני בלוקים נפרדים. יש לסדר $22-3-3+2 = 18$ פריטים. מספר התמורות הוא $18!$. לכן, $P(A_1 \cap A_2) = \frac{18!}{22!} = \frac{1}{22 \cdot 21 \cdot 20 \cdot 19}$. מסימטריה, $P(A_1 \cap A_2) = P(A_1 \cap A_3) = P(A_2 \cap A_3)$. לכן, $\sum P(A_i \cap A_j) = 3 \cdot \frac{18!}{22!}$. **חישוב $P(A_1 \cap A_2 \cap A_3)$**: כדי לחשב את $P(A_1 \cap A_2 \cap A_3)$, נתייחס ל"נמל", "ספה", "רשת" כשלושה בלוקים נפרדים. יש לסדר $22-3-3-3+3 = 16$ פריטים. מספר התמורות הוא $16!$. לכן, $P(A_1 \cap A_2 \cap A_3) = \frac{16!}{22!}$. **סיכום**: נציב את כל החלקים בנוסחת ההכלה וההפרדה: $$ P(A_1 \cup A_2 \cup A_3) = 3 \cdot \frac{20!}{22!} - 3 \cdot \frac{18!}{22!} + \frac{16!}{22!} $$ ניתן לבטא את התשובה גם כך: $$ P(\text{לפחות מילה אחת}) = \frac{3}{22 \cdot 21} - \frac{3}{22 \cdot 21 \cdot 20 \cdot 19} + \frac{1}{22 \cdot 21 \cdot 20 \cdot 19 \cdot 18 \cdot 17} $$ $$ = \frac{3}{462} - \frac{3}{175560} + \frac{1}{53721360} $$ זוהי התשובה הסופית. $\blacksquare$