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
pessoas, existem pelo menos
pessoas que nasceram no mesmo dia da semana.
Informações dadas e relevantes:
Informações dadas e relevantes:
- Há
pessoas no grupo. - Os dias da semana fornecem exatamente
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
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
pessoas em
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
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
objetos em
caixas, então alguma caixa tem pelo menos
objetos. Aqui:
-
é o número de objetos (no nosso caso, pessoas), -
é o número de caixas (no nosso caso, dias da semana), -
é a função teto (arredonda 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
objetos. Então o número total de objetos seria, no máximo,
Mas por definição de teto temos
, logo
ou seja, o total seria menor que
, contradição. Portanto alguma caixa tem pelo menos
objetos.
Passo 4
Agora aplico isso ao problema concreto:
pessoas e
dias da semana. Pelo princípio,
Calculo o teto:
Logo existe algum dia da semana que é o dia de nascimento de pelo menos
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
ou mais pessoas nascidas nele. Então cada dia teria no máximo
pessoas, e o total máximo possível seria
pessoas. Mas temos
pessoas no grupo, e
. Contradição. Portanto a suposição era falsa e algum dia tem pelo menos
pessoas.
Passo 6
Resumo prático para a prova (receita rápida): quando dividir
itens em
categorias, calcule
. Esse é o menor número que você pode garantir que aparece em alguma categoria. No problema:
. 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
pessoas nasceram no mesmo dia da semana.