Ensino Superior ⇒ Exercicios de Elementos da Teoria dos Números Tópico resolvido

[ana2011]

Considere 25 pontos em um plano de forma que para cada 3 pontos quaisquer, dentre os 25, pelo menos um par deles possui distância menor que 1 cm. Mostre que existe um círculo de raio 1 cm que contém pelo menos 13 dos 25 pontos.

[cajuADMIN]

Olá ana2011,

Acredito que o enunciado se refira a um círculo com diâmetro de 1cm, e não raio de 1cm.

Vamos começar com o caso trivial, ou seja, os 25 pontos ([tex3]p_1[/tex3] até [tex3]p_{25}[/tex3] dentro do círculo de diâmetro 1cm (que iremos chamar de [tex3]C_1[/tex3]):

25pts_circle.png (4.29 KiB) Exibido 978 vezes

Sendo o círculo de diâmetro 1cm, todos os pontos dentro dele possuem uma distância até qualquer outro menor do que 1cm.

Agora vamos ver todas situações possíveis e tentar chegar a uma demonstração.

Vamos retirar um ponto ([tex3]p_1[/tex3]) de dentro deste círculo e colocá-lo longe (distância maior do que 1cm) do círculo [tex3]C_1[/tex3]:

25pts_circle2.png (7.25 KiB) Exibido 978 vezes

Esta nova situação continua satisfazendo o enunciado, pois o ponto fora do círculo só poderá formar triplas com outros dois que estejam dentro do círculo (portanto, terão uma distância entre eles menor do que 1cm).

Agora que começa o problema. Ao retirar mais um ponto ([tex3]p_2[/tex3]) de dentro de [tex3]C_1[/tex3] seremos obrigados a colocar perto (distância menor do que 1cm) do ponto [tex3]p_1[/tex3]. Caso contrário, poderíamos formar uma tripla onde nenhuma dupla possuiria distância menor do que 1cm (como o enunciado manda). Ou seja, só poderemos colocar [tex3]p_2[/tex3] a uma distância menor do que 1cm de [tex3]p_1[/tex3].
Para facilitar, vamos envolver [tex3]p_1[/tex3] com um círculo de diâmetro 1cm, o que faz com que [tex3]p_2[/tex3] tenha de ser ser colocado dentro deste círculo:

25pts_circle3.png (9.42 KiB) Exibido 978 vezes

Agora, para continuar satisfazendo o enunciado, o único jeito de retirar pontos de dentro de [tex3]C_1[/tex3] é colocando dentro de [tex3]C_2[/tex3], pois assim nunca teremos uma tripla onde nenhum grupo de dois desta tripla possua distância menor do que 1cm entre eles (conforme enunciado).

Vamos retirando um por um de [tex3]C_1[/tex3] e colocando em [tex3]C_2[/tex3]. O pior caso vai ocorrer quando tivermos 12 pontos dentro de [tex3]C_1[/tex3] e, consequentemente, 13 pontos em [tex3]C_2[/tex3].
Em todos os outros casos ou [tex3]C_1[/tex3] ou [tex3]C_2[/tex3] terá mais do que 13 pontos. Como queríamos demonstrar.

Grande abraço,
Prof. Caju