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 \,25\, caixas de maçãs.
  • Existem \,3\, 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 \,9\, caixas; em outras palavras, provar que pelo menos \,9\, das caixas contêm o mesmo tipo de maçãs.

Passo 2

Idéia geral (intuição): se espalharmos \,25\, caixas em \,3\, categorias (os três tipos), algumas categorias receberão várias caixas. Uma forma direta de quantificar isso é dividir \,25\, por \,3\, 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 n e k, quando distribuímos n objetos em k caixas, a menor garantia que podemos dar para a caixa mais carregada é
\left\lceil \frac{n}{k} \right\rceil,
onde \lceil x\rceil é a função teto (arredonda x para cima ao inteiro mais próximo). Explicando a função teto: se x é inteiro, \lceil x\rceil=x; se não for inteiro, toma-se o próximo inteiro maior. Exemplinho rápido: \lceil 3{,}2\rceil=4, \lceil 5\rceil=5.
Motivação por trás disso (intuição formal): se cada uma das k caixas tivesse no máximo \left\lceil n/k\right\rceil-1 objetos, o total máximo seria
k\left(\left\lceil \frac{n}{k}\right\rceil - 1\right) < k\cdot\frac{n}{k} = n,
ou seja, não bastaria para colocar todos os n objetos; portanto alguma caixa tem que ter pelo menos \left\lceil n/k\right\rceil objetos.

Passo 3

Aplicando a ideia ao nosso problema: aqui n=\!25 e k=\!3. Calculamos
\frac{25}{3}=8{,}333\ldots
Tomando o teto,
\left\lceil \frac{25}{3}\right\rceil = 9.
Interpretação: ao distribuir \,25\, caixas entre \,3\, tipos, alguma categoria (algum tipo de maçã) terá pelo menos \,9\, 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 \,9\, caixas. Ou seja, suponha que cada tipo tenha no máximo \,8\, caixas. Como há \,3\, tipos, o número total de caixas seria no máximo
3\cdot 8 = 24.
Mas sabemos que existem \,25\, caixas no total. Isso é uma contradição, porque não é possível que 25 seja menor ou igual a 24. Logo a hipótese é falsa, e portanto existe pelo menos um tipo que aparece em pelo menos \,9\, caixas.

Passo 5

Resumo didático (como aplicar em prova): duas maneiras equivalentes de justificar rapidamente:
  • Usando teto: calcular \left\lceil \dfrac{25}{3}\right\rceil = 9, logo algum tipo tem pelo menos 9 caixas.
  • Usando contradição: se cada tipo tivesse no máximo 8 caixas, o total seria \le 24, impossível, logo existe tipo com \ge 9 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 \,10\, caixas e \,3\, tipos, \left\lceil \dfrac{10}{3}\right\rceil = 4. Então pelo menos 4 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 9 caixas contêm o mesmo tipo de maçãs.

Exercícios relacionados