Mostre que dados dez pontos em um retângulo 3 \times 1, há um subconjunto de quatro pontos tal que quaisquer dois pontos nele distam no máximo \sqrt{2} entre si. Mostre que dados treze pontos em um hexágono regular de lado 1 , há um subconjunto de três pontos tal que quaisquer dois pontos nele distam no máximo 1 entre si.

Passo 1

O enunciado pede duas coisas usando a ideia de princípio da casa dos pombos em geometria combinatória. Primeiro, mostrar que em qualquer conjunto de 10 pontos num retângulo de dimensões 3\times1 existe um subconjunto de 4 pontos cuja distância máxima entre quaisquer dois é \le\sqrt{2}. Depois, mostrar que em qualquer conjunto de 13 pontos num hexágono regular de lado 1 existe um subconjunto de 3 pontos cuja distância máxima entre quaisquer dois é \le1. Vamos resolver cada parte particionando a região em “caixas” de diâmetro adequado e aplicar Dirichlet.

Passo 2

Para o retângulo 3\times1, subdividimos em três quadrados contíguos de lado 1. Cada quadrado tem diâmetro (maior distância entre dois pontos dentro dele) igual a \sqrt{1^2+1^2}=\sqrt{2}. Logo, quaisquer dois pontos num mesmo quadrado distam no máximo \sqrt{2}.

Passo 3

Agora aplicamos o princípio da casa dos pombos: são 10 pontos (pombos) e 3 quadrados (caixas). Se nenhum quadrado contivesse 4 ou mais pontos, cada quadrado teria no máximo 3 pontos, dando no total 3\times3=9 pontos — absurdo, pois há 10. Portanto existe pelo menos um quadrado com \ge4 pontos.

Passo 4

Nesse quadrado com 4 pontos, a distância entre quaisquer dois é \le\sqrt{2}. Isso prova a primeira parte.

Passo 5

Para o hexágono regular de lado 1, note que ele se decompõe em 6 triângulos equiláteros congruentes de lado 1 (basta unir o centro aos 6 vértices). Cada triângulo equilátero de lado 1 tem diâmetro igual a 1, pois a maior distância entre dois pontos nele é um lado.

Passo 6

Temos 13 pontos (pombos) e 6 triângulos (caixas). Se nenhum triângulo tivesse 3 ou mais pontos, cada um teria no máximo 2, perfazendo 6\times2=12 pontos — mas há 13. Logo há pelo menos um triângulo com \ge3 pontos.

Passo 7

Dentro desse triângulo com 3 pontos, quaisquer dois distam no máximo 1. Isso prova a segunda parte.

Resposta

Em qualquer arranjo de 10 pontos no retângulo 3\times1 existe um subconjunto de 4 pontos com distâncias \le\sqrt{2}.
Em qualquer arranjo de 13 pontos no hexágono regular de lado 1 existe um subconjunto de 3 pontos com distâncias \le1.

Exercícios relacionados