Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 iTest Problems/Problem 59"
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
''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 ==
 
== Problem ==
−
Let <math>T=\text{TNFTPP}</math>. Fermi and Feynman play the game <math>\textit{Probabicloneme}</math> in which Fermi wins with probability <math>a/b</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers such that <math>a/b<1/2</math>. 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 <math>\textit{Probabicloneme}</math> 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 <math>(T-332)/(2T-601)</math>. Find the value of <math>a</math>.  
+
Fermi and Feynman play the game <math>\textit{Probabicloneme}</math> in which Fermi wins with probability <math>a/b</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers such that <math>a/b<1/2</math>. 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 <math>\textit{Probabicloneme}</math> 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 <math>17/77</math>. Find the value of <math>a</math>.
  
 
== Solution ==
 
== Solution ==
 +
There is a bijection between an infinite string of games that the men play and an infinite path from <math>(0,0)</math> always going up or right. Let the ordered pair <math>(x,y)</math> represent the number of Fermi wins followed by the number of Feynman wins, and call the probability of Fermi winning <math>p</math>.
 +
 +
Note that every possible game can first tie at 2 games, 4 games, etc. corresponding to paths intersecting <math>(1,1)</math>, paths intersecting <math>(2,2)</math> but not <math>(1,1)</math>, 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 <math>(n,n)</math> (aka they stay underneath/above the diagonal until <math>(n,n)</math>), we consider the Catalan numbers.
 +
 +
Generally, assume Fermi wins the first game. Then in order for them to first tie at <math>(n,n)</math>, the games must be under the diagonal running from <math>(0,0)</math> to <math>(n,n)</math> or under/on the diagonal running from <math>(1,0)</math> to <math>(n,n-1)</math>. This corresponds to <math>C_{n-1}</math> paths, where <math>C_n</math> is the <math>n</math>th Catalan number. Then they tie by Feynman winning the last game (how the path runs afterwards is irrelevant). Any path running from <math>(0,0)</math> to <math>(n,n)</math> has <math>n</math> Fermi and Feynman wins each, so it happens with probability <math>(p(1-p))^n</math>. 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 <math>n</math>, the cumulative probability of tieing is
 +
<cmath>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}</cmath>
 +
Recall the generating function of the Catalan numbers,
 +
<cmath>\sum_{n=0}^{\infty}C_{n}x^{n}=\frac{1-\sqrt{1-4x}}{2x}</cmath>
 +
so
 +
<cmath>2\sum_{n=0}^{\infty}C_{n}(p(1-p))^{n+1}=1-\sqrt{1-4p(1-p)}=\frac{17}{77}</cmath>
 +
<cmath>p=\frac{17}{154},\frac{137}{154}</cmath>
 +
Because <math>p<1/2</math>, the requested answer is <math>\boxed{17}</math>.
 +
 +
~clarkculus
  
 
==See Also==
 
==See Also==

Latest revision as of 09:56, 16 April 2024

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

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_59&oldid=218250"