KöMaL problem A, 2021

Algebra Difficulty 6.0 National Olympiad Prove it Hungary

Let $0<p<1$ be given. Initially we have $n$ coins, all of which has probability $p$ of landing on heads, and probability $1-p$ landing on tails (the results of the tosses are independent from each other). In each round we toss our coins and remove those that result in heads. We keep repeating this until all our coins are removed. Let $k_n$ denote the expected number of rounds that was needed to get rid of all the coins. Prove that there exists $c>0$ for which the following inequality holds for all positive integers $n$ :

We don't reproduce this publisher's solutions. Their own solution is here — work the problem first.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: KöMaL, licensed Rights held by KöMaL and the MATFUND Foundation. Statement reproduced verbatim; metadata (topic, difficulty) added by this project. Solutions are the publisher's, linked not copied.