Competition problem — Combinatorics

Library / /52 of 196

Combinatorics Difficulty 4.7 AIME Prove it Soviet Union

Problem:

$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$ .

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$ .

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.