Combinatoria
Suponha que você decida passar a noite de sexta-feira em um carnaval. No carnaval, um locutor coloca um problema e diz que quem acertar vai receber um pequeno prêmio. Aqui está o problema que o locutor coloca: se você tem 8 luvas vermelhas e 8 luvas verdes em um cesto de roupa suja para um total de 16 luvas, qual é o número mínimo de luvas que você deve tirar do cesto de roupa para garantir um par correspondente?
Você começa a pensar sobre isso, e sabe que deve ser mais de uma luva, pois você precisa de um par correspondente. Se você puxou duas luvas, você pode ter sorte e conseguir um par, mas também pode conseguir uma luva vermelha e uma luva verde, o que significa que você não tem um par garantido.
Se você tirar três luvas do cesto de roupa suja, cada uma das luvas pode ser vermelha ou verde. Se as duas primeiras luvas que você puxar forem iguais, você terá a mesma. Do contrário, você tem uma luva vermelha e uma verde e, como a terceira deve ser vermelha ou verde, você deve ter um par. Portanto, se você tirar três luvas do cesto de roupa suja, terá um par garantido. Você compartilha sua resposta com o locutor: o número mínimo de luvas que devem ser retiradas do cesto de roupa suja que garantiria um par correspondente é três, e receba seu prêmio!
Este problema da luva é um problema matemático na área de combinatória. Combinatória é um ramo da matemática que tem a ver com técnicas de contagem. Não deixe o grande nome assustar você. Como afirma a definição, é apenas um nome sofisticado para o estudo da contagem.
O Princípio Pigeonhole
A lógica por trás do problema da luva, na verdade, tem a ver com um conceito extremamente simples, mas poderoso, em combinatória. Este conceito é denominado princípio da classificação . Basicamente, esse princípio afirma que se estamos colocando pombos em escaninhos, e temos mais pombos do que escaninhos, deve ser o caso de pelo menos um dos buracos ter mais de um pombo nele. Parece bom senso, certo? É, mas você ficaria surpreso com a utilidade desse princípio no estudo de combinatória.
Pense no nosso exemplo de luva novamente. Considere nossas luvas como pombos e as cores das luvas como escaninhos. Se tirarmos três luvas do cesto de roupa suja, e essas luvas podem ser de duas cores, vermelha ou verde, teremos três pombos e dois escaninhos. Pelo princípio do escaninho, pelo menos dois dos pombos devem ir no mesmo escaninho, então pelo menos duas das luvas devem ser da mesma cor quando você puxar três. Muito legal, não é? É um conceito tão simples, mas pode ser aplicado a muitos problemas diferentes.
Mais exemplos
Vejamos mais alguns exemplos em que o princípio do escaninho pode ser aplicado. Para começar, considere o último livro que você leu. Aqui está um fato interessante: para qualquer parágrafo com 27 ou mais palavras, deve ser o caso de pelo menos duas dessas palavras começarem com a mesma letra. Aqui está um fato ainda mais interessante: é verdade por causa do princípio da classificação.
Vamos pensar sobre isso. Existem 26 letras no alfabeto. Vamos pensar nessas 26 letras como escaninhos e nas palavras do parágrafo como pombos. Como o parágrafo tem 27 ou mais palavras, há mais palavras do que letras no alfabeto, portanto, temos mais pombos do que escaninhos. Assim, pelo princípio dos escaninhos, deve acontecer que haja pelo menos dois pombos em um desses escaninhos. Portanto, pelo menos duas das palavras do parágrafo devem começar com a mesma letra.
Agora, aqui está outra coisa que é bastante legal. Se você for a uma reunião com mais de 366 pessoas, deve ser o caso de que pelo menos duas pessoas presentes compartilhem o mesmo aniversário! Novamente, isso é algo que pode ser explicado usando o princípio da classificação.
Há 365 dias em um ano, mas em um ano bissexto, há 366 dias. Portanto, existem 366 aniversários possíveis. Se pensarmos nesses aniversários como escaninhos e nas pessoas presentes à reunião como pombos, teremos mais pombos do que escaninhos. Pelo princípio do escaninho, deve haver mais de um pombo em pelo menos um dos escaninhos. Portanto, deve haver pelo menos duas pessoas com o mesmo aniversário. Ah-ha! O princípio do escaninho prevalece novamente!
Resumo da lição
A Combinatória é um ramo da matemática que estuda as técnicas de contagem. O princípio do escaninho é um conceito simples e amplamente utilizado em combinatória. Este princípio afirma que se estamos colocando pombos em escaninhos e temos mais pombos do que escaninhos, deve ser o caso de pelo menos um dos escaninhos conter mais de um pombo. Vimos que essa é uma ideia extremamente simples, mas também vimos como ela pode ser facilmente aplicada a diferentes circunstâncias e problemas em matemática, combinatória e aplicações no mundo real.