Seja S um conjunto de
inteiros positivos. Nenhum dos elementos de S é divisível por
. Prove que existe um subec S tal que a soma de feus elementos é divisível por
Passo 1
Resumo do enunciado: Temos um conjunto S com n números inteiros positivos, nenhum deles divisível por n. Precisamos provar que existe um subconjunto não‐vazio de S cuja soma seja divisível por n.
Conteúdo envolvido:
Conteúdo envolvido:
- Aritmética modular (restos da divisão por n).
- Princípio da casa dos pombos (pigeonhole principle).
O que vamos usar: conceitos de resto (mod n), a ideia de “soma parcial” e o fato de que, se dois somatórios têm o mesmo resto, a diferença deles é múltipla de n.
Passo 2
Primeiro, pegue uma ordem qualquer para os elementos de S e chame-os de
Defina as somas parciais
Cada
deixa um resto
, que pode ser
.
– Se algum , então a soma do subconjunto
já é divisível por
e acabamos.
– Se algum
Passo 3
Suponha que nenhum
seja zero. Então cada resto
está em
. Mas temos
valores
e só
“caixinhas” possíveis para esses restos.
Pelo princípio da casa dos pombos, existem índices tais que
Pelo princípio da casa dos pombos, existem índices
Isso significa
Passo 4
Observe que
Esse é um subconjunto não‐vazio de S (pois
Resposta
Logo, sempre existe um subconjunto não‐vazio de S cuja soma é divisível por
.