Prove que de qualquer conjunto de dez inteiros podemos escolher um subconjunto cuja soma é um múltiplo de 10.

Passo 1

Resumo da questão: temos um conjunto genérico de dez números inteiros e queremos mostrar que, dentro dele, dá para escolher algum subconjunto cuja soma é múltipla de 10.
Conteúdo envolvido: teoria dos restos (aritmética modular, em particular módulo 10) e Princípio da Casa dos Pombos (pigeonhole principle).
O que vamos usar:
  • Definição de resto de uma soma quando dividida por 10;
  • Somatórios parciais e suas classes de resto;
  • Princípio da Casa dos Pombos para garantir que dois desses restos sejam iguais.

Passo 2

Primeiro, organize os dez inteiros em uma sequência qualquer: Sk = a1 + a2 + cdots + ak, . Definimos os somatórios parciais
rk equiv Sk pmod10, rk in 0,1,2,dots,9
para cada . Agora, para cada consideramos seu resto ao dividir por 10, que chamaremos de :
Lembra que dizer é falar que divide .

Passo 3

Vejamos dois casos:
  1. Se algum dos restos Sk = a1 + dots + ak for igual a 0, isto é, ri = rj , então já é um subconjunto (os primeiros números) cuja soma é múltipla de 10.
  2. Se nenhum for zero, então todos os 10 restos estão entre 1 e 9. Mas aí temos 10 valores ocupando apenas 9 possibilidades (1,2,…,9).
    Pelo Princípio da Casa dos Pombos, existem índices tais que

Passo 4

Supondo ai+1 + cdots + aj = Sj - Si com Sj - Si equiv rj - ri equiv 0 pmod10 , consideramos o subconjunto formado pelos termos de . A soma dele é
Como e e , segue
Logo essa soma também é múltipla de 10.

Resposta

Em qualquer conjunto de dez inteiros, ou algum somatório parcial já é múltiplo de 10, ou surgem dois somatórios parciais com o mesmo resto em módulo 10. Em ambos os casos encontramos um subconjunto cuja soma é múltipla de 10. Portanto, a afirmação está provada.

Exercícios relacionados