Mostre que em qualquer coleção de n inteiros há um subconjunto cuja soma dos elementos é divisivel por n.
Soluçäo:
Podemos separar os 11 inteiros ( a_{1}, a_{2}, \ldots, a_{11} ) da seguinte forma:
a_{1}
a_{1}+a_{2}
a_{1}+a_{2}+a_{3}
a_{1}+a_{2}+\ldots+a_{n}
Se um destes somatórios for divisivel por n , então acabou o problema.
Caso nenhum destes somatórios seja divisivel por n, temos n-1 restos de divisão por n que estes termos podem assumir. Como temos n somatórios e n-1 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 a_{j}+a_{j+1}+\ldots+a_{n}

Passo 1

O enunciado pede que, dados n inteiros quaisquer a_{1},a_{2},\dots,a_{n}, mostremos que existe sempre um subconjunto não vazio cuja soma dos elementos é divisível por n. O plano é usar somas parciais e o princípio da casa dos pombos (pigeonhole principle).

Passo 2

Definimos para cada k\in\{1,2,\dots,n\} a soma parcial
S_{k} \;=\; \sum_{i=1}^{k} a_{i}.
Se algum desses S_{k} for congruente a zero módulo n, ou seja, se
S_{k}\equiv 0\pmod{n},
então o próprio conjunto \{a_{1},\dots,a_{k}\} tem soma divisível por n e já terminamos a prova.

Passo 3

Suponha, então, que nenhum S_{k} seja congruente a zero módulo n. Cada S_{k} deixa um resto em \{1,2,\dots,n-1\} quando dividido por n. Como temos n somas parciais e apenas n-1 valores possíveis de resto, pelo princípio da casa dos pombos existem dois índices i<j tais que
S_{i}\equiv S_{j}\pmod{n}.

Passo 4

Desses índices i<j vemos que
S_{j}-S_{i} \;=\; \sum_{k=1}^{j}a_{k} \;-\; \sum_{k=1}^{i}a_{k} \;=\; \sum_{k=i+1}^{j}a_{k}
é congruente a zero módulo n. Logo a soma dos elementos do subconjunto \{a_{i+1},a_{i+2},\dots,a_{j}\} é divisível por n.

Resposta

Mostramos que sempre existe um subconjunto não vazio cuja soma é múltiplo de n.

Exercícios de Livros Relacionados