2023 WSMO Accuracy Round Problems/Problem 5

Problem

Bob flips $x+1$ coins and Bobby flips $x$ coins, where $x$ is a random integer chosen between the range of $[27,100].$ The expected probability that Bob gets more heads than Bobby is $\frac{m}{n},$ for relatively prime positive integers $m$ and $n.$ Find $m+n$ .

Solution

We will count the number of outcomes in which Bob and Bobby flip coins such that Bob gets more heads than Bobby, and divide that by the total number of possible outcomes, $2^{x+1} \cdot 2^x = 2^{2x+1}.$ Consider Bob's and Bobby's first $x$ flips. There are a total of $2^x \cdot 2^x = 2^{2x}$ possible outcomes. Among these, $\sum_{i=0}^x \binom{x}{i} \binom{x}{i} = \sum_{i=0}^x \binom{x}{i} \binom{x}{x-i} = \binom{2x}{x}$ are the outcomes in which Bob and Bobby have the same number of heads. Now, we consider Bob's final (last) coin flip. For these $\tbinom{2x}{x}$ outcomes, Bob must flip a head to end up with more heads than Bobby. For the remaining $2^{2x} - \tbinom{2x}{x}$ outcomes, in exactly half of them Bob already has more heads than Bobby, and in the other half, Bobby has more. If Bob already has more heads, then regardless of the final flip, he will still have more heads. If he has fewer heads, then the final flip won't change that. So, the number of favorable outcomes is $\binom{2x}{x} + \frac{2^{2x} - \binom{2x}{x}}{2} \cdot 2 = 2^{2x}.$ Therefore, the probability that Bob ends up with more heads than Bobby is $\frac{2^{2x}}{2^{2x+1}} = \frac{1}{2}.$ So, the expected probability over $x$ from $[27, 100]$ is $\frac{1}{2} \implies 1 + 2 = 3.$

~pinkpig

Page

Toolbox

Search

2023 WSMO Accuracy Round Problems/Problem 5

Problem

Solution