Vinte e cinco caixas de maçãs foram entregues em uma loja. As maçãs são de três tipos diferentes, mas todas as maçãs em cada caixa são do mesmo tipo. Mostre que pelo menos nove das caixas contêm o mesmo tipo dè maçãs.
Passo 1
O enunciado dá as seguintes informações:
- Foram entregues
caixas de maçãs. - Existem
tipos diferentes de maçãs. - Todas as maçãs dentro de cada caixa são do mesmo tipo (cada caixa é “uniforme” quanto ao tipo).
O que o enunciado pede: - Mostrar que existe pelo menos um tipo de maçã que aparece em pelo menos
caixas; em outras palavras, provar que pelo menos das caixas contêm o mesmo tipo de maçãs.
Passo 2
Idéia geral (intuição): se espalharmos
caixas em
categorias (os três tipos), algumas categorias receberão várias caixas. Uma forma direta de quantificar isso é dividir
por
e ver quantas caixas cabem, em média, em cada tipo. Vou explicar o conceito usado com calma.
Definição e ferramenta que vamos usar: para inteiros positivos
e
, quando distribuímos
objetos em
caixas, a menor garantia que podemos dar para a caixa mais carregada é
onde
é a função teto (arredonda
para cima ao inteiro mais próximo). Explicando a função teto: se
é inteiro,
; se não for inteiro, toma-se o próximo inteiro maior. Exemplinho rápido:
,
.
Motivação por trás disso (intuição formal): se cada uma das
caixas tivesse no máximo
objetos, o total máximo seria
ou seja, não bastaria para colocar todos os
objetos; portanto alguma caixa tem que ter pelo menos
objetos.
Passo 3
Aplicando a ideia ao nosso problema: aqui
e
. Calculamos
Tomando o teto,
Interpretação: ao distribuir
caixas entre
tipos, alguma categoria (algum tipo de maçã) terá pelo menos
caixas.
Vou mostrar essa conclusão também de outra maneira, equivalente e talvez ainda mais direta.
Passo 4
Prova por contradição (forma elementar): suponha, para contradizer, que nenhum tipo aparece em pelo menos
caixas. Ou seja, suponha que cada tipo tenha no máximo
caixas. Como há
tipos, o número total de caixas seria no máximo
Mas sabemos que existem
caixas no total. Isso é uma contradição, porque não é possível que
seja menor ou igual a
. Logo a hipótese é falsa, e portanto existe pelo menos um tipo que aparece em pelo menos
caixas.
Passo 5
Resumo didático (como aplicar em prova): duas maneiras equivalentes de justificar rapidamente:
- Usando teto: calcular
, logo algum tipo tem pelo menos caixas. - Usando contradição: se cada tipo tivesse no máximo
caixas, o total seria , impossível, logo existe tipo com caixas.
Dica prática: essa é a aplicação direta do princípio que muitas provas chamam de “princípio da gaveta” (pigeonhole). Na prova, escrever uma das duas justificativas acima é suficiente e rápido.
Passo 6
Exemplo extra para fixar: se fossem
caixas e
tipos,
. Então pelo menos
caixas conteriam o mesmo tipo. Isso ajuda a ficar confortável com a ideia para outros números.
Força aí — no edital da prova, quando vir uma questão do tipo “mostre que pelo menos …”, pensar imediatamente em dividir e usar o teto ou fazer a conta por contradição costuma resolver no tempo.
Resposta
Pelo menos
caixas contêm o mesmo tipo de maçãs.