∆∊∫afi∅s

[Lucas de Alkmim]

Desafio 4: 50 pontos são marcados em uma folha de papel. É sempre possível construir uma reta que separa os pontos em dois grupos de 25 pontos cada?

[Sobolev]

Sim, é sempre possível. Apesar de existirem algoritmos determinísticos para resolver este problema ( com complexidade O(n) ou O(n log n) ), uma forma simples de encontrar a recta que divide o conjunto de pontos é a seguinte:

1. Escolher uma recta ao acaso (podem ser usados alguns critérios baseados nas médias ou medianas das coordenadas dos pontos mas não é muito relevante)

2. Projectar todos os pontos sobre essa recta.

3. Ordenar as projeções e escolher um ponto Q da recta que divida em duas partes iguais os pontos projectados. (isto pode nem sempre ser possível devido à possibilidade de diversos pontos terem a mesma projecção).

4. A recta perpendicular à recta inicial que passa no ponto Q tem igual número de pontos de cada lado.

Naturalmente, se o passo 3 não for possível deve ser escolhida outra recta.

[Rui Carpentier]

Uma outra maneira de chegar à solução é a seguinte:

1) Escolha-se um ponto P que não seja colinear com qualquer par dos 50 pontos dados;

2) Toma-se uma reta que passe pelo ponto P e não passe por nenhum dos 50 pontos;

3) Escolhe-se uma orientação para a reta, e seja E(0) o nº de pontos à esquerda da reta (na orientação escolhida) e D(0) o nº de pontos à esquerda da reta;

4) Vai-se rodando a reta continuamente e para cada ângulo \(\alpha\) seja \(E(\alpha)\) o nº de pontos à esquerda da reta e \(D(\alpha)\) o nº de pontos à esquerda da reta;

Temos então que, para \(\alpha=180^o\), \(E(\alpha)=D(0)\) e \(D(\alpha)=E(0)\). E como \(E(\alpha)\) e \(D(\alpha)\) variam em + ou - 1 à medida que variamos \(\alpha\) (é aqui que é importante o facto de P não ser colinear com 2 ou mais pontos) temos que haverá um ângulo \(\alpha\) entre 0 e 180º tal que \(E(\alpha)=D(\alpha)=25\).

[Lucas de Alkmim]

obrigado, caras.