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:
O conteúdo que vamos usar é principalmente uma combinação de dois ingredientes:
- 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).
- 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
e o seu conjunto de pontos internos de
Os outros pontos (os que não cabem em
) chamamos de
e aí
.
Passo 3
Agora vem a observação-chave:
Se 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 só 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.”
Se
Mas, por Helly para discos, isso aconteceria só se para cada centro possível de disco de raio 1 que contém
“para algum
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
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
-
, -
.
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, comoestã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.