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:
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:
. Definimos os somatórios parciais
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:
- Se algum dos restos
for igual a 0, isto é, , então já é um subconjunto (os primeiros números) cuja soma é múltipla de 10. - 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 índicestais que
Passo 4
Supondo
com
, 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.