Mostre que dados dez pontos em um retângulo
, há um subconjunto de quatro pontos tal que quaisquer dois pontos nele distam no máximo
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
pontos num retângulo de dimensões
existe um subconjunto de
pontos cuja distância máxima entre quaisquer dois é
. Depois, mostrar que em qualquer conjunto de
pontos num hexágono regular de lado
existe um subconjunto de
pontos cuja distância máxima entre quaisquer dois é
. Vamos resolver cada parte particionando a região em “caixas” de diâmetro adequado e aplicar Dirichlet.
Passo 2
Para o retângulo
, subdividimos em três quadrados contíguos de lado
. Cada quadrado tem diâmetro (maior distância entre dois pontos dentro dele) igual a
Logo, quaisquer dois pontos num mesmo quadrado distam no máximo
.
Passo 3
Agora aplicamos o princípio da casa dos pombos: são
pontos (pombos) e
quadrados (caixas). Se nenhum quadrado contivesse
ou mais pontos, cada quadrado teria no máximo
pontos, dando no total
pontos — absurdo, pois há
. Portanto existe pelo menos um quadrado com
pontos.
Passo 4
Nesse quadrado com
pontos, a distância entre quaisquer dois é
. Isso prova a primeira parte.
Passo 5
Para o hexágono regular de lado
, note que ele se decompõe em
triângulos equiláteros congruentes de lado
(basta unir o centro aos
vértices). Cada triângulo equilátero de lado
tem diâmetro igual a
, pois a maior distância entre dois pontos nele é um lado.
Passo 6
Temos
pontos (pombos) e
triângulos (caixas). Se nenhum triângulo tivesse
ou mais pontos, cada um teria no máximo
, perfazendo
pontos — mas há
. Logo há pelo menos um triângulo com
pontos.
Passo 7
Dentro desse triângulo com
pontos, quaisquer dois distam no máximo
. Isso prova a segunda parte.
Resposta
Em qualquer arranjo de
pontos no retângulo
existe um subconjunto de
pontos com distâncias
.
Em qualquer arranjo de pontos no hexágono regular de lado
existe um subconjunto de
pontos com distâncias
.
Em qualquer arranjo de