ISL 2019 C3
Let be a positive integer. Harry has coins lined up on his desk, each showing heads or tails. He repeatedly does the following operation: if there are coins showing heads and , then he flips the coin over; otherwise he stops the process. (For example, the process starting with THT would be THT , which takes three steps.) Letting denote the initial configuration (a sequence of 's and 's), write for the number of steps needed before all coins show . Show that this number is finite, and determine its average value over all possible initial configurations .
Official text Transcription from NuminaMath olympiads, checked word for word against the official paper. Quoted with source.
Official text: IMO 2019 Shortlist booklet, page 8.
Solutions
Official solution Solution 1 by the IMO Problem Selection Committee
The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).
Similar problems
These problems have the most words in common with this statement.