Library / Belarus — Selection and Training Session /29 of 78

Belarus — Selection and Training Session

Combinatorics Difficulty 5.3 AIME, harder Prove it Belarus

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$ .

Solution

1. See IMO-2014 Shortlist, Problem C2.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.