Mostre que em qualquer grupo de 20 pessoas, pelo menos 3 nasceram no mesmo dia da semana.

Passo 1

O enunciado pede que mostremos que, em qualquer grupo de 20 pessoas, existem pelo menos 3 pessoas que nasceram no mesmo dia da semana.
Informações dadas e relevantes:
  • 20 pessoas no grupo.
  • Os dias da semana fornecem exatamente 7 categorias possíveis para o dia de nascimento (segunda, terça, …, domingo).
  • Devemos concluir que existe um dia da semana que é o dia de nascimento de pelo menos 3 dessas pessoas.

Passo 2

Vou organizar mentalmente as informações: cada pessoa tem um dia da semana associado ao seu aniversário. Isso é o mesmo que repartir as 20 pessoas em 7 caixas (cada caixa corresponde a um dia da semana). Escrever isso ajuda a transformar o problema em algo fácil de contar: quantas pessoas cabem em cada caixa antes de sermos forçados a ter uma caixa com pelo menos 3 pessoas?

Passo 3

Apresento um princípio simples e útil (vou explicá-lo do jeito mais claro): o princípio da casa dos pombos. Ele diz, de forma intuitiva, o seguinte: se você coloca n objetos em k caixas, então alguma caixa tem pelo menos \left\lceil \dfrac{n}{k}\right\rceil objetos. Aqui:
  • n é o número de objetos (no nosso caso, pessoas),
  • k é o número de caixas (no nosso caso, dias da semana),
  • \lceil x\rceil é a função teto (arredonda x para cima ao inteiro mais próximo).
Explicação por que isso é verdade (pequena “prova” por contradição): suponha que nenhuma caixa tivesse mais do que \left\lceil \dfrac{n}{k}\right\rceil - 1 objetos. Então o número total de objetos seria, no máximo,
k\left(\left\lceil \frac{n}{k}\right\rceil - 1\right).
Mas por definição de teto temos \left\lceil \dfrac{n}{k}\right\rceil -1 < \dfrac{n}{k}, logo
k\left(\left\lceil \frac{n}{k}\right\rceil - 1\right) < k\cdot\frac{n}{k} = n,
ou seja, o total seria menor que n, contradição. Portanto alguma caixa tem pelo menos \left\lceil \dfrac{n}{k}\right\rceil objetos.

Passo 4

Agora aplico isso ao problema concreto: n=20 pessoas e k=7 dias da semana. Pelo princípio,
\text{algum dia da semana tem pelo menos }\left\lceil \frac{20}{7}\right\rceil \text{ pessoas.}
Calculo o teto:
\frac{20}{7}\approx 2{,}857\ldots\quad\Rightarrow\quad \left\lceil \frac{20}{7}\right\rceil = 3.
Logo existe algum dia da semana que é o dia de nascimento de pelo menos 3 pessoas.

Passo 5

Dou uma alternativa mais elementar (também muito usada em prova) que chega à mesma conclusão por contradição direta: suponha que nenhum dia da semana tivesse 3 ou mais pessoas nascidas nele. Então cada dia teria no máximo 2 pessoas, e o total máximo possível seria
7\times 2 = 14
pessoas. Mas temos 20 pessoas no grupo, e 20>14. Contradição. Portanto a suposição era falsa e algum dia tem pelo menos 3 pessoas.

Passo 6

Resumo prático para a prova (receita rápida): quando dividir n itens em k categorias, calcule \left\lceil \dfrac{n}{k}\right\rceil. Esse é o menor número que você pode garantir que aparece em alguma categoria. No problema: \left\lceil \dfrac{20}{7}\right\rceil=3. Anote isso, escreva a pequena conta e pronto — argumento curto e completo na prova. Você consegue!

Resposta

Pelo princípio da casa dos pombos, pelo menos \left\lceil \dfrac{20}{7}\right\rceil = 3 pessoas nasceram no mesmo dia da semana.

Exercícios relacionados