Qual o número mínimo de pessoas para o qual temos certeza de que há sempre duas que fazem aniversário no mesmo mês? E se for no mesmo dia do ano?
11. Numa gaveta há seis meias pretas e seis meias brancas. Qual o número mínimo de meias que devemos retirar (no escuro) para ter certeza que:
(a) As meias retiradas contenham um par da mesma cor?
(b) As meias retiradas contenham um par da cor branca?

Passo 1

O exercício envolve duas aplicações do princípio da casa dos pombos (pigeonhole principle). Primeiro, queremos saber quantas pessoas são necessárias para garantir que duas compartilhem mês de aniversário (com 12 meses possíveis) e quantas para garantir que duas compartilhem dia exato do ano (com 365 dias possíveis). Em seguida, aplicamos o mesmo princípio a um conjunto de meias: 6 pretas e 6 brancas, para saber quantas devemos retirar no escuro para obter certos pares.

Passo 2

Para garantir que duas pessoas façam aniversário no mesmo mês, imagine que cada mês seja uma “gaveta” e cada pessoa um “pombo”. Se tivermos n pessoas e 12 meses, só ficamos forçados a colocar dois pombos na mesma gaveta quando n>12. Portanto, o mínimo é
n=12+1=13.

Passo 3

Para garantir que duas pessoas façam aniversário no mesmo dia exato do ano, agora temos 365 gavetas (dias). Pelo mesmo raciocínio, precisamos de
n=365+1=366
pessoas para ter certeza de uma coincidência de dia.

Passo 4

Para ter um par de meias da mesma cor, note que há 2 cores (pretas e brancas). No pior caso, as duas primeiras meias retiradas são de cores diferentes. A terceira meia, obrigatoriamente, vai coincidir com uma das duas já tiradas, formando um par. Logo, o mínimo é 3.

Passo 5

Para ter um par de meias brancas, no pior caso podemos retirar primeiro todas as 6 meias pretas. Só a partir da sétima retirada começamos a pegar brancas, mas para formar um par branco precisamos de duas delas. Assim, o mínimo é
6+2=8.

Resposta

Para garantir duas pessoas com aniversário no mesmo mês: \,13.
Para garantir duas pessoas com aniversário no mesmo dia do ano: \,366.
(a) Para um par da mesma cor: \,3.
(b) Para um par de meias brancas: \,8.

Exercícios relacionados