The numbers $1, 2, \ldots, n$ are written on a blackboard. Each minute, a student goes up to the board, chooses two numbers $x$ and $y$, erases them, and writes the number $2x+2y$ on the board. This continues until only one number remains. Prove that this number is at least $\frac{4}{9}n^3$. Brian Hamrick.
Problem
Source: ELMO Shortlist 2010, C4
Tags: integration, combinatorics proposed, combinatorics
19.07.2012 14:34
Let $a$ be the remaining number. Since $\sqrt{x}+\sqrt{y} \le \sqrt{2(x+y)}$, we must have $\sqrt{1}+ \cdots +\sqrt{n} \le \sqrt{a}$. But $\sum_{i=1}^n \sqrt{i} \ge \int_0^{n} \sqrt{x} dx = \frac{2}{3} n^{\frac{3}{2}}$, so $a \ge \frac{4}{9}n^3$.
19.07.2012 20:18
Alternatively, note that the final sum is of the form $\sum_{k=1}^{n}2^{a_k}k$, where $\sum_{k=1}^{n}2^{-a_k}=1$. After Cauchy, we can finish in the same way as the previous poster did. Note that ISL 2007 A5 has a similar condition ($\{x,y\}\to\{2x+2y\}$).
28.09.2018 15:57
Let $x_1,x_2,x_3 \cdots x_n$ be the order of doing the operations.Then the last number left on the board will be $$a=2^1\cdot n + 2^2\cdot n-1+ \cdots 2^{n-1}\cdot 2 + 2^{n-1}\cdot 1$$for the minimum condition by rearrangement inequality.This also $\implies a=7 \cdot 2^n-1 -2n-4$ Or we have to prove $7 \cdot 2^n-1 -2n-4 \geq \frac {4n^3} {9}$ We process by induction on $n$ So for $n=1$ it is obviously true So enough to prove that $2n^3-6n^2+3n+7 \geq 0$ Or $n(2n^2-6n+3)+7 \geq 0$ But for $n \geq 3 $ LHS $\geq $ 0 Hence we need to check for $n \leq 3$ which is true Done! Hope this correct
11.02.2019 21:22
??
02.04.2019 16:31
@thetwoabove. Actually by setting $n=2^k$ for some positive integer $k$, and operate on every number each turn, you would get $a=2^k \times \frac{n(n+1)}{2}=\frac{n^2(n+1)}{2}$, which means that you could nearly get $\frac{1}{2}n^3$ for large enough $n$. So your proof is wrong.
02.04.2019 16:34
A non-trivial question remains for the best coefficient before $n^3$, and I would guess (reasonably) that $\frac{1}{2}$ is the best. (Although $a\geqslant \frac{n^2(n+1)}{2}$ fails for $n=5$.)