HMMT-Feb 2011 guts, Problem 11

Rosencrantz and Guildenstern play a game in which they repeatedly flip a fair coin. Let $a_{1}=4$, $a_{2}=3$, and $a_{n}=a_{n-1}+a_{n-2}$ for all $n \geq 3$. On the $n$th flip, if the coin is heads, Rosencrantz pays Guildenstern $a_{n}$ dollars, and, if the coin is tails, Guildenstern pays Rosencrantz $a_{n}$ dollars. If play continues for 2010 turns, what is the probability that Rosencrantz ends up with more money than he started with?

Solution: Since Rosencrantz and Guildenstern have an equal chance of winning each toss, both have the same probability of ending up with a positive amount of money. Let $x$ denote the probability that they both end up with zero dollars. We wish to find $\frac{1-x}{2}$. We have $x$ is equal to the probability that \[ s_{2010}:=i_{1} a_{1}+i_{2} a_{2}+\cdots i_{2010} a_{2010}=0 \] where $i_{n}$ has an equal probability of being either 1 or -1 . We claim that $s_{2010}=0$ if and only if $i_{3 n}=-i_{3 n-1}=-i_{3 n-2}$ for all $n \leq 670$. We start with the following lemma. Lemma. We have $a_{n}>\sum_{k=1}^{n-3} a_{k}$ for all $n \geq 4$. Proof: For the case $n=4, a_{4}=a_{3}+a_{2}=2 a_{2}+a_{1}>a_{1}$. In case $n>4$, we have \[ a_{n}=a_{n-2}+a_{n-1}>a_{n-2}+\sum_{k=1}^{n-4} a_{k}=a_{n-4}+\sum_{k=1}^{n-3} a_{k}>\sum_{k=1}^{n-3} a_{k} \] It suffices to show that $s_{3 n}=0$ only if $i_{3 k}=-i_{3 k-1}=-i_{3 k-2}$ for all $k \leq n$. The triangle inequality implies the following: \[ \begin{aligned} & 0 \leq|| i_{3 n-2} a_{3 n-2}+s_{3 n-3}|-| i_{3 n-1} a_{3 n-1}+i_{3 n} a_{3 n}|| \leq\left|s_{3 n}\right|=0 \\ & 0 \leq|| i_{3 n-1} a_{3 n-1}+s_{3 n-3}|-| i_{3 n-2} a_{3 n-2}+i_{3 n} a_{3 n}|| \leq\left|s_{3 n}\right|=0 \end{aligned} \] By the lemma, we have \[ \begin{array}{rll} a_{3 n-2}+\sum_{k=1}^{3 n-3} a_{k}<a_{3 n-2}+a_{3 n} & < & a_{3 n-1}+a_{3 n} \\ a_{3 n-1}+\sum_{k=1}^{3 n-3} a_{k}<a_{3 n-1}+a_{3 n-3}+a_{3 n-4}+a_{3 n-2} & = & a_{3 n-2}+a_{3 n} \end{array} \] $i_{3 n}=i_{3 n-1}$ implies $\left|a_{3 n-2}+\sum_{k=1}^{3 n-3} a_{k}\right|<\left|i_{3 n-1} a_{3 n-1}+i_{3 n} a_{3 n}\right|$ and $i_{3 n}=i_{3 n-2}$ implies $\mid a_{3 n-1}+$ $\sum_{k=1}^{3 n-3} a_{k}|<| i_{3 n-2} a_{3 n-2}+i_{3 n} a_{3 n} \mid$, which are both contradictions; therefore, we must have $i_{3 n}=-i_{3 n-1}$ and $i_{3 n}=-i_{3 n-2}$. The probability that $i_{3 n}=-i_{3 n-1}=-i_{3 n-2}$ is $\frac{1}{4}$, so $x=\left(\frac{1}{4}\right)^{670}=\frac{1}{2^{1340}}$, and $\frac{1-x}{2}=\frac{1}{2}-\frac{1}{2^{1341}}$. $\fbox{\frac{1}{2}-\frac{1}{2^{1341}}}$.

Answer: \frac{1}{2}-\frac{1}{2^{1341}}