What is the inspiration of looking at the product of the numbers and not the sum of the numbers?

I'm guessing that one tries the sum of the numbers first, and doesn't really find anything useful; then another possible quantity would be the product.

My solution: consider an operation that we erase $a,b$ and write $a+b$ instead of them. let $S$ be the sum of other sheets(other than $a,b$) then the sum of all the sheets is $2a+2b+S$. without loss of generality we can erase $a,b$ and replace them by $2a,2b$; the sum of the sheets after this operation is also $2a+2b+S$ so we can do this operation instead of the original operation (because only the sum of the sheets is important for us). thus after $m2^{m-1}$ operations the numbers $2^{k_1},2^{k_2},\cdots ,2^{k_{2^m}}$ are written on the sheets where $\sum_{i=1}^{2^m} k_i=m2^m$ so using AM-GM inquality we get $2^{k_1}+2^{k_2}+\cdots +2^{k_{2^m}}\ge \sqrt[2^m]{2^{\sum_{i=1}^{2^m} k_i}}=4^m$ Q.E.D

andria wrote: My solution: consider an operation that we erase $a,b$ and write $a+b$ instead of them. let $S$ be the sum of other sheets(other than $a,b$) then the sum of all the sheets is $2a+2b+S$. without loss of generality we can erase $a,b$ and replace them by $2a,2b$; the sum of the sheets after this operation is also $2a+2b+S$ so we can do this operation instead of the original operation (because only the sum of the sheets is important for us). thus after $m2^{m-1}$ operations the numbers $2^{k_1},2^{k_2},\cdots ,2^{k_{2^m}}$ are written on the sheets where $\sum_{i=1}^{2^m} k_i=m2^m$ so using AM-GM inquality we get $2^{k_1}+2^{k_2}+\cdots +2^{k_{2^m}}\ge \sqrt[2^m]{2^{\sum_{i=1}^{2^m} k_i}}=4^m$ Q.E.D But won't that effect the outcome of later operations. I mean you can't just assume something like that,

Here is my solution. Note that $(a+b)^2 \geq 4ab$ as $(a-b)^2 \geq 0.$ Now define $S$ to be the product of the numbers on the sheets. Then $S$ increases at least $4$ times after each operation. Hence finally, $S \geq 4^{m \cdot 2^{m-1}}.$ Now simple AM-GM applied to the numbers finally on the sheets implies the result.

I think I'm missing something because my solution is much simpler than all of yours. Please tell me where I've gone wrong. Without loss of generality, let's keep the sheets in ascending order (left to right). After each move, they'll be sorted again. In order to keep the total number as small as it can be, we will always select the two leftmost sheets for each move. If all $2^m$ sheets are the same, then after $2^m/2=2^{m-1}$ moves, the total will double. So after $m2^{m-1}$ moves, the total number will have doubled $m$ times, so the total will be $2^m*2^m=2^{2m}=4^m$. This is when we are keeping the total as low as possible, so if we aren't, the total will be greater than $4^m$.

@above : you didn't prove that the greedy algorithm which consisted in minimizing step by step the sum is a global minimum. MSTang wrote: I'm guessing that one tries the sum of the numbers first, and doesn't really find anything useful; then another possible quantity would be the product. Not really. Here's how I proceeded to naturaly look up to the product : First, I tried on few cases. It appeared that the "best" way to minimize the sum was to act on the two most little value, and that it doubled the two most llitle values. Then I've obeserved that each "operation" consisted in turning $a,b$ into $a+b$, $a+b$ whose sum is exactly twice the $a,b's$ sum. Then I thought that using the sum of $log_2(a_i)$ , where $a_i$ is the number written on the $i-th$ sheet, was appropriate, as it would increase by at least 2 in each step. After a few manipulation, I've noticed that it was the same as considering product of all numbers, and then it's seasy to come up with the solution above.

I essentially did what you guys got!!!

hajimbrak wrote: 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$ This problem is very similar to ELMO 2013 C2 and this solution is very similar to the one given by Unsolved_cube there.

My solution(similar to some of the above solutions): Let $n$ denote the product of the numbers on the $2^m$ sheets of paper. It is initially $1$. Because $(a+b)^2 \geq 4ab$ we can see that at each step the new product $n' \geq 4n$. Thus after $m*2^{m-1}$ steps the final product say $n''$ is at least $4^{m*2^{m-1}}$. Now note that by AM-GM, if the sum of the $2^m$ numbers of the cards at this point is $k$ then $(\frac{k}{2^m})^{2^m} \geq n''\geq 4^{m*2^{m-1}}$ or $k \geq 4^m$ proved.

