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

תמונה: שאטרסטוק  

מה שהיא לא ידעה זה שכל אחד מחמשת אחייניה שונא סוג שוקולד אחד:

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

דודה שושנה לא זוכרת איזה שוקולד נמצא באיזו אריזה.

כמה אפשרויות יש לחלק את חמשת השוקולדים כך שאף ילד לא יקבל את השוקולד שהוא שונא? מהו הסיכוי שאף ילד לא יקבל את השוקולד שהוא שונא?

חשיבה מתוקה,

סבינה



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

13 תגובות

  • רמי

    פתרון לא רקורסיבי

    פתרון מעניין של Simon Plouffe שמצאתי באתר [https://oeis.org/A000166] : f(n) = {n!/e} (*) הביטוי בסוגריים המסולסלים מעוגל לשלם הקרוב ביותר : {5.6}=6 , {6.4}=6
    (*) e הוא קבוע אוילר ששווה בקרוב 2.71828

  • מומחה מצוות מכון דוידסוןסבינה

    derangements

    מעניין! הנוסחה בסוגריים היא נוסחת קירוב. הקירוב טוב יותר ככול ש-n גדול יותר. מעניין לדעת כיצד מגיעים לנוסחה זו....מילת הקסם היא "derangement". כל הכבוד לכל אלה שפתחו את בעיית השוקולדים הנ"ל בלי להכיר את התורה המתמטית המתאימה.

  • רמי

    נוסחת פתרון שונה

    נסמן את מספר האפשרויות לחלוקת N שוקולדים כך שאף ילד לא יקבל את השוקולד שהוא שונא ע"י הפונקציה f(N) . מספר כל האפשרויות הוא עצרת של מספר השוקולדים/ילדים !N (120=5! בחידה). 1) מספר המצבים בו בדיוק ילד אחד מקבל שוקולד שהוא שונא הוא מספר המצבים בו יש (N-1) ילדים שמקבלים שוקולד שהם לא שונאים, ואחד מקבל שוקולד שהוא שונא.
    כלומר בוחרים ילד אחד מ N הילדים ומספר האפשרויות של שאר N-1 הילדים לקבל שהם לא שונאים הוא החידה עצמה עבור הערך N-1.
    נסמן את מספר האפשרויות לבחירת i מתוך N ע"י (i of N)
    כלומר עבור בדיוק ילד אחד הערך הוא f(N-1)*(1 of N)
    (f(5-1)*(1 of 5)=9*5=45) 2) מספר המצבים בהם בדיוק 2 ילדים מקבלים שוקולד שהם שונאים הוא מספר המצבים לבחירת 2 ילדים מתוך (N) ילדים שמקבלים שוקולד שהם שונאים, ושאר (N-2) הילדים מקבלים שוקולד שהם אוהבים. וזאת החידה עבור N-2 ילדים.
    ולכן במקרה זה f(N-2)*(2 of N)
    (f(5-2)*(2 of 5)=2*10=20)
    :
    :
    i) מספר המצבים בהם בדיוק i ילדים מקבלים שוקולד שהם שונאים הוא מספר המצבים לבחירת i ילדים מתוך (N) ילדים שמקבלים שוקולד שהם שונאים, ושאר (N-i) הילדים מקבלים שוקולד שהם אוהבים. וזאת החידה עבור N-i ילדים.
    ולכן במקרה זה f(N-i)*(i of N)
    :
    N) יש רק מקרה אחד בו כולם מקבלים שוקולד שאינם אוהבים אם נחסיר מסה"כ האפשרויות (!N) את האפשרויות הלא טובות שהן סכום כל הנ"ל עבור i=1 ועד i=N , נקבל את התוצאה f(N) . ערכי בסיס הרקורסיה :
    נסמן 1=:(0)f וגם 0=:(1)f
    אפשר לבדוק כי 1=(2)f וסה"כ :
    44=120-76={1+10+20+45}-!5=(5)f

  • מומחה מצוות מכון דוידסוןסבינה

    יפה מאוד

    יפה מאוד!
    באיזו משתי השיטות (לפי רמי או לפי אוהד ניר) הייתם בוחרים אילו היו לדודה הרבה יותר מחמישה שוקולדים, נגיד 10 או 50?
    האם יש עוד דרך לפתרון (בנוסף לדרכים של רמי ושל אוהד ניר)?

  • אוהד ניר

    תשובה

    המספר !50 הוא עצום, וקשה מאוד לחשב אותו ללא מחשבון, וגם אם נשתמש במחשבון - אז המחשבון לא יציג אותו באופן מדויק, אלא רק מקורב - הסדר גודל יהיה נכון, אבל בהחלט ייתכן כי ספרת היחידות לא תהיה נכונה, זה חלק מהקירובים שמחשבים עושים על מספרים עצומים...
    ולכן, לדעתי, במספרים גדולים מומלץ להשתמש בשיטה של נוסחת הנסיגה, כי אז לא מגיעים למספרים עצומים - כי אין שימוש בעצרת, ניתן גם לכתוב לולאה קצרה במחשב אם סיבוכיות לינארית O(n) שתפתור בזמן קצר עבור כל מספר n.

  • אוהד ניר

    המשך תשובה

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

  • אוהד ניר

    המשך התשובה, חידוד הנקודה

    הכוונה היא שכאשר משתמשים במחשב כדי לחסר מספר עצום במספר עצום, והתוצאה היא מספר קטן מאוד (נגיד בתחום ~ 0-100), אז מקבלים שטויות.

  • מומחה מצוות מכון דוידסוןסבינה

    דרכי הפתרון השונות

    אני התכוונתי לשאלה האם יש דרך פתרון בה אין צורך לחשב את הפתרון עבור כל מספר קטן מהמספר הנתון (מספר הילדים ומספר השוקולדים, 5, 10 או 50).
    האם יש דרך לא ריקורסיבית?
    לגבי דיוק המחשבים/המשחבונים: תמיד נגיע למספרים באותו סדר הגודל, לא נראה לי שיש שיטה אחת שתיתן תוצאות מדויקות יותר משיטה אחרת.

  • אוהד ניר

    הסבר הפתרון

    זאת בעיה בקומבינטוריקה שקל יחסית לפתור בעזרת שימוש בנוסחת נסיגה.
    נניח שיש n ילדים והפתרון שלנו הוא An.
    לילד הראשון יש n-1 אפשרויות לחלק שוקולד.
    אבל מה לגבי הילד השני, אם השוקולד שלקח הילד הראשון זה לא השוקולד שהילד השני שונא, אז בעצם קיבלנו את אותה הבעיה עבור n-1 ילדים, ולכן הפתרון שלה יהיה An-1.
    אבל אם השוקולד שלקח הילד הראשון זה כן השוקולד שהילד השני שונא, אז בעצם קיבלנו את אותה הבעיה עבור n-2 ילדים, ולכן הפתרון שלה יהיה An-2.
    ולכן, הפתרון An שווה לחיבור הפתרונות An-1+An-2 והכפלת התוצאה ב- n-1.
    וקיבלנו את נוסחת הנסיגה הבאה:
    An = (n-1)*(An-1+An-2)
    מזכיר קצת את נוסחת פיבונצ'י למעט ההכפלה ב- n-1... - מספר האפשרויות לחלק שוקולדים ל- 2 ילדים שכל אחד מהם לא אוהב שוקולד אחד מתוכם, וזה לא אותו השוקולד, שווה לאפשרות אחת.
    - מספר האפשרויות לחלק שוקולדים ל- 3 ילדים שכל אחד מהם לא אוהב שוקולד אחד מתוכם, וזה לא אותו השוקולד, שווה לשתי אפשרויות.
    - ולכן, מספר האפשרויות לחלק שוקולדים ל- 4 ילדים שכל אחד מהם לא אוהב שוקולד אחד מתוכם, וזה לא אותו השוקולד, שווה ל:
    3*(1+2)=9
    - ובמקרה שלנו, מספר האפשרויות לחלק שוקולדים ל- 5 ילדים שכל אחד מהם לא אוהב שוקולד אחד מתוכם, וזה לא אותו השוקולד, שווה ל:
    4*(9+2)=44

  • מומחה מצוות מכון דוידסוןסבינה

    הסבר יפה מאוד!

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

  • אוהד ניר

    פתרון

    44=11*4

  • מומחה מצוות מכון דוידסוןסבינה

    מדוע?

    מדוע 4*11?

  • אוהד ניר

    המשך הפתרון

    מספר האפשרויות לחלק את חמשת השוקולדים כך שאף ילד לא יקבל את השוקולד שהוא שונא זה 44, לגבי הסיכוי צריך לחלק את זה במספר האפשרויות הכולל שזה 5! כלומר 120, וזה נותן סיכוי של 36.67%