Dado um conjunto de 25 pontos no plano tais que entre quaisquer 3 deles existe um par com distância menor que 1. Provar que existe um círculo de raio 1 que contém pelo menos 13 dos 25 pontos dados.

Passo 1

Então, a questão é a seguinte: você tem 25 pontos no plano e sabe que em qualquer conjunto de 3 pontos sempre aparece um par cuja distância é menor que 1. O que queremos provar é que existe um círculo de raio 1 que consiga agrupar pelo menos 13 desses 25 pontos.
O conteúdo que vamos usar é principalmente uma combinação de dois ingredientes:
  1. Um argumento de “disco de cobertura máximo” (a gente pega um disco de raio 1 que já contém o máximo possível de pontos e mostra que, se contivesse menos que 13, daria ruim).
  2. Um pouquinho de Helly (a versão para discos: se famílias de discos têm interseções de três em três, então todas juntas também têm).
    Além disso, vamos usar o princípio da casa‐dos‐pombos (pigeonhole) para garantir que algum ponto interior “bloqueie” vários pontos de fora.

Passo 2

Suponha, para chegar a uma contradição, que nenhum círculo de raio 1 consiga pegar 13 ou mais pontos. Então o melhor círculo de raio 1 que você conseguir colocar pega no máximo 12 pontos. Chamemos este círculo de X = ,x1,x2,dots,xm com m<=12 e o seu conjunto de pontos internos de
Y=,y1,y2,dots,y25-m,
Os outros pontos (os que não cabem em ) chamamos de
e aí .

Passo 3

Agora vem a observação-chave:
Se dl(y,x(y)r)>2 não coubesse em , isso significa que não existe um disco de raio 1 contendo simultaneamente todos os pontos de e também o .
Mas, por Helly para discos, isso aconteceria se para cada centro possível de disco de raio 1 que contém , esse mesmo centro não conseguisse conter . E a falha mais óbvia é:
para algum a distância é maior que 2.”
Para ver por quê, note:
  • Qualquer disco unitário que contenha todo está dentro da interseção .
  • Se ficasse a no máximo 2 de cada , então cada par de discos e se sobrepõe, e por Helly a família teria interseção comum não‐vazia, ou seja, haveria um disco de raio 1 contendo todo , contradizendo o maximalidade de .
  • Logo, para cada existe pelo menos um “bloqueador” com

Passo 4

Agora aplicamos a casa‐dos‐pombos: temos d(y1,x)>2 e d(y2,x)>2 pontos em e só em . Se cada aponta para um “bloqueador” , então há uma para a qual pelo menos dois apontam. Ou seja,

Passo 5

Considere o triplo . Temos
  1. ,
  2. .
    Falta só verificar que . Mas note que, se por acaso , então já haveria um par a menos que 1 no triplo e não teríamos contradição.
    Porém, como estão ambos fora do disco de raio 1 centrado em , eles satisfazem . Isso implica que cada um deles está muito longe de e, em particular, obrigatoriamente .
    Para ver de modo direto: se dois pontos estão a mais de 2 unidades de , então o triângulo tem dois lados maiores que 2, e o terceiro lado não pode cair abaixo de 1 (caso contrário daria um “triângulo super‐estuprado” na geometria euclidiana).
De qualquer forma, concluímos que nesse triplo nenhuma das três distâncias ficou abaixo de 1, o que quebra a hipótese inicial de que “em todo conjunto de 3 pontos sempre aparece um par com distância <1.”

Resposta

Portanto nossa suposição de que nenhum círculo de raio 1 poderia conter 13 pontos está errada. Logo existe, sim, um círculo de raio 1 contendo pelo menos 13 dos 25 pontos.

Exercícios relacionados