2019 IMO Problems/Problem 5
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 .