Maths Olympiad Prep

Library / /77 of 84

Combinatorics Difficulty 5.9 AIME, harder Prove it United States

Problem:

Rosencrantz and Guildenstern each start with $2013\$ 2013 and are flipping a fair coin. When the coin comes up heads Rosencrantz pays Guildenstern $1\$ 1 and when the coin comes up tails Guildenstern pays Rosencrantz $1\$ 1. Let f(n)f(n) be the number of dollars Rosencrantz is ahead of his starting amount after nn flips. Compute the expected value of max{f(0),f(1),f(2),,f(2013)}\max \{f(0), f(1), f(2), \ldots, f(2013)\}.

Solution

Solution:

Answer: 12+(1007)(20131006)22012\frac{-1}{2}+\frac{(1007)\binom{2013}{1006}}{2^{2012}}

We want to calculate Γ=i=0iP(max\Gamma=\sum_{i=0}^{\infty} i \cdot P(\max profit =i)=i), where we consider the maximum profit Rosencrantz has at any point over the first 2013 coin flips. By summation by parts this is equal to a=12013P(max\sum_{a=1}^{2013} P(\max profit a)\geq a).

Let pap_{a} be the probability that Rosencrantz' max profit is at least aa and let En,aE_{n, a} be the set of sequences of flips such that Rosencrantz first reaches a profit of aa on exactly the nnth flip. Let Qa+,Qa,QaQ_{a}^{+}, Q_{a}^{-}, Q_{a} be the sets such that after all 2013 flips Rosencrantz' final profit is (respectively) greater than, less than, or equal to aa.

Then,
Γ=a=12013P( max profit a)=a=12013n=a2013P(En,a)=a=12013n=a2013P(En,aQa+)+P(En,aQa)+P(En,aQa). \begin{aligned} \Gamma & =\sum_{a=1}^{2013} P(\text{ max profit } \geq a) \\ & =\sum_{a=1}^{2013} \sum_{n=a}^{2013} P\left(E_{n, a}\right) \\ & =\sum_{a=1}^{2013} \sum_{n=a}^{2013} P\left(E_{n, a} \cap Q_{a}^{+}\right)+P\left(E_{n, a} \cap Q_{a}^{-}\right)+P\left(E_{n, a} \cap Q_{a}\right) . \end{aligned}
By symmetry, P(En,aQa+)=P(En,aQa)P\left(E_{n, a} \cap Q_{a}^{+}\right)=P\left(E_{n, a} \cap Q_{a}^{-}\right) because, for any sequence in En,aQa+E_{n, a} \cap Q_{a}^{+}, we can reverse all the flips after the nnth flip to get a sequence in En,aQaE_{n, a} \cap Q_{a}^{-}, and vice-versa.

Furthermore, n=a2013P(En,aQa+)=P(Qa+)\sum_{n=a}^{2013} P\left(E_{n, a} \cap Q_{a}^{+}\right)=P\left(Q_{a}^{+}\right) and n=a2013P(En,aQa)=P(Qa)\sum_{n=a}^{2013} P\left(E_{n, a} \cap Q_{a}\right)=P\left(Q_{a}\right).

So we have
a=12013P( max profit a)=a=12013(P(Qa)+2P(Qa+)) \sum_{a=1}^{2013} P(\text{ max profit } \geq a)=\sum_{a=1}^{2013}\left(P\left(Q_{a}\right)+2 P\left(Q_{a}^{+}\right)\right)
Since by symmetry P(Qa)=P(Qa)P\left(Q_{a}\right)=P\left(Q_{-a}\right) and we have an odd number of flips, we have a=12013P(Qa)=12\sum_{a=1}^{2013} P\left(Q_{a}\right)=\frac{1}{2}.

Also P(Qa+)=122013k=2014+a22013(2013k)P\left(Q_{a}^{+}\right)=\frac{1}{2^{2013}} \sum_{k=\left\lceil\frac{2014+a}{2}\right\rceil}^{2013}\binom{2013}{k}.

So the rest is just computation. We have:
Γ=12+122012a=12013k=2014+a22013(2013k)=12+122012k=10082013a=12k2014(2013k)=12+122012k=10082013(2013k)(k+k20131)=12+122012k=100820132013(2012k1)2013(2012k)(2013k)=12+2013(20121007)22012+(20131007)22012=12+(1007)(20131006)22012. \begin{aligned} \Gamma & =\frac{1}{2}+\frac{1}{2^{2012}} \sum_{a=1}^{2013} \sum_{k=\left\lceil\frac{2014+a}{2}\right\rceil}^{2013}\binom{2013}{k} \\ & =\frac{1}{2}+\frac{1}{2^{2012}} \sum_{k=1008}^{2013} \sum_{a=1}^{2 k-2014}\binom{2013}{k} \\ & =\frac{1}{2}+\frac{1}{2^{2012}} \sum_{k=1008}^{2013}\binom{2013}{k}(k+k-2013-1) \\ & =\frac{1}{2}+\frac{1}{2^{2012}} \sum_{k=1008}^{2013} 2013\binom{2012}{k-1}-2013\binom{2012}{k}-\binom{2013}{k} \\ & =\frac{1}{2}+\frac{2013\binom{2012}{1007}-2^{2012}+\binom{2013}{1007}}{2^{2012}} \\ & =\frac{-1}{2}+\frac{(1007)\binom{2013}{1006}}{2^{2012}} . \end{aligned}
So the answer is 12+(1007)(20131006)22012\frac{-1}{2}+\frac{(1007)\binom{2013}{1006}}{2^{2012}} (for reference, approximately 35.3).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.