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\to 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<l$ en $S$ e por tanto

$$\sum _{i=k+1}^l{a}_i=\sum _{i=1}^l{a}_i-\sum _{i=1}^k{a}_i$$ 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,