Track / Stage 5 / 237 of 400 #1317 of 2444

Problem 1317

AIME late

Algebra Difficulty 5.4 Prove it Berkeley Math Circle · United States

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

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

We proceed by strong induction $n$ , with the base case $n=1$ being vacuous. For the inductive step, consider the situation in which we have two numbers $x$ and $y$ remaining on the blackboard. Suppose the first one was written after $a-1$ operations, and the second one was written after $b-1$ operations, so that $(a-1)+(b-1)=n-2$ . Then by the inductive hypothesis,
$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)^{2} \leq 2\left(a^{2}+b^{2}\right)$ , we have
$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)^{4} \geq 2^{\frac{4 n^{2}-4}{3}}$ as needed.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.