Pombos e revestimentos

Os três problemas do "pombo" propostos na semana passada , apesar de sua relativa simplicidade, provocaram numerosos e interessantes comentários.

A primeira é a mais simples: se lançarmos um dado 12 vezes, pode acontecer, embora seja improvável (quão improvável?), que cada um dos seis números saia duas vezes, então teríamos que lançá-lo 13 vezes para ter certeza absoluta de que algum número sairá pelo menos três vezes.

A segunda pode ser abordada de diferentes maneiras. Veja como Luis Ortiz fez:

O problema dos 12 dígitos é claramente ilustrado por meio de uma tabela. Organizamos os 100 números possíveis de dois dígitos em fileiras de 11 números consecutivos cada, começando em 00, da seguinte maneira:

00 01 02 03 04 05 06 07 08 09 10

11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32

· · ·

88 89 90 91 92 93 94 95 96 97 98

99

Nesta tabela, a diferença entre quaisquer dois números na mesma coluna é um múltiplo de 11, ou seja, ambos os algarismos são iguais. Se escolhermos quaisquer 12 números na tabela, pelo menos dois deles devem estar na mesma coluna, o que significa que a diferença entre eles terá ambos os algarismos iguais. De fato: no fim das contas, trata-se de um pombal com 11 caixas e 12 pombos.

Eu disse no final do post anterior que o princípio da casa dos pombos nos permite abordar efetivamente alguns problemas combinando-o com a teoria dos grafos, e a solução fornecida por Manuel Amorós para o terceiro dos problemas da semana passada é um bom exemplo disso:

O problema da amizade é claramente visto em um grafo colorido onde os pontos são pessoas e as arestas expressam os relacionamentos: uma aresta azul se elas se conhecem e uma vermelha caso contrário. O objetivo é demonstrar a existência de um grafo monocromático. De qualquer vértice P, emanam 5 arestas, azuis ou vermelhas. Necessariamente, haverá 3 da mesma cor, digamos azul. Os 3 vértices correspondentes estarão, por sua vez, conectados entre si , e pode haver dois casos: ou todas as 3 arestas do referido triângulo são vermelhas (teríamos um triângulo monocromático), ou há uma aresta azul. Essa aresta, juntamente com as 2 que emanam de suas extremidades em direção a P, formam um triângulo azul.

Revestimentos com figuras semelhantes

Sem sair do nosso pombal conceitual (embora a relação possa não ser óbvia), Salva Fuster propôs o seguinte problema de cobertura:

“Dado um triângulo equilátero, quantos triângulos equiláteros menores são necessários, no mínimo, para cobri-lo?”

Esses triângulos menores não precisam ser iguais e podem se sobrepor (caso contrário, a resposta obviamente seria 4).

O problema admite variações e generalizações interessantes: dado um quadrado, quantos quadrados menores são necessários, no mínimo, para cobri-lo? O critério pode ser generalizado para outros polígonos regulares? E para polígonos irregulares? E para o círculo?

E, finalmente, outro problema (sutilmente relacionado ao da FC) em que o triângulo equilátero e o princípio da casa dos pombos convergem:

Dados 5 pontos em um triângulo equilátero com lados de 1 metro, eles podem estar separados por mais de 50 cm?