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 $\textit{Probabicloneme}$ in which Fermi wins with probability $a/b$ , where $a$ and $b$ are relatively prime positive integers such that $a/b<1/2$ . 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 $\textit{Probabicloneme}$ 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 $17/77$ . Find the value of $a$ .

Solution

There is a bijection between an infinite string of games that the men play and an infinite path from $(0,0)$ always going up or right. Let the ordered pair $(x,y)$ represent the number of Fermi wins followed by the number of Feynman wins, and call the probability of Fermi winning $p$ .

Note that every possible game can first tie at 2 games, 4 games, etc. corresponding to paths intersecting $(1,1)$ , paths intersecting $(2,2)$ but not $(1,1)$ , 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 $(n,n)$ (aka they stay underneath/above the diagonal until $(n,n)$ ), we consider the Catalan numbers.

Generally, assume Fermi wins the first game. Then in order for them to first tie at $(n,n)$ , the games must be under the diagonal running from $(0,0)$ to $(n,n)$ or under/on the diagonal running from $(1,0)$ to $(n,n-1)$ . This corresponds to $C_{n-1}$ paths, where $C_n$ is the $n$ th Catalan number. Then they tie by Feynman winning the last game (how the path runs afterwards is irrelevant). Any path running from $(0,0)$ to $(n,n)$ has $n$ Fermi and Feynman wins each, so it happens with probability $(p(1-p))^n$ . 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 $n$ , the cumulative probability of tieing is $2\sum_{n=1}^{\infty}C_{n-1}(p(1-p))^n=2\sum_{n=0}^{\infty}C_{n}(p(1-p))^{n+1}=\frac{17}{77}$ Recall the generating function of the Catalan numbers, $\sum_{n=0}^{\infty}C_{n}x^{n}=\frac{1-\sqrt{1-4x}}{2x}$ so $2\sum_{n=0}^{\infty}C_{n}(p(1-p))^{n+1}=1-\sqrt{1-4p(1-p)}=\frac{17}{77}$ $p=\frac{17}{154},\frac{137}{154}$ Because $p<1/2$ , the requested answer is $\boxed{17}$ .

~clarkculus

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

Page

Toolbox

Search

2007 iTest Problems/Problem 59

Problem

Solution

See Also