Track / Stage 4 / 156 of 340 #896 of 2444

Problem 896

AMC 12 late, AIME early

Combinatorics Difficulty 4.7 Prove it All-Soviet-Union Mathematical Olympiad · Soviet Union

$n$ numbers are written on a blackboard. Someone then repeatedly erases two numbers and writes half their arithmetic mean instead, until only a single number remains. If all the original numbers were $1$ , show that the final number is not less than $1/n$ .

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:

Put $c = (a + b)/4$ . We have $1/c = 4/(a + b) \leq 1/a + 1/b$ , so each move does not increase the sum of the reciprocals of the numbers. If the final number is $k$ , then the final sum of reciprocals is $1/k$ . The initial sum is $n$ , so $1/k \leq n$ , or $k \geq 1/n$ .

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