Teorema de Svéd-Vázsonyi

O principio do pombal di que se temos  buratos nun pombal e  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  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 , que poden mesmo estar repetidos. Daquela hai un subconxunto de elementos consecutivos desa secuencia  tal que a suma  é un múltiplo de .

Exemplo
Para unha secuencia aleatoria  temos  se probramos o máis simple, sumas consecutivas desde o primeiro: , non temos ningunha  divisíbel por , mais se sumamos desde o segundo  temos a secuencia con suma  é múltiplo de .

Demostración
Sexa  e   e consideremos o mapa  determinado polo residuo de  módulo . Polo principio do pombal temos  para algún </math>k \lt l</math> en  e por tanto

faise cero módulo . O subconxunto  ten a propiedade procurada, a súa suma é múltiplo de .

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  con sumas parciais  os residuos ao dividir entre  son , vemos que hai dous residuos  e dous  e dous , polo principio do pombal debe haber polo menos  pombas no mesmo burato (dous residuos iguais), pero pode haber máis (se hai outros buratos baleiros).
Así temos:
 entre os dous . 
 entre os dous . 
 entre os dous . 

Vexamos outro exemplo ao chou.
 Para  coa secuencia.
 Sumas consecutivas . 
 Residuos módulo .
E seguindo a demostración:
 de residuo 2 a 2 temos .
 de 6 a 6 temos .
 de 5 a 5 temos .

 Notas 


 Véxase tamén 

 Bibliografía 




 Outros artigos 
 Principio do pombal.

Categoría:Teoremas
Categoría:Teoría de números