Teorema de Svéd-Vázsonyi

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. O teorema que se atribúe a Márta Svéd e Andrew Vázsonyi usa este principio e trata sobre secuencias aleatorias e divisivilidade.

Dada unha secuencia de Modelo:Mvar números aleatorios existe unha subsecuencia consecutiva cuxa suma é divisíbel polo número de elementos da secuencia orixinal.

Teorema de Svéd-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

Para unha secuencia aleatoria $\{3,7,1,4,1,1\}$ temos $n=6$ se probramos o máis simple, sumas consecutivas desde o primeiro: $\{0,3,10,11,15,16,17\}$, non temos ningunha divisíbel por $6$, mais se sumamos desde o segundo $\{0,7,8,12,\cdots \}$ temos a secuencia con suma $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 </math>k \lt l</math> 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 a secuencia aleatoria $\{3,7,1,4,1,1\}$ con sumas parciais $\{0,3,10,11,15,16,17\}$ os residuos ao dividir 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 (dous residuos iguais), pero pode haber máis (se hai outros buratos baleiros). Así temos:

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

Vexamos outro exemplo ao chou.

• Para $n=9$ coa secuencia$\{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:

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

Véxase tamén

Bibliografía

• Modelo:Cita web

• Modelo:Cita libro

Outros artigos

• Principio do pombal.