Competition problem — Combinatorics

Library / /15 of 35

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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.