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 5(0,1,2,3,4) então basta pegar um número de cada resto que a soma destes cinco números vai ser divisivel por 5 :
5 q_{1}+0+5 q_{2}+1+5 q_{3}+2+5 q_{4}+3+5 q_{5}+4=5\left(q_{1}+q_{2}+q_{3}+q_{4}+q_{5}+2\right)
Suponhamos agora que um dos restos năo esteja presente. Assim, sobram quatro restos possiveis.
Como 17=4.4+1, 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 :
5 q_{1}+r+5 q_{2}+r+5 q_{3}+r+5 q_{1}+r+5 q_{5}+r=5\left(q_{1}+q_{2}+q_{3}+q_{4}+q_{5}+r\right)

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: \{0,1,2,3,4\}. 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
5q_{1}+0,\quad 5q_{2}+1,\quad 5q_{3}+2,\quad 5q_{4}+3,\quad 5q_{5}+4.
Então a soma é
(5q_{1}+0)+(5q_{2}+1)+(5q_{3}+2)+(5q_{4}+3)+(5q_{5}+4) =5\bigl(q_{1}+q_{2}+q_{3}+q_{4}+q_{5}+2\bigr),
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
\bigl\lceil\tfrac{17}{4}\bigr\rceil =5
pombos, ou seja, há 5 números com o mesmo resto r\in\{0,1,2,3,4\}. Esses cinco números podem ser escritos como
5q_{1}+r,\;5q_{2}+r,\;5q_{3}+r,\;5q_{4}+r,\;5q_{5}+r.
A soma deles é
(5q_{1}+r)+(5q_{2}+r)+(5q_{3}+r)+(5q_{4}+r)+(5q_{5}+r) =5\bigl(q_{1}+q_{2}+q_{3}+q_{4}+q_{5}+r\bigr),
também divisível por 5.

Resposta

Em qualquer caso, conseguimos cinco dos 17 números cuja soma é múltipla de 5.

Exercícios de Livros Relacionados