Mostre que dados 17 números naturais é possível escolher 5 deles cuja soma seja divisivel por 5.
Solução:
Divida todos os 17 números por 5 e anote o resto. Se entre os 17 números existirem todos os cinco restos da divisão por
então basta pegar um número de cada resto que a soma destes cinco números vai ser divisivel por 5 :
Suponhamos agora que um dos restos năo esteja presente. Assim, sobram quatro restos possiveis.
Como
, então entre os 17 números há 5 que deivam o mesmo resto na divisão por 5 . A soma destes 5 números é divisivel por 5 :
Solução:
Divida todos os 17 números por 5 e anote o resto. Se entre os 17 números existirem todos os cinco restos da divisão por
Como
Passo 1
O enunciado pede para mostrar que, dados 17 números naturais, sempre é possível escolher 5 deles cuja soma seja divisível por 5. O conteúdo principal é a teoria de resíduos (classes modulares) e o princípio da casa dos pombos (pigeonhole principle).
Passo 2
Classificamos os 17 números pelos seus restos na divisão por 5. Há cinco classes de resto possíveis:
. Se todas as cinco classes aparecem pelo menos uma vez entre os 17 números, basta escolher um número de cada classe. Suponha que esses números sejam
Então a soma é
que é claramente divisível por 5.
Passo 3
Se alguma das cinco classes de resto não aparece, restam apenas quatro restos possíveis entre os 17 números. Pelo princípio da casa dos pombos, ao distribuir 17 “pombos” em 4 “caixas”, alguma caixa conterá pelo menos
pombos, ou seja, há 5 números com o mesmo resto
. Esses cinco números podem ser escritos como
A soma deles é
também divisível por 5.
Resposta
Em qualquer caso, conseguimos cinco dos 17 números cuja soma é múltipla de 5.