חידה יפה

[lucy17]

חידה יפה

החידה הבאה יפה לא בגלל החידה עצמה אלא בגלל הפתרון האלגנטי והיפה שלה! (והשימושי!) יש שלוש קוביות הוגנות. מה ההסתברות שסכומן יהיה 12? ברור שיש דרך "ראש בקיר" לפתור את זה... יש רק 216 קומבינציות אפשריות, ומהן יש לספור את כל אלה שסכומן 15, למשל 3,4,5 וכן הלאה. אם לא תתבלבלו בספירה, אז תוכלו למצוא את הפתרון. לכן, מי שהצליח את הנ"ל בקלות מתבקש לפתור את הבעיה הנ"ל עם 6 קוביות וסכום 20... ולמעשה החידה היא למצוא דרך יותר חכמה למצוא את ההסתברות!

 

[lucy17]

רמז למי שרוצה

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

 

[איייייל]

זה בטוח לא מה שהתכוונת אליו

אבל הדרך הכי פשוטה שאני יכול לחשוב עליה היא חישוב ישיר של הקונבולוציה: (לצערי אף פעם לא למדתי קומינטוריקה כמו שצריך...) קוביה אחת:

(1,1,1,1,1,1)​

שתי קוביות:

(0,1,2,3,4,5,6,5,4,3,2,1)​

שלוש קוביות:

(0,0,1,3,6,10,15,21,25,27,27,25,21,15,10,6,3,1)​

כלומר התשובה היא 25/216. (באופן דומה עבור 6 קוביות וסכום 20 מקבלים

4221/46656​

אשמח לשמוע על דרך יותר אלגנטית!

 

[lucy17]

הפתרון שלי

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

g(z) = 0*1+1*z+1*z^2+1*z^3+1*z^4+1*z^5+1*z^6= z*(1-z^6)/(1-z)​

ושל תוצאות שלוש קוביות

f(z) = g(z)^3​

ופיתוח לטור חזקות נותן את התוצאה הדרושה. (נותר רק לחלק ב216) כמובן, פיתוח מכפלת פולינומים (והרי בצורתן ה"גולמית" הפונקציות היוצרות אינן אלא פולינומים) שקולה לקונבולוציה של המקדמים וזה מה שאתה עשית. שיטה זו היא שיטה מאד שימושית לבעיות ספירה וחלוקה למינהן. אני אישית לא "עליתי" על הפתרון כל כך מהר... (לקח לי זמן וגם קצת הדרכה... למשל כיצד לעבור מבעיה עם שתי קוביות לשלוש...) ושוב כל הכבוד!

 

[איייייל]

גם אני לא עליתי על זה "כל כך מהר",

אני כבר טוחן קונבולוציות כמעט שנתיים בטכניון

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

 

[איייייל]

שאף = שאף פעם

 

[freedom rider]

תשובה אחרת

נסמן ב-Sn את סכום ההטלות של n קוביות, וב-Ak את תוצאת ההטלה של הקוביה ה-k. אזי

P(Sn=k)=SP(Sn-1=k-j, An=j)= SP(Sn-1=k-j|An=j)P(An=j) =1/6 SP(Sn-1=k-j)​

כאשר הסכימה היא מ-1 עד 6. ולא נותר אלא לכתוב תכנית מחשב קטנה שתחשב את הרקורסיה הזאת.

 

[איייייל]

למה "תשובה אחרת"?

זו בדיוק הקונבולוציה שחישבתי! רק שאני לא כתבתי תכנית מחשב, אלא השתמשתי בתכנה קיימת... Microsoft Excel