Mostre que em qualquer coleção de
inteiros há um subconjunto cuja soma dos elementos é divisivel por
.
Soluçäo:
Podemos separar os 11 inteiros (
) da seguinte forma:
Se um destes somatórios for divisivel por n , então acabou o problema.
Caso nenhum destes somatórios seja divisivel por
, temos
restos de divisão por
que estes termos podem assumir. Como temos
somatórios e
restos possíveis, teremos dois somatórios com mesmo resto quando dividido por n.
Subtraindo estes dois somatórios obteremos um somatório que é divisivel por ne da forma
Soluçäo:
Podemos separar os 11 inteiros (
Se um destes somatórios for divisivel por n , então acabou o problema.
Caso nenhum destes somatórios seja divisivel por
Subtraindo estes dois somatórios obteremos um somatório que é divisivel por ne da forma
Passo 1
O enunciado pede que, dados
inteiros quaisquer
, mostremos que existe sempre um subconjunto não vazio cuja soma dos elementos é divisível por
. O plano é usar somas parciais e o princípio da casa dos pombos (pigeonhole principle).
Passo 2
Definimos para cada
a soma parcial
Se algum desses
for congruente a zero módulo
, ou seja, se
então o próprio conjunto
tem soma divisível por
e já terminamos a prova.
Passo 3
Suponha, então, que nenhum
seja congruente a zero módulo
. Cada
deixa um resto em
quando dividido por
. Como temos
somas parciais e apenas
valores possíveis de resto, pelo princípio da casa dos pombos existem dois índices
tais que
Passo 4
Desses índices
vemos que
é congruente a zero módulo
. Logo a soma dos elementos do subconjunto
é divisível por
.
Resposta
Mostramos que sempre existe um subconjunto não vazio cuja soma é múltiplo de
.