2014 IMO SL #C2

Since the last one was super easy, I have to do another one... right?

 We have $2^m$ sheets of paper, with the number $1$ written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a + b$ on both sheets. Prove that after $m2^{m -1}$ steps, the sum of the numbers on all the sheets is at least $4^m$ .

Let $S_n, P_n$ denote the sum, product of the numbers after $n$ moves respectively.

Claim: $P_n \ge 2^{2n}$

Proof: Note that $(a+b)^2 \ge 4ab.$ So we get the recursive relation $P_n \ge 4P_{n-1}.$ This yields the claim. $\square$

Thus by AM-GM

$$S_{m2^{m-1}} \ge 2^m \left( P_{m2^{m-1}} \right) ^{1/2^m} \ge 2^m \left( 2^{m2^{m}} \right) ^{1/2^m} = 4^m$$which is the desired bound. $\blacksquare$.

Alright, at least it wasn't as easy as the last one.