A removing number problem - Printable Version +- OMath! ( http://math.elinkage.net)+-- Forum: Math Forums ( /forumdisplay.php?fid=4)+--- Forum: Graph & Combinatorics ( /forumdisplay.php?fid=9)+--- Thread: A removing number problem ( /showthread.php?tid=699) |

A removing number problem - elim - 11-08-2012 02:15 PM
source (Vietnam NMO 1990_2) At least $ n - 1$ numbers are removed from the set $ A = \{1, 2, \ldots, 2n - 1\}$ according to the following rules: (i) If $ a$ is removed, so is $ 2a$; (ii) If $ a$ and $ b$ are removed, so is $ a + b$. Find the way of removing numbers such that the sum of the remaining numbers is maximum possible. RE: A removing number problem - elim - 11-08-2012 02:51 PM
We have to remove $n-1$ even numbers $2,4,\ldots,2n-2$ so the sum of the remaining is maximum! The solution is from these Lemma: Lemma1: If we remove $1$ we have to remove $2,3,\ldots$ so we remove all numbers from the set $A$ Lemma2: If we remove $2$, we remove $n-1$ numbers $2,4,\ldots,2n-2$ so the sum of remaining numbers is $n^2$ Lemma3: If we remove $p$ number $a_1<a_2<a_3<\cdots <a_p$ so we must remove the number $a_1+a_p$ but this number greater than $a_p$ so $a_1+a_p > 2n-1 $ A similar way to $a_i$ and $a_{p+1-i}$. So the sum of the number which are removed is $\ge n(n-1)$ So the sume of the remaining numbers is $< n^2$. |