Seja S um conjunto de n inteiros positivos. Nenhum dos elementos de S é divisível por n. Prove que existe um subec S tal que a soma de feus elementos é divisível por n

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:
  • 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
a1, a2, dots, an
Defina as somas parciais
sk = a1 + a2 + cdots + ak, k=1,2,dots,n
Cada sk deixa um resto rk = sk bmod n, que pode ser 0,1,2,dots,n-1.
– Se algum rk = 0, então a soma do subconjunto a1,dots,ak já é divisível por n e acabamos.

Passo 3

Suponha que nenhum rk seja zero. Então cada resto rk está em 1,2,dots,n-1. Mas temos n valores r1,dots,rn e só n-1 “caixinhas” possíveis para esses restos.
Pelo princípio da casa dos pombos, existem índices i tais que
ri = rj
Isso significa
siequiv sjpmod n Longrightarrow sj - siequiv 0pmod n

Passo 4

Observe que
sj - si = (a1 + cdots + aj) - (a1 + cdots + ai) = ai+1 + cdots + aj
Esse é um subconjunto não‐vazio de S (pois j>i) e sua soma é múltipla de n.

Resposta

Logo, sempre existe um subconjunto não‐vazio de S cuja soma é divisível por n.

Exercícios relacionados