IMO 2019 Shortlist C3
Let n be a positive integer. Harry has n coins lined up on his desk, each showing heads or tails. He repeatedly does the...
Category: Combinatorics
Problem
Let n be a positive integer. Harry has n coins lined up on his desk, each showing heads or tails. He repeatedly does the following operation: if there are k coins showing heads and k ą 0, then he flips the kth coin over; otherwise he stops the process. (For example, the process starting with THT would be THT Ñ HHT Ñ HTT Ñ TTT, which takes three steps.) Letting C denote the initial configuration (a sequence of n H’s and T’s), write ℓpCq for the number of steps needed before all coins show T. Show that this number ℓpCq is finite, and determine its average value over all 2n possible initial configurations C. (USA)