2007 iTest Problems/Problem 59
The following problem is from the Ultimate Question of the 2007 iTest, where solving this problem required the answer of a previous problem. When the problem is rewritten, the T-value is substituted.
Problem
Fermi and Feynman play the game in which Fermi wins with probability , where and are relatively prime positive integers such that . The rest of the time Feynman wins (there are no ties or incomplete games). It takes a negligible amount of time for the two geniuses to play so they play many many times. Assuming they can play infinitely many games (eh, they're in Physicist Heaven, we can bend the rules), the probability that they are ever tied in total wins after they start (they have the same positive win totals) is . Find the value of .
Solution
There is a bijection between an infinite string of games that the men play and an infinite path from always going up or right. Let the ordered pair represent the number of Fermi wins followed by the number of Feynman wins, and call the probability of Fermi winning .
Note that every possible game can first tie at 2 games, 4 games, etc. corresponding to paths intersecting , paths intersecting but not , etc. Because these points are on the diagonal of our plane of paths, and we wish to have paths that don't intersect the diagonal until (aka they stay underneath/above the diagonal until ), we consider the Catalan numbers.
Generally, assume Fermi wins the first game. Then in order for them to first tie at , the games must be under the diagonal running from to or under/on the diagonal running from to . This corresponds to paths, where is the th Catalan number. Then they tie by Feynman winning the last game (how the path runs afterwards is irrelevant). Any path running from to has Fermi and Feynman wins each, so it happens with probability . We have to double our probability due to either starting with a Fermi win or a Feynman win, which are symmetric. Because these events are mutually exclusive between any , the cumulative probability of tieing is Recall the generating function of the Catalan numbers, so Because , the requested answer is .
~clarkculus
See Also
2007 iTest (Problems, Answer Key) | ||
Preceded by: Problem 58 |
Followed by: Problem 60 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • TB1 • TB2 • TB3 • TB4 |