Harvard-MIT Mathematics Tournament

Solution:

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

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\left|\left|i_{3 n-2} a_{3 n-2}+s_{3 n-3}\right|-\left|i_{3 n-1} a_{3 n-1}+i_{3 n} a_{3 n}\right|\right| \leq\left|s_{3 n}\right|=0 \\ & 0 \leq\left|\left|i_{3 n-1} a_{3 n-1}+s_{3 n-3}\right|-\left|i_{3 n-2} a_{3 n-2}+i_{3 n} a_{3 n}\right|\right| \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 $|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}|$, 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}}$.