Eliminar el mínimo número de elementos

Question

Dadas las cifras $ 1,2,..,2n + 1 $ , $ n > 0$ Elimina el menor número posible de números, de modo que entre los números restantes ningún número sea igual a la suma de otros dos números.

Después de retirar la primera $n$ números , los números restantes satisfacen la propiedad requerida. Estoy convencido de que al menos $n$ hay que eliminar los números para que no sea posible hacerlo mejor, pero no puedo probarlo.

Answer 1

Sin duda es suficiente para eliminar $n$ números: podemos eliminar todos $n$ números pares. Entonces todos los números que quedan son Impares, por lo que la suma de dos cualesquiera de ellos es par y en particular ninguno de los números que quedan.

Para demostrar que necesitamos eliminar al menos $n$ números, considere el mayor número $M$ que queda. Distinguimos dos casos:

• $M = 2\ell+1$ es impar. Hemos eliminado todos $2(n-\ell)$ números mayores que $M$ y también tenemos que eliminar un número de cada uno de los $\ell$ pares $(1,2\ell)$ , $(2,2\ell-1)$ , ... $(\ell,\ell+1)$ . Así que eliminamos al menos $2(n-\ell) + \ell= 2n-\ell \geq n$ números (como $\ell \leq n$ ).

• $M = 2\ell$ es par. Ahora hay $2(n-\ell)+1$ números mayores que $M$ y podemos formar $\ell-1$ pares: $(1,2\ell-1)$ hasta $(\ell-1,\ell+1)$ . Así que de nuevo eliminamos al menos $2(n-\ell) + (\ell-1) = 2n - \ell \geq n$ números.

En cada caso, vemos que al menos $n$ hay que eliminar los números.