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

th coin from the left; otherwise all coins show

T

and he stops. For example, if

n=3

, the process starting with

THT

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. Determine the average value of

L(C)

over all

2^n

possible initial configurations.

Step 3 of 6: Transform a final head

Previous step Next step

In plain words

Counting heads from the left becomes counting tails from the right.

k-1\text{ heads in the first }n-1\text{ coins }\Longrightarrow\text{flip the }k\text{th left coin}=\text{the }(n-k)\text{th right tail}

Detailed analysis

Now suppose the last coin is $H$ . If the first $n-1$ coins contain $k-1$ heads, the total is $k$ , so the rule flips the $k$ th coin from the left; this is among the first $n-1$ coins. Those coins contain $n-k$ tails, and the selected position is the $(n-k)$ th tail counted from the right. Thus, after reversing the first $n-1$ positions and exchanging $H$ with $T$ , the operation is exactly the original rule, with the target changed from all tails to all heads.