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