Problema. Se nos da $2000$ enteros, cada uno con valor absoluto menos de $1000$ y con la suma igual a $1$. Demostrar que podemos elegir algunos de ellos con suma igual a $0$.
Aquí está mi solución:
Supongamos que los números se $X = \{a_1, a_2, ..., a_{2000} \}$.
Primero elige una al azar $a_i$ y llamar a $x_1$. Deje $S_1 = x_1$ y construimos $(S_i)_{1 \leq i \leq n}$ con el siguiente algoritmo recursivo:
Elija un elemento $x_i$ $X$ que satisface $|S_{i-1} + x_i| <1000$ y quitarlo de $X$.
$S_i = S_{i-1} + x_i$, en particular, $|S_i| < 1000$.
Me dicen que siempre es posible encontrar una $x_i$ a satisfacer paso $1$. Supongamos lo contrario, es decir, existe $S_k = x_1 + x_2 + ... + x_k$ e no $x_{k+1}$ existe.
WLOG, podemos suponer $S_k > 0$. Así, para cada $a_i \in X$,$a_i \geq 1000 - S_k$. Pero esto es imposible, ya que $a_1 + a_2 + ... + a_{2000} = 1$.
Por lo tanto, podemos generar
\begin{align*} S_1 & = x_1 \\ S_2 & = x_1 + x_2 \\ & \vdots \\ S_{2000} & = x_1 + x_2 + ... + x_{2000} \end{align*} Sabemos que $-999 \leq S_1, S_2, ..., S_{2000} \leq 999$ así que por Pigeon-hole, al menos dos $S_i$ son iguales. Pero podemos restar estos dos para obtener un subconjunto de a$a_i$, que se suma a $0$.
¿Alguien tiene algún comentario que hacer esto más claro? También me encantaría ver otra solución!
