2019 IMO Problems/Problem 5
Problem
The Bank of Bath issues coins with an on one side and a
on the other. Harry has
of these coins arranged in a line from left to right. He repeatedly performs the following operation:
If there are exactly coins showing
, then he turns over the
coin from the left; otherwise, all coins show
and he stops. For example, if
the process starting with the configuration
would be
, which stops after three operations.
(a) Show that, for each initial configuration, Harry stops after a finite number of operations.
(b) For each initial configuration , let
be the number of operations before Harry stops. For
example,
and
. Determine the average value of
over all
possible initial configurations
.
Solution
Don't worry, this is way simpler than it's length may suggest :)
Claim: The expected value of is
.
We prove parts A and B simultaneously using induction.
Base case:
and
, and these are the only possibilities, so clearly the process terminates and
.
Inductive step: Assume that for coins, the process always terminates, and
. Define
here. Now, for
coins, define
across all
configurations. Consider cases on the last coin:
Case 1: Final coin is
If the last coin is T, then we simply can forget about it, as we can flip it to heads only if we have n heads, which is impossible. This occurs with probablity , and will be identical to the general
case; thus, this process terminates, and we will have an expected number of moves here of
.
Case 2: Final coin is
The probability that this occurs is . The only way we have for the process to terminate now is for all coins to show heads, after which we can progressively flip each coin from right to left (this will take
moves). Thus, we now have a new goal for the first
coins (given the head at the end); get all heads.
We claim that this process is symmetrical to the original process on coins, and thus it terminates and has the expected number of moves
.
Proof: Let us have heads in our group of n coins, of which
are in the first n-1. We are supposed to flip the
'th coin from the left in the first n-1 coins, which is equivalent to flipping the
'th coin from the right (in the first
coins, NOT all
coins), but there are
tails in the first
coins! We now have a new process defined as follows:
Consider a configuration of n-1 coins with tails, and flip the x'th coin from the right, and keep flipping until all coins are heads.
This is clearly symmetric to the original process, and will terminate if and only if the original process on n-1 coins does, and has the same expected number of moves as the original. Thus, the claim is proven.
Back to the case: We now have a process to get to all heads that will terminate with an expected number of steps of , and then an n-step algorithm to reach the finish. Thus, here also, the process terminates, and we have a total expected number of steps as
.
Thus, the overall process on n coins will terminate, since the process terminates in both the representative cases on n-1 coins. Also, the expected value of steps can be easily computed now; $E_{n} = (P_{T})(E_{n-1})+(P_{H})(E_{n-1}+n) = E_{n-1}+n/2 = \frac{n(n-1}{4}+\frac{n}{2} = \makebox{\frac{n(n+1)}{4}}$ (Error compiling LaTeX. Unknown error_msg) as desired. We are now done.
-Solution by thanosaops