On a board we have $n$ $1$'s. At each step, we choose two numbers $a$ and $b$ and we replace them with $\frac{(a+b)}{4}$. Prove that, after $n-1$ steps, the last remaining number is greater or equal to $\frac{1}{n}$
Although I couldn't solve the problem, I found some (maybe useful) properties:
- If we have the numbers $a_1 \leq a_2 \leq...\leq a_k$ on the table, then $$a_1a_2...a_k \cdot \frac{1}{a_ia_j} \cdot \frac{a_i+a_j}{4} \geq a_1a_2...a_k \cdot \frac{1}{a_{k-1}a_k} \cdot \frac{a_{k-1}+a_k}{4}$$which means that at each step the product of the numbers on the table decreases at most when we choose the two greatest numbers
- When $n=2^p$ we have equality using the fact listed above (the last number is $\frac{1}{2^p}$). We can prove by induction that for $n=2^p$ the conclusion holds
- For $n=4$ the least last remaining number is $\frac{1}{4}=\frac{8}{32}$ and for $n=5, 6, 7$ we have the values $\frac{7}{32}, \frac{6}{32}$ and $\frac{5}{32}$ and, of course, for $n=8$ it is $\frac{4}{32}=\frac{1}{8}$ and maybe we can find a formula for the least remaining number
What should I do?
The claim is obviously true for $n=1$. Assume $n>1$ and the claim is true for all smaller values. In the last step, we are left with only two numbers $a,b$ that we combine into the final result $\frac{a+b}4$. The numbers $a,b$ themselves were obtained by the same procedure, but come from fewer "ancestors". Say, $a$ has $r$ ancestors and $b$ has $s$ ancestors. We have $1\le r,s<n$ and $r+s=n$. By induction hypothesis, this makes $a\ge \frac1r$ and $b\ge \frac 1s$. Then from the arithmetic-geometric inequality $\sqrt{rs}\le\frac{r+s}2 $, we find $4rs\le(r+s)^2$ and hence $$\frac{a+b}4\ge \frac{\frac1r+\frac1s}4=\frac{r+s}{4rs}\ge \frac{r+s}{(r+s)^2}=\frac1{r+s}=\frac1n. $$