Library / /2 of 10

, 2015

Algebra Difficulty 4.5 AIME Prove it Taiwan

遊戲開始時有 $2^m$ 張紙，每張上寫有一個 $1$ 。考慮以下操作：每次我們選兩張紙，假設其上的數字分別為 $a$ 與 $b$ 。將兩張紙上的數字都擦掉，並在兩張紙上都寫上 $a+b$ 。
試證：經過 $m2^{m-1}$ 步後，所有紙上的數字總和至少為 $4^m$ 。

Solution

At the start of the game there are $2^m$ pieces of paper, each with a $1$ written on it. Consider the following operation: each time we choose two pieces of paper, and suppose the numbers written on them are $a$ and $b$ respectively. We erase the numbers on both pieces of paper, and write $a+b$ on both pieces of paper.
Prove that after $m2^{m-1}$ steps, the sum of the numbers on all the pieces of paper is at least $4^m$ .

Let $P_k$ be the product of the numbers on all pieces of paper after the $k$ -th operation, and let $S_k$ be the sum of the numbers on all pieces of paper after the $k$ -th operation. Clearly $P_0 = 1$ . Also, based on $(a+b)^2 \ge 4ab$ , it is easy to see that $P_{k+1} \ge 4P_k$ , so $P_{m2^{m-1}} \ge 4^{m2^{m-1}} = (2^m)^{2^m}$ . Finally, by the AM-GM inequality, $S_k \ge 4^m$ . This completes the proof.

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 translated into English from zh; metadata (topic, difficulty) added by this project.