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. ----------------------- OK, so shat can we do with 4 sheets (m = 2, 4 steps, final sum 16) 1 1 1 1 2 2 1 1 2 2 2 2 4 4 2 2 4 4 4 4 sum exactly 16 after 4 steps. Other approach 1 1 1 1 2 2 1 1 3 2 3 1 3 3 3 3 6 6 3 3 sum 18 > 16 Is it possible to do better after 3 3 2 1? 4 3 2 4 4 5 5 4 again, sum 18 3 3 2 1? 3 5 5 1 3 5 6 6 sum 20 Intuitively, pairing with equal number "only" doubles the number, pairing with a higher number raises the number more. (on the other hand, the smaller number less, but we are somehow looking at a logarithmic scale) Hm... Sum of the logarithms of of the numbers could be an interesting attribute of the configuration. When pairing equal numbers, the sum of logarithms is increased by 2, (every number by one Can we prove that it increases always at least by one? 2^a 2^b -> 2^a+2^b, 2^a+2^b log: a,b -> 2log(2^a + 2^b) It should be Jensen inequality applied to (binary) logarithm. It states: log((a+b)/2) >= (log(a) + log(b))/2 log(a) + log(b) <= 2log((a+b)/2) = 2log(a+b) - 2 2log(a+b) >= log(a) + log(b) + 2 This is exactly, what I need for initial numbers a,b. So, in every step, the log-sum increases by at least 2. At the beginning, the log-sum is 0. After m2^(m-1) steps, the log-sum is at least m*2^m. Can we conclude something about the standard sum? (I hope, it should be just other Jensen for log) Let us denote the final numbers a_1 ... a_(2^m) By Jensen, we have: log((a_1+...+a_(2^m))/2^m) >= (log(a_1) + ... + log(a_(2^m)))/2^m -- substitute log-sum log((a_1+...+a_(2^m))/2^m) >= (m*2^m) / 2^m = m -- 2^LHS >= 2^RHS (a_1+...+a_(2^m))/2^m = 2^m a_1 + ... + a_(2^m) = 4^m Problem solved!