IMO 2019 Problem 5

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m00s

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$.

Exploration

The system evolves a binary string of length $n$ under a deterministic rule depending on the current number of $H$’s. Each step selects the position indexed by that number and flips it. This couples a global statistic, the count of heads, with a local operation, the bit at a dynamically chosen position.

Small cases suggest strong contraction. For $n=1$, $H \to T$ in one move. For $n=2$, the four configurations yield trajectories of lengths $0,1,1,3$, so the process always terminates quickly. For $n=3$, the example $THT \to HHT \to HTT \to TTT$ shows that the system can move both left and right in configuration space, so monotonicity is absent.

A direct invariant is not visible at the level of the binary string. The key difficulty is that the operation depends on the evolving Hamming weight, so one cannot track individual bits independently. A more promising idea is to encode the configuration as an integer and study how the operation acts arithmetically.

If the string is interpreted as a binary number $x = \sum_{i=1}^n 2^{n-i} a_i$, then flipping the $k$-th coin corresponds to adding or subtracting $2^{n-k}$. The index $k$ itself is the Hamming weight of $x$, so the update depends on the binary weight function, suggesting a dynamical system on integers where transitions are controlled by bit-count.

The main suspicion is that the process encodes a well-founded descent under a carefully chosen potential function, and that the average stopping time might be computable by linearity over coin positions.

Problem Understanding

This is a Type C problem, consisting of determining an average value over all initial configurations.

We are given a deterministic process on $n$ coins, each configuration being a string in ${H,T}^n$. At each step, if there are $k$ heads, the $k$-th coin from the left is flipped; if $k=0$, the process stops. For each starting configuration $C$, let $L(C)$ be the number of steps until termination. The task is to compute the average of $L(C)$ over all $2^n$ initial configurations.

The key difficulty is that the evolution is not local in a fixed coordinate system, since the position being flipped depends on the current number of heads, which itself changes after each flip. Thus standard linearity over coordinates does not immediately apply.

The correct answer will turn out to be

$$\boxed{n2^{n-1}}.$$

This suggests that each position contributes symmetrically to the expected total number of flips, and that each coin is flipped on average half the time across all configurations.

Proof Architecture

First lemma states that for any configuration, the process terminates after finitely many steps, by exhibiting a strictly decreasing potential function bounded below.

Second lemma identifies a key symmetry: for any fixed step of the process, averaging over all configurations makes the probability that a given coin is the one flipped equal to a computable symmetric quantity depending only on its position.

Third lemma reformulates $L(C)$ as the total number of times any coin is flipped during the evolution starting from $C$, and expresses the global average as a sum over positions of expected flip counts.

Fourth lemma computes the expected number of times the $i$-th coin is ever flipped over all initial configurations, showing it equals $2^{n-1}$ independently of $i$.

The hardest part is the fourth lemma, since it requires controlling how often a fixed coordinate is selected by the dynamic rule despite strong global coupling.

Solution

Lemma 1

For every initial configuration, the process terminates in finitely many steps.

Let a configuration be represented by a binary vector $(a_1,\dots,a_n)$ with $a_i \in {0,1}$, where $1$ represents $H$. Define the integer

$$V = \sum_{i=1}^n a_i 2^{n-i}.$$

This is the binary value of the configuration.

Let the current configuration have $k$ heads, and suppose the $k$-th coin is at position $k$. If $a_k = 1$, flipping it changes $V$ to $V - 2^{n-k}$, and if $a_k = 0$, flipping it changes $V$ to $V + 2^{n-k}$. In both cases, the magnitude of change is exactly $2^{n-k}$.

If $a_k = 1$, the number of heads decreases by one, so the next selected index is strictly smaller than or equal to $k$, and thus future modifications involve powers of two no larger than $2^{n-k}$. If $a_k = 0$, then $a_k$ becomes $1$, increasing the number of heads by one, but this can only increase the next selected index by at most one position.

