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
.