hajimbrak wrote: 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$ . Proposed by Abbas Mehrabian, Iran Let $\mathcal{S},\mathcal{P}$ denote the sum,product of the numbers respectively.Note that $(a-b)^2 \Longleftrightarrow (a+b)^2\geq 4ab \implies \tfrac{(a+b)^2}{ab}\geq 4$.Hence in each move $\mathcal{P}'\geq 4 \mathcal{P}$.The initial product was $1$.So after $m\cdot 2^{m-1}$ moves The product $\mathcal{P}\geq 4^{m\cdot 2^{m-1}}$.Now By AM-GM $$\mathcal{S}\geq 2^m\cdot \sqrt[2^m]{\mathcal{P}}\geq 2^m\cdot 2^m=4^m$$as desired.$\blacksquare$

Please check my Solution because it is absolutely different from the previous solutions and might be wrong. It is obviously not as elegant as the previous solutions.

You show that you can have $4^n$ as a result, but you don't prove that it's the minimum. To do so, you can't suggest an algorithm wich attains this minimum but must explain why a better algorithm doesn't exist. For such question monovariant are often the only way. The fact that you used a greedy algorithm doesn't imply it is the most efficient one. It is just the most efficient "step by step", but you can't prove that it's the best one globaly.

Let $\mathcal{P}$ denote the product of the numbers on all $2^m$ sheets of paper. Notice that since $(a + b)^2 \geq 4ab$, the product $\mathcal{P}$ increases by at least $4$ every step. Hence after $m\cdot 2^{m-1}$ steps, the product $P$ becomes at least $4^{m\cdot2^{m-1}} = 2^{m\cdot 2^m}$. Let $a_1, a_2, \ldots a_k$ denote the numbers on the papers after the moves, where $k = m\cdot 2^{m-1}$. By AM-GM, we have\[a_1 + a_2 + \ldots + a_k \geq 2^m \cdot \mathcal{P}^{\frac{1}{2^m}} \geq 2^m\cdot \left(2^{m\cdot 2^m}\right)^{\frac{1}{2^m}} \geq 4^m\]as desired. Exactly $4^m$ can be achieved if we apply all operations on the same two elements. Remark: Dam$\textbf{}$n this took long to come up with (a littler longer than a year). Solution was short enough though, so by infinite monkey I still took the dub

hajimbrak wrote: 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$ . Proposed by Abbas Mehrabian, Iran Expansion We have $n^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 $n$ sheets are $x_1,x_2,...,x_n$, then we erase these numbers and write the number $x_1+x_2+...+x_n$ on $n$ sheets. Prove that after $m.n^{m -1}$ steps, the sum of the numbers on all the sheets is at least $n^{2m}$ .

Darn this was tricky The key is to focus on the product of the $2^m$ numbers, instead of the sum. Claim: Whenever the operation is performed, the resulting product of the $2^m$ increases by at least $4$ times. Proof: $(a+b)^2 \geq 4ab$. Now, at the end of the $m2^{m-1}$ steps, the product will be at least $4^{m2^{m-1}} = 2^{2^m}$, so by AM-GM, the sum of the $2^m$ sheets of paper is at least $2^m \cdot 2^m = 4^m$, as desired. Remark: There are three main factors that motivate this solution. Firstly, the bound on this problem is quite loose, which suggests that a strict and rigid understanding of the process likely isn't the key, but rather involves using some pretty general bounding methods. In addition, all of the constants in this problem feel much more multiplicative than additive, which suggests considering the product instead of the sum. Lastly, the equality case is when all the sheets have equal value, which prompts using algebraic inequalities like AM-GM over combinatorical reasoning.

Claim: After each step the product of the numbers is always 4 or more times the previous product. Order the sequence of papers such that the one that contain $a,b$ are at front and the product the numbers of the last $2^m-2$ sheets is $z$. Then, at the beginning, before making a move, the product of all numbers is: $$ab \cdot (2^m-2)$$and after one step; it is: $$(a+b)^2 \cdot (2^m-2)$$Since $(a+b)^2 \ge 4ab$, our claim is proven. The desired result follows$\blacksquare$.

AZOT1 wrote: Expansion:We have $n^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 $n$ sheets are $x_1,x_2,...,x_n$, then we erase these numbers and write the number $x_1+x_2+...+x_n$ on $n$ sheets. Prove that after $m.n^{m -1}$ steps, the sum of the numbers on all the sheets is at least $n^{2m}$ . solution Consider the product of the $n^m$ numbers. Each step multiplies it by at least $n^n$ since $(y_1+y_2+...+y_n)^n\geq n^n.y_1...y_n$ for all real $y_1,y_2,...,y_n$, so the product at the end of all the steps is at least $(n^n)^{mn^{m-1}}=n^{m.n^m}$. By AM-GM, the sum is then at least $n^m\sqrt[n^m]{n^{m.n^m}}=n^m\cdot n^m=n^{2m}$.

