2019 IMO Problems/Problem 5

Problem

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation:

If there are exactly $k > 0$ coins showing $H$ , then he turns over the $k^{th}$ coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n = 3$ the process starting with the configuration $THT$ would be $THT \rightarrow HHT \rightarrow HTT \rightarrow TTT$ , 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 $C$ , let $L(C)$ be the number of operations before Harry stops. For example, $L(THT) = 3$ and $L(TTT) = 0$ . Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$ .

Solution

Don't worry, this is way simpler than it's length may suggest :)

Claim: The expected value of $L(C)$ is $\frac{n(n+1)}{4}$ .

We prove parts A and B simultaneously using induction.

Base case: $n=1$

$L(T)=0$ and $L(H)=1$ , and these are the only possibilities, so clearly the process terminates and $E[L(C)] = \frac{1}{2} = \frac{1*2}{4}$ .

Inductive step: Assume that for $n-1$ coins, the process always terminates, and $E[L(C)] = \frac{n(n-1)}{4}$ . Define $E_{n-1} = E[L(C)]$ here. Now, for $n$ coins, define $E_{n} = E[L{C}]$ across all $2^n$ configurations. Consider cases on the last coin:

Case 1: Final coin is $T$

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 $P_{T} = 1/2$ , and will be identical to the general $n-1$ case; thus, this process terminates, and we will have an expected number of moves here of $E_{n-1}$ .

Case 2: Final coin is $H$

The probability that this occurs is $P_{H} = 1/2$ . 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 $n$ moves). Thus, we now have a new goal for the first $n-1$ coins (given the head at the end); get all heads.

We claim that this process is symmetrical to the original process on $n-1$ coins, and thus it terminates and has the expected number of moves $E_{n-1}$ .

Proof: Let us have $k \ge 1$ heads in our group of n coins, of which $k-1$ are in the first n-1. We are supposed to flip the $k$ 'th coin from the left in the first n-1 coins, which is equivalent to flipping the $(n-k)$ 'th coin from the right (in the first $n-1$ coins, NOT all $n$ coins), but there are $n-k$ tails in the first $n-1$ coins! We now have a new process defined as follows:

Consider a configuration of n-1 coins with $x \ge 1$ 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 $E_{n-1}$ , 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 $E_{n-1}+n$ .

Thus, the overall process on n coins will terminate, since the process terminates in both the representative cases on n-1 coins. $\boxed{Q.E.D}$ 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} = \boxed{\frac{n(n+1)}{4}}$ as desired. We are now done.

-Solution by thanosaops

Page

Toolbox

Search

2019 IMO Problems/Problem 5

Problem

Solution