Maths Olympiad Prep

Library / /86 of 105

Algebra Difficulty 5.4 AIME, harder Prove it United States

Problem:

Let nn be a fixed positive integer. Initially, nn 11's are written on a blackboard. Every minute, David picks two numbers xx and yy written on the blackboard, erases them, and writes the number (x+y)4(x+y)^4 on the blackboard. Show that after n1n-1 minutes, the number written on the blackboard is at least 24n2432^{\frac{4 n^{2}-4}{3}}.

Solution

Solution:

We proceed by strong induction nn, with the base case n=1n=1 being vacuous. For the inductive step, consider the situation in which we have two numbers xx and yy remaining on the blackboard. Suppose the first one was written after a1a-1 operations, and the second one was written after b1b-1 operations, so that (a1)+(b1)=n2(a-1)+(b-1)=n-2. Then by the inductive hypothesis,
x24a243,y24b243 x \geq 2^{\frac{4 a^{2}-4}{3}}, \quad y \geq 2^{\frac{4 b^{2}-4}{3}}
Consequently, using convexity and the bound (a+b)22(a2+b2)(a+b)^{2} \leq 2\left(a^{2}+b^{2}\right), we have
x+y222(a2+b2)432(a+b)213=2n213. x+y \geq 2 \cdot 2^{\frac{2\left(a^{2}+b^{2}\right)-4}{3}} \geq 2^{\frac{(a+b)^{2}-1}{3}}=2^{\frac{n^{2}-1}{3}} .
So (x+y)424n243(x+y)^{4} \geq 2^{\frac{4 n^{2}-4}{3}} as needed.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.