Problem A. 798. (April 2021)

A. 798. Let \(\displaystyle 0<p<1\) be given. Initially we have \(\displaystyle n\) coins, all of which has probability \(\displaystyle p\) of landing on heads, and probability \(\displaystyle 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 \(\displaystyle k_n\) denote the expected number of rounds that was needed to get rid of all the coins. Prove that there exists \(\displaystyle c>0\) for which the following inequality holds for all positive integers \(\displaystyle n\):

\(\displaystyle c\left(1+\frac12+\cdots+\frac1{n}\right)<k_n<1+c\left(1+\frac12+\cdots+\frac1{n}\right). \)

(7 pont)

Deadline expired on May 10, 2021.

Statistics:

1 student sent a solution.
3 points:	1 student.

Problems in Mathematics of KöMaL, April 2021