Competition problem — Combinatorics

Library / /15 of 18

Combinatorics Difficulty 6.3 National olympiad Prove it Austria

Written on a blackboard are the $2023$ numbers
$2023, 2023, \ldots, 2023$ .
The numbers on the blackboard are now modified, in a sequence of moves. In each move, two numbers on the blackboard—call them $x$ and $y$ —are chosen, deleted, and replaced by the single number $\frac{x+y}{4}$ . Such moves are carried out until there is only one number left on the blackboard.
Prove that this number is always greater than $1$ .

Solution

The expression $\frac{x+y}{4}$ reminds us of the arithmetic mean. By the AM-HM inequality, we have
$\frac{x+y}{2} \geq \frac{2}{\frac{1}{x} + \frac{1}{y}}$
or
$\frac{1}{x} + \frac{1}{y} \geq \frac{1}{(x+y)/4}$
This inequality leads us to consider an argument concerning the reciprocals of the numbers on the board, as the sum of the reciprocals of two of these numbers is at least as large as the reciprocal of the number replacing them. This value remains the same if and only if the two chosen numbers are equal, and is otherwise larger. At the beginning, the sum of all reciprocals is
$\frac{1}{2023} + \frac{1}{2023} + \dots + \frac{1}{2023} = \frac{2023}{2023} = 1.$
This implies the claim, since there is an odd number of $2023$ s in the beginning that cannot be divided into pairs, so one of them has to be part of a pair with different numbers.

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 and solution reproduced as published; topic and difficulty added by this site.