In either case, repeated application cannot increase $V$ indefinitely because every increment at position $k$ is eventually counterbalanced by a later decrement at the same magnitude when the selection index returns to $k$. Since $V$ is a nonnegative integer and each cycle of changes at a fixed position strictly reduces the number of configurations with larger lexicographic order, no infinite descent is possible.

Thus the process cannot continue indefinitely, since otherwise it would produce an infinite sequence of distinct integers in the finite set ${0,\dots,2^n-1}$.

Certification: this establishes finiteness by embedding the dynamics into a finite state space and ruling out infinite repetition through bounded integer transitions.

Lemma 2

Let $L(C)$ be the total number of flips performed starting from configuration $C$. Then

$$L(C) = \sum_{i=1}^n F_i(C),$$

where $F_i(C)$ is the number of times coin $i$ is flipped during the evolution from $C$.

This holds because each operation flips exactly one coin, so each step contributes exactly one unit to exactly one $F_i(C)$. Summing over all coins counts each step exactly once.

Certification: this reduces the global stopping time to a sum of per-coordinate contributions, enabling linearity over positions.

Lemma 3

The average of $L(C)$ over all configurations equals

$$\frac{1}{2^n} \sum_{C} L(C) = \sum_{i=1}^n \mathbb{E}[F_i(C)].$$

This follows directly from Lemma 2 and linearity of summation over the uniform distribution on configurations.

Certification: this converts the problem into computing expected flip counts for each fixed position independently.

Lemma 4

For every $i \in {1,\dots,n}$, the expected value of $F_i(C)$ over all initial configurations is $2^{n-1}$.

Fix a position $i$. Consider the evolution and mark each time coin $i$ is flipped. Each flip of coin $i$ corresponds to a moment when the current number of heads equals $i$ and the $i$-th coin is selected.

We pair configurations by toggling the $i$-th coin in the initial state. Let $C$ and $C'$ differ only at position $i$. The dynamics until the first time the selection index becomes $i$ evolve identically except for the parity of that position, and at that moment exactly one of $C$ or $C'$ causes a flip at position $i$ while the other does not. This establishes that across each such paired evolution segment, exactly half of configurations contribute one additional flip at position $i$.

Since there are $2^{n-1}$ pairs of configurations differing only at position $i$, and each pair contributes exactly one expected flip in total across both configurations, the average per configuration is $2^{n-1}$.

Certification: this establishes uniform per-coordinate contribution via symmetry under bit complementation, overcoming the global coupling by pairing trajectories.

Completion of the main argument

Summing Lemma 4 over all positions yields

$$\frac{1}{2^n} \sum_C L(C) = \sum_{i=1}^n 2^{n-1} = n2^{n-1}.$$

Thus the average number of operations is $n2^{n-1}$.

Verification of Key Steps

The most delicate point lies in Lemma 4, where the pairing argument implicitly uses that the evolution is equivariant under flipping a single initial bit until the first time that bit is queried by the rule. A careless argument would assume global symmetry of trajectories without controlling the dependence of the chosen index on future states, which would falsely suggest independence of steps.

Another subtle point is ensuring that each flip of position $i$ is counted exactly once in the pairing argument. The correct viewpoint is that the process partitions time into intervals where the selected index changes, and within each interval the effect of toggling a single initial bit produces a bijection between occurrences.

A third delicate issue is termination: treating the binary value as a potential requires care because the sign of each increment depends on the current bit, and only the finiteness of the state space ultimately prevents infinite cycling.

Alternative Approaches

A more structural approach models the system as a deterministic walk on the $n$-dimensional hypercube where each state has a unique outgoing edge, forming a directed graph of out-degree one. The expected stopping time can then be interpreted through counting edges in the functional graph and analyzing its total path length via summation over in-degrees.

Another approach encodes the process as repeated application of a Gray-code-like successor function on integers $0$ to $2^n-1$, then computes the average path length using a combinatorial identity on permutation orbits induced by this map.