AlgebraDifficulty 5.4AIME, harderProve itUnited States
Problem:
Let n be a fixed positive integer. Initially, n1'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 234n2−4.
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≥234a2−4,y≥234b2−4 Consequently, using convexity and the bound (a+b)2≤2(a2+b2), we have x+y≥2⋅232(a2+b2)−4≥23(a+b)2−1=23n2−1. So (x+y)4≥234n2−4 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.