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?
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
meses possíveis) e quantas para garantir que duas compartilhem dia exato do ano (com
dias possíveis). Em seguida, aplicamos o mesmo princípio a um conjunto de meias:
pretas e
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
pessoas e
meses, só ficamos forçados a colocar dois pombos na mesma gaveta quando
. Portanto, o mínimo é
Passo 3
Para garantir que duas pessoas façam aniversário no mesmo dia exato do ano, agora temos
gavetas (dias). Pelo mesmo raciocínio, precisamos de
pessoas para ter certeza de uma coincidência de dia.
Passo 4
Para ter um par de meias da mesma cor, note que há
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 é
Passo 5
Para ter um par de meias brancas, no pior caso podemos retirar primeiro todas as
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 é
Resposta
Para garantir duas pessoas com aniversário no mesmo mês:
.
Para garantir duas pessoas com aniversário no mesmo dia do ano: .
(a) Para um par da mesma cor: .
(b) Para um par de meias brancas: .
Para garantir duas pessoas com aniversário no mesmo dia do ano:
(a) Para um par da mesma cor:
(b) Para um par de meias brancas: