הצעת דרך לפתרון
אסמן את מספר הצירופים מ-n על k כך: (C(n,k. סביבות נפילת עץ בדיוק k פעמים מתוך n שווה:
C(n,k) * 0.5^k * 0.5^(n-k) = C(n,k) / 2^n
סבירות נפילת עץ j פעמים ב-k הנסיונות של התנין ו-j פעמים ב-n-k הפעמים של הקיפוד שווה:
[ C(k,j) / 2^k ] * [ C(n-k,j) / 2^(n-k) ] = = C(k,j)C(n-k,j) / 2^n
סבירות נפילת עץ מספר פעמים שווה אצל שניהם:
[ C(k,0)C(n-k,0) + C(k,1)C(n-k,1) + C(k,2)C(n-k,2) + . . . ] / 2^n
"וכן הלאה" פירושו עד הקטן משני המספרים k או n-k (אפשר להחליט שהמינימלי מהם הוא למשל k, אחרת התנין והקיפוד פשוט יכולים להתחלף בשמותיהם). בקיצור, צריך להוכיח את הזהות:
C(k,0)C(n-k,0) + C(k,1)C(n-k,1) + C(k,2)C(n-k,2) + . . . = C(n,k)
הצעת כיוון להוכחת זהות זו, היא שימוש במשולש פסקל:
C(n,k) = C(n-1,k-1) + C(n-1,k) = = [ C(n-2,k-2) + C(n-2,k-1) ] + [ C(n-2,k-1) + C(n-2,k) ] = = C(n-2,k-2) + 2C(n-2,k-1) + C(n-2,k) = = C(n-3,k-3) + 3C(n-3,k-2) + 3C(n-3,k-1) + C(n-3,k) = . . . = C(m,0)C(n-m,k-m) + C(m,1)C(n-m,k-m+1) + . . . + C(m,m)C(n-m,k)
כל עוד m אינו גדול מ-k ומ-n-k. נראה לי שאפשר להוכיח את זה, למשל, באינדוקציה על m.