F.6 O Princípio das Casas de Pombo
Esse princípio recebeu esse nome baseado na seguinte ideia: se mais de k pombos entram em casas de pombos, então, pelo menos, uma casa vai ter mais de um pombo. Aprofundando essa ideia, suponha que cada casa contenha, no máximo, um pombo. Então existem, no máximo, k pombos e não os “mais de k” pombos que supostamente entraram nas casas.
Definição do Princípio das Casas de Pombo: Se mais de k itens são colocados em k caixas, então, pelo menos, uma caixa contém mais de um item.
Exemplo F.11: Quantas pessoas precisam estar presentes em uma sala para garantir que duas delas tenham o último nome começando com a mesma letra?
O alfabeto possui 26 letras (caixas). Se a sala tiver 27 pessoas, então existem 27 iniciais (itens) para se colocar em 26 caixas, de modo que, pelo menos, uma caixa conterá mais de uma inicial. Portanto, precisam estar presentes, no mínimo, 27 pessoas.
Exemplo F.12: Quantas vezes é preciso jogar um dado de modo a garantir que um mesmo valor apareça duas vezes?
Um dado apresenta 6 números (caixas). Se ele for jogado 7 vezes, então existem 7 jogadas (itens) para se colocar em 6 caixas, de modo que, pelo menos, uma caixa conterá mais de uma jogada (número repetido). Portanto, é necessário jogar o dado, no mínimo, 7 vezes.