Congruencias y las palomas

Question

La pregunta es esta:

Dado $n$ enteros, $(a_1, \dotsc, a_n)$, muestran que existe algún subconjunto $B\subseteq \{1,\dotsc, n\}$, de tal manera que $$\sum_{i\in B}i \equiv 0 \bmod n.$$

Se ve que le gusta esta debe ser una aplicación de la encasillar principio, pero yo estoy luchando para ver cómo se aplican.

Gracias.

Answer 1

Sugerencia: Considere los números $$a_1,\quad a_1+a_2,\quad a_1+a_2+a_3,\dots, a_1+a_2+\cdots+a_n.$$ Si uno de ellos es divisible por $n$, estamos acabados. Si ninguno es divisible por $n$, hay entre estos no más de $n-1$ distintos resto en la división por $n$.

Así que por el Principio del Palomar, debe haber dos con el mismo resto. El uso de este para llegar a la conclusión deseada.