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 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\$.