En una secuencia de $n$ enteros, ¿debe existir una subsecuencia contigua que sume un múltiplo de $n$ ?

Question

Sea $x_1, \ldots, x_n$ sean números enteros. Entonces, ¿existen índices $1\le a\le b\le n$ tal que $$\sum_{i=a}^b x_i$$ es múltiplo de $n$ ?

Answer 1

Sea $$s_k = \sum_{i=1}^k x_i\pmod n.$$ Si $s_k$ es cero para cualquier $k$ hemos encontrado la subsecuencia deseada ( $a=1, b=k$ ), así que supongamos que todos los $s_k$ son distintos de cero. Hay $n$ de ellos, cada uno en el rango $1,\ldots,n-1$ así que dos, digamos $s_{a}$ y $s_b$ deben ser iguales. Entonces como $s_b - s_a = 0$ tenemos $$\begin{align} \sum_{i=1}^b x_i - \sum_{i=1}^{a} x_i & = 0\pmod n \\ \sum_{i=a+1}^b x_i & = 0\pmod n \end{align}$$

como desee.

(Tenga en cuenta que si $a+1 = b$ no pasa nada; sólo significa que $x_b$ es múltiplo de $n$ .)