Suponha que todo estudante em uma classe de matemática discreta de 25 alunos seja um calouro, um veterano ou um aluno júnior.
a) Mostre que há pelo menos nove calouros, nove veteranos ou nove juniores na sala.
b) Mostre que há pelo menos três calouros, 19 veteranos ou 5 juniores na sala.
a) Mostre que há pelo menos nove calouros, nove veteranos ou nove juniores na sala.
b) Mostre que há pelo menos três calouros, 19 veteranos ou 5 juniores na sala.
Passo 1
O enunciado diz que há 25 estudantes e cada um é calouro, veterano ou júnior. Vamos usar o princípio da casa dos pombos, que em geral diz que, se distribuímos
objetos em
caixas, alguma caixa tem pelo menos
objetos.
Passo 2
Para (a), temos
estudantes e
categorias (calouro, veterano, júnior). Pelo princípio da casa dos pombos, alguma categoria contém pelo menos
estudantes. Assim há pelo menos nove calouros, veteranos ou juniores.
Passo 3
Para (b), queremos mostrar que vale uma das três afirmações: “há pelo menos 3 calouros”, “há pelo menos 19 veteranos” ou “há pelo menos 5 juniores”. Suponha, para fins de contradição, que todas falhem simultaneamente:
Então o total de estudantes seria
o que contraria o fato de existirem 25 alunos. Logo não é possível que todas as três contagens sejam pequenas, e portanto pelo menos uma delas alcança o valor proposto.
Resposta
(a) Há pelo menos nove calouros, nove veteranos ou nove juniores.
(b) Há pelo menos três calouros, dezenove veteranos ou cinco juniores.
(b) Há pelo menos três calouros, dezenove veteranos ou cinco juniores.