יומי הולדת

[Jjack]

יומי הולדת

לא ראיתי כאן בעיות בהסתברות (חוץ מכמה הוצאות גרביים או כפפות מארונות) אז הנה: מה מספר מינימלי של אנשים שנמצאים במקום אחד שיוכלו להגיד שיש סיכוי יותר מ- 50% שיש ביניהם 2 אנשים עם תאריך לידה זהה (רק תאריך ללא שנה - למשל שניהם ב-1 לאפריל)? למשל, ברור ש-179 מתאים לפי עיקרון השובך. אבל האם גם 100 יתאים? האם מספר אף יותן קטן יתאים? רמז : ניתן לפתור רק דרך חישובי הסתברויות.

 

[רוברט בנאי]

אני יודע שזה די ../images/Emo163.gif מצדי, אבל...

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

 

[snogal]

עקרון שובך היונים:

גרסה ראשונה: בהנתן n+1 יונים שיש להניח אותם ב n שובכים אזי ישנה לפחות קופסה אחת שמכילה לפחות 2 יונים. דוגמה עבור 8 אנשים לפחות שניים נולדו באותו יום בשבוע. גרסה מורחבת: בהנתן n*r+1 יונים שיש להניח אותם ב n תאים , אזי יש לפחות תא אחד שיש בו לפחות r+1 יונים. גרסה קצת אחרת: בהנתן ש q1,q2,..qn מספרים שלמים חיוביים, אזי אם (q1+q2+..+qn -(n-1 איברים מוכנסים ל n תאים אזי מתקיים שלפחות תא אחד תא i מכיל לפחות qi איברים. שימוש נחמד לעקרון שובך היונים: בהנתן m מספרים שלמים (לאו דווקא שונים) a1,a2,..,am , אזי קיימים מספרים שלמים k,l כך ש

0≤k<l≤m​

ומתקיים (a(k+1)+a(k+2)+..+a(l מתחלק ב m ללא שארית. למשל בסדרה 3,3,5,2 עבור k=1 ו l=3 מתקיים 3+5=8 שמתחלק ב 4 ללא שארית. עבור m-1 איברים הטענה אינה נכונה למשל עבור הסדרה 1,1,1..,1 יש m-1 אחדים, לא נוכל למצו תת דברה (אפילו כל הסדרה עצמה) כך שהסכום מתחלק ב m ללא שארית. הוכחה: נסמן:

s(0)=0 s(1)=a1 s(2)=a1+s2 .... s(m)=a1+a2+..+am​

סה"כ קיבלנו m+1 סדרות אלו היונים. התאים (שובכים) יהיו שאטריות החלוקה של הסדרה ב m. סה"כ יש לנו m אפשרויות כאלו 1,0,...,m-1 , ולכן יש לנו m תאים. לפי עקרון שובך היונים יהיה לנו לפחות תא אחד שבו יש 2 יונים, כלומר 2 סדרות (שונות) בעלות אותה שארית חלוקה ב m נסמן אותם ב s(l) and s(k) w כאשר l>k. לכן הסדרה (s(l)-s(k)=a(k+1)+a(k+2)+..+a(l מתחלקת ב m ללא שארית (כי שארית החלוקה של שתי הסדרות ב m היתה שווה).

 

[אמיר96]

../images/Emo62.gif

אני אראה את הדרך לעשות את זה, ומכיוון שאין לי את המחשבון המתאים אני רק אתן הערכה. צריך לקחת בחשבון כל זוג של אנשים. כמה זוגות אפשריים יש? נניח שיש לי 10 אנשים אז לכל איש יש 9 פרטנרים ובסך הכל 90, אבל בגלל שיש כפילות עבור כל זוג, מחלקים ב2 ומקבלים 45 זוגות. באופן כללי יש

n(n-1)/2​

זוגות אפשריים. אני רוצה לחשב את האפשרות ההפוכה, שלא תהיה התאמה בין אף זוג. לכל זוג ההסתברות להתאמה היא 364\365 ולכן ההסתברות הכוללת היא:

(364/365)^(n(n-1)/2)​

וצריך למצוא את הN הנמוך ביותר שההסתברות הזו קטנה מ50.אין לי את המחשבון לעשות את זה בצורה מסודרת, אבל קיבלתי שהחזקה צריכה להיות בערך 256, וזה אומר שN הוא בערך 22 או 23.

 

[אמיר96]

אני כבר לא בטוח

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

 

[אמיר96]

נסיון נוסף

שוב נחשב מה ההסתברות שלא יהיה יום הולדת משותף. עבור 2 זה 364\365 עבור 3 זה

(364/365)*(363/365)​

עבור N זה

(364/365)*(363/365)*....*((366-N)/365) וכל זה צריך להיות פחות מחצי. לפי החישוב שלי זה יוצא 23. מוזר שזה יצא כמו החישוב הקודם אז אולי בכל זאת הוא היה נכון?​

 

[snogal]

זה הפתרון הנכון אבל

רק תשים לב שהפתרון הדרוש הוא המאורע המשלים למה שחישבת (במקרה הנ"ל זה לא משמעותי כי ההסתברות לכל מאורע תהיה 0.5) 23 זו בערך התשובה. אגב נדמה לי שעבור N בערך בסביבות ה 40-50 (לא זוכר במדויק אולי קצת יותר) ההסתברות היא גבוהה מאד (קרובה ל 100)

 

[snogal]

קרובה ל 1 , כמובן.

 

[Jjack]

לכולם ../images/Emo127.gif ../images/Emo70.gif ../images/Emo127.gif זה היה מהיר

 

[Jjack]

בהקשר זה, מי יודע איפה בספרות השתמש

ו בעובדה זאת ?