Problem 1

Consider the following operation on positive real numbers written on a blackboard: choose a number

r

written on the blackboard, erase that number, and then write a pair of positive real numbers

a

and

b

satisfying

2r^2=ab

on the board. Assume that you start out with just one positive real number

r

on the blackboard, and apply this operation

k^2-1

times to end up with

k^2

positive real numbers, not necessarily distinct. Show that there exists a number on the board which does not exceed

kr

Step 2 of 4: Define the invariant sum

Previous step Next step

S_0=\frac1{r^2},\quad S_\ell=\sum\frac1{x^2},\quad S_0\le S_1\le\cdots\le S_{k^2-1}

Detailed analysis

Let $S_\ell$ be the sum of reciprocal squares of all numbers on the board after $\ell$ operations. The estimate for one replacement shows $S_\ell$ is nondecreasing, and initially $S_0=1/r^2$ . Thus $S_{k^2-1}\ge1/r^2$ .