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$.
The problem is C2 from this shortlist:
https://www.imo-official.org/problems/IMO2014SL.pdf
It's a nice one to struggle with because the statement quickly appears to be obviously true (after a bit of counting and experimenting), but it's hard to prove.
My solution:
First note that pairing two sheets with the same number at each step until each sheet reads $2^m$ yields a sum of $4^m$ in exactly $m2^{m-1}$ steps.
We prove that this construction yields the minimal sum over all possible sums that can be constructed in $m2^{m-1}$ steps.
Note that this construction is minimal over all constructions in which sheets are paired only with other sheets containing the same number as themselves (since it increases the number on a given sheet from $1$ to $2^m$ in exactly $m$ steps, and an $m+1$th step for a given pair of sheets would clearly cause a greater addition to the final sum than any of the steps here).
Suppose it were possible to construct a smaller sum in the same number of steps. Then there must be some sheet $A$ which is at some step paired with a sheet $B$ containing a number smaller than its own.
Suppose $A$ is initially paired with a sheet containing the same number as itself (thus doubling its total) $s$ times, and $B$ paired with such a sheet $t$ times where $s>t$, and then in what will be the $s+1$'th step involving $A$ and the $t+1$'th step involving $B$, $A$ and $B$ are paired giving each the same total, namely $2^s+2^t$.
Consider now the case where for their respective remainders of $m$ steps, both $A$ and $B$ are paired with sheets containing the same number as themselves and hence having their totals doubled at each step.
Then the numbers on $A$ and $B$ after each has performed its $m$ steps will be
$(2^s+2^t)2^{m-(s+1)}$ and $(2^s+2^t)2^{m-(t+1)}$ respectively.
Since the sum of these two numbers is > $2\times2^m$, we see that pairing $A$ with a number smaller than itself at a single step and $B$ with a number larger than itself a single step does not lead to a smaller final sum.
So if it is possible to reduce the final sum after the step at which $A$ and $B$ are paired, it must be by subsequently either pairing $A$ with at least one further sheet containing a smaller number, or by pairing $B$ with at least one sheet containing a smaller number. But each time $A$ or $B$ is paired with a sheet $C$ containing a smaller number, $C$ is being paired with a sheet containing a larger number. [incomplete]
Hence the sum constructed initially is minimal.
Edited in response to comments, rethinking conclusion, suggestions welcome. Thanks.