IMO 2019 · Problem 5

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^{\text{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\to HHT\to HTT\to 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\).

Official text of the problem. Official problem paper (PDF)

Answer

Harry always stops. The average number of operations is \[ \boxed{\frac{n(n+1)}4}. \]

Solution

Number the coins \(1,2,\ldots,n\) from left to right. For a configuration \(C\), let \(k\) be the number of heads and let \(S\) be the sum of the positions of those heads. Define \[ V(C)=2S-k^2. \]

We show that \(V(C)\) is a nonnegative integer that decreases by exactly \(1\) at every operation.

If the heads occupy positions \(a_1<a_2<\cdots<a_k\), then \(a_j\ge j\), so \[ V(C)=2\sum_{j=1}^{k}a_j-k^2 \ge 2\sum_{j=1}^{k}j-k^2=k. \] Thus \(V(C)\ge0\), and \(V(C)=0\) if and only if there are no heads.

Now suppose \(k>0\), and let \(C'\) be the configuration after one operation. The coin in position \(k\) is turned over. Put \(\varepsilon=1\) if it changes from \(T\) to \(H\), and \(\varepsilon=-1\) if it changes from \(H\) to \(T\). The new number of heads is \(k+\varepsilon\), and the new sum of their positions is \(S+\varepsilon k\). Consequently, \[ \begin{aligned} V(C') &=2(S+\varepsilon k)-(k+\varepsilon)^2\\ &=2S-k^2-\varepsilon^2\\ &=V(C)-1. \end{aligned} \]

Since a nonnegative integer cannot decrease indefinitely, the process must stop. At that point all coins show \(T\), so the final value of \(V\) is zero. Therefore \[ \boxed{L(C)=V(C)=2S-k^2}. \] This proves part (a) and gives the formula needed for part (b).

Choose an initial configuration uniformly from all \(2^n\) configurations. For each \(i\), let \(X_i=1\) if coin \(i\) shows \(H\), and \(X_i=0\) otherwise. Then \[ S=\sum_{i=1}^{n}iX_i,\qquad k=\sum_{i=1}^{n}X_i. \] Each \(X_i\) has expectation \(1/2\), and distinct coins are independent, so \(\mathbb E[X_iX_j]=1/4\) for \(i\ne j\). Hence \[ \mathbb E[2S]=2\sum_{i=1}^{n}i\cdot\frac12 =\frac{n(n+1)}2, \] and, using \(X_i^2=X_i\), \[ \mathbb E[k^2] =\sum_{i=1}^{n}\mathbb E[X_i] +2\sum_{1\le i<j\le n}\mathbb E[X_iX_j] =\frac n2+\frac{n(n-1)}4 =\frac{n(n+1)}4. \] Thus the required average is \[ \mathbb E[L(C)] =\mathbb E[2S-k^2] =\frac{n(n+1)}2-\frac{n(n+1)}4 =\boxed{\frac{n(n+1)}4}. \]

The solution was checked against the official IMO shortlist solutions.