O teorema de Svéd-Vázsonyi

Novo artigo de Andrés Ventas

O principio do Pombal

O principio do Pombal di que se temos $n$ buratos nun pombal e $n+1$ pombas daquela nalgún burato hai máis dunha pomba. Nunca souben para que podía servir algo tan obvio, ultimamente quixen profundar algo máis e deime conta que a sustanza deste principio reside en como podemos enfocar os problemas para poder usalo e así transformamos problemas nada evidentes en problemas cunha demostración moito simple. Un caso que me fascina é o teorema que se atribúe a Marta Svéd e Andrew Vázsonyi. Trata sobre secuencias aleatorias e divisivilidade.

Teorema de Sved-Vázsonyi

Sexan os enteiros $a_1, a_2, \cdots, a_n$, que poden mesmo estar repetidos. Daquela hai un subconxunto de elementos consecutivos desa secuencia $a_k, a_{k+1}, \cdots, a_l$ tal que a suma $a_k + a_{k+1} + \cdots, a_l$ é un múltiplo de $n$.

Exemplo

Mais como pode ser tal cousa? Se eu apaño $n$ números e os sumo poden ser múltiplos de calquera cousa, eu que sei, sumarán un múltiplo de $17$ ou de $3015$ ou de $2$, como que haberá unha desas sumas que sexa división exacta por $n$? non o vexo. A ver: $\{3, 7, 1, 4, 1, 1\}$ temos $n=6$ e imos probrar o máis simple, sumas consecutivas desde o primeiro: $\{0, 3, 10, 11, 15, 16, 17\}$, mmm... ningunha é divisíbel por $6$, desde o segundo $\{0, 7, 8, 12, \cdots \}$ cazado !! $7 + 1 + 4$ é múltiplo de $6$.

Demostración

Sexa $S=\{0, 1, \cdots, n\}$ e $R=\{0, 1, \cdots, n-1\}$ e consideremos o mapa $f: S \rightarrow R$ determinado polo residuo de $f(m)=a_1 + \cdots + a_m$ módulo $n$. Polo principio do pombal temos $f(k)=f(l)$ para algún $k \lt l$ en $S$ e por tanto

$$ \begin{equation} \sum_{i=k+1}^{l} a_i = \sum_{i=1}^{l} a_i - \sum_{i=1}^{k} a_i \end{equation} $$ faise cero módulo $n$. O subconxunto $a_k, a_{k+1}, \cdots a_l$ ten a propiedade procurada, a súa suma é múltiplo de $n$.

Exemplo aplicando a demostración

Seguindo a demostración agora é moito simple obter o subconxunto de elementos consecutivos cuxa suma é divisíbel polo número total de elementos. Para $\{3, 7, 1, 4, 1, 1\}$ con sumas parciais $\{0, 3, 10, 11, 15, 16, 17\}$ os residuos entre $6$ son $\{0, 3, 4, 5, 3, 4, 5\}$, vemos que hai dous residuos $3$ e dous $4$ e dous $5$, polo principio do pombal debe haber alomenos $2$ pombas no mesmo burato, pero pode haber máis (se hai outros buratos baleiros). Así temos:

1. entre os dous $3$: $7+1+4 = 12$.
2. entre os dous $4$: $1+4+1 = 6$.
3. entre os dous $5$: $4+1+1 = 6$.

Vexamos outro exemplo ao chou.

Para $n=9$ con $\{2, 8, 4, 1, 19, 17, 2, 3, 12\}$.

Sumas consecutivas $\{0, 2, 10, 14, 15, 34, 51, 53, 56, 68\}$.

Residuos módulo $9$, $\{0, 2, 1, 5, 6, 7, 6, 8, 2, 5\}$.

E seguindo a demostración:

1. de residuo 2 a 2 temos $56 - 2 = 54 = 9 \cdot 6$.
2. de 6 a 6 temos $19 + 17 = 36 = 9 \cdot 4$.
3. de 5 a 5 temos $68 - 14 = 54 = 9 \cdot 6$.

Fascinante!

Bibliografia

1. Vincent Gélinas, The Pigeon-Hole Principle and Double Counting,