Note that in each move, the product of all of the numbers on the board is multiplied by \[\frac{(a+b)^2}{ab}\ge 4.\]So the product of all of the numbers on the board after $m2^{m-1}$ moves is at least \[4^{m2^{m-1}}=2^{m2^m}.\]AM-GM immediately finishes.

Lasitha_Jayasinghe wrote:

Actually, this proves that the "sum" is locally minimal, but it doesn't prove that it is globally minimal which you need to do in this problem. This was a common mistake I guess, I also fakesolved like this at first.

Yes, so I believe that monovariants are the only way (hence why almost everyone has used the AM-GM method)

certainly a problem of all time

Claim: The, ratio of the numbers, after every step(taking the product), is at least $4.$ Proof: Note, that this is $\frac{(a+b)^2}{ab},$ now, by AM-GM, we have $\frac{a^2+b^2}{2} \ge \sqrt{a^2\cdot b^2}=ab$, hence, $a^2+b^2 \ge 2ab.$ Now, note that $(a+b)^2=(a^2+b^2)+2ab \ge 4ab,$ hence, the ratio, is at least $4.$ So, the product, is at least, $4^{m\cdot 2^{m-1}},$ now we let the numbers, be $a_1, a_2, a_3, a_4, ....., a_{2^m},$ then, by AM-GM we have that $\frac{a_1+a_2+a_3+.....+a_{2^m}}{2^m} \ge \sqrt[2^m]{4^{m\cdot 2^{m-1}}}$, multiplying, both sides, by $2^m,$ holds, $a_1+a_2+a_3+.....+a_{2^m} \ge 2^m \cdot \sqrt[2^m]{4^{m\cdot 2^{m-1}}}=4^m,$ hence, our proof is done.

Note that $(a+b)^2\geq 4ab$, so the product at least quadruples each move, so at the end the product is at least $2^{m\cdot 2^m}$. By AM-GM, this means that the sum is at least $4^m$.

in class $\text{sol}^n$ Note $(a + b)^2 \geq 4ab$ since $(a - b)^2 \geq 0$ by Trivial Inequality. This indicates that the product is increasing by four times each step. $$\text{After } m2^{m-1} \text{steps, the product would be} \geq 4^{m2^{m-1}} = 2^{m2^m}$$By AM-GM, after all steps, we notice that: $$\frac{\text{sum of numbers on all sheets}}{2^m} \geq \sqrt[2^m]{2^{m2^m}} \implies \text{sum of numbers on all sheets} \geq 4^m$$

Let $P_k$ denote the product on numbers of numbers of the papers, namely, $P_0=1$. Now, note that if the $k$'th operation is on the numbers $a$ and $b$ then we see that \[ P_k = P_{k-1} \cdot \frac{(a+b)^2}{ab} \geq P_{k-1} \cdot \frac{\left ( 2\sqrt{ab} \right )^2}{ab} = 4 \cdot P_{k-1} \implies P_k \geq 4^k \]If we let $S_k$ denote the sum of all the numbers after $k$ operations, then we have \[ \frac{S_k}{2^m} \geq \sqrt[2^m]{P_k} \geq \sqrt[2^m]{4^k}=4^{\frac{k}{2^m}}\]Setting $k=m2^{m-1}$ yields \[ \frac{S_{m2^{m-1}}}{2^m} \geq 4^{\frac{m}{2}} \implies S_{m2^{m-1}} \geq 4^m \]Implying the result.

By AM-GM, we have $(a + b)^2 \ge 4ab$, so the product of all numbers on the sheets is multiplied by at least $4$ with every move. Thus, after $m2^{m - 1}$ moves is at least $4^{m2^{m - 1}} = 2^{m2^m}$. By AM-GM, this means the sum of all numbers is at least $$2^m\sqrt[2^m]{2^{m2^m}} = 2^m \cdot 2^m = 4^m,$$as desired.

What!!!! Notice $(a+b)^2\ge 4ab$ so the product is multiplied by at least $4$ every move so after $m2^{m-1}$ moves the product is $\ge 4^{m2^{m-1}}.$ Then the geometric mean is $\ge 2^m$ and the arithmetic mean is $\ge 2^m$ so the sum is $\ge 4^m$

By AM-GM we have $(a+b)^2 \geq 4ab$ so the product of the $2^m$ cards increases by at least $4$ each move. So then the product of the $2^m$ cards is at least $4^{m2^{m-1}}$, and by AM-GM we have that the sum of the cards is at least $4^{m/2} \cdot 2^m = 4^m$ as desired.

Each move increases the product by at least a factor of $4$, so we are immediately done by noticing the final product is at least $4^{m2^{m -1}}$ and using AM-GM.

REALLLLLLLYC2?? TOO EASY FOR A C2

Good question