[obm-l] Diagonais de um Polígono Convexo

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

Caro Paulo:

Segui a sua sugestão para o problema a seguir e cheguei numa resposta
"bonitinha".
A saber: n*(n-3)*(n-4)*(n-5)/12.
Espero que seja a correta.

************

PROBLEMA : Num poligono convexo de N lados e tal que duas diagonais
quaisquer nao sao paralelas. Quantos pontos no exterior do poligono sao
pontos de interseccao de diagonais ?

OBS : Considere que nenhum ponto ( interior ou exterior ao poligono ) e
ponto de interseccao de mais de duas diagonais.

SUGESTAO : Antes de fazer uma sugestao, gostaria de registrar que o nosso
colega Alexandre Tessarolo resolveu esta questao aqui nesta lista. A solucao
dele nao e essa que vou sugerir.

De um vertice partem N-3 diagonais. Se N e par havera uma unica diagonai
N-3 diagonais se encontram. Afora este caso, duas diagonais quaisquer se
encontraram ou fora ou dentro do poligono.

IMAGINE as diagonais que partem de um vertice. Considerando qualquer uma
delas em particular, observe que ela cinde o poligono em dois outros
"sub-poligonos" que tem um lado em comum ( que e a diagonal sob analise ).
Qualquer par de diagonais, uma de cada um dos "sub-poligonos" representam um
ponto de interseccao no exterior, a excecao daqueles pares que tem um
vertice comum.

Finalmente, para que nao surjam dificuldades devido a paridade de N, use
[N], a funcao maximo inteiro : o maior inteiro que nao supera N. Lembre-se
tambem que em somatorios complicados, o uso de numeros binomiais costuma
facilitara as coisas.

***********

SOLUÇÃO:

1. Eu classifiquei as diagonais de um polígono de acordo com a sua "ordem":
Uma diagonal de um polígono de n lados tem ordem = k ( 1 <= k <= [n/2] - 1 )
se e somente se:
a) esta diagonal dividir o polígono em 2 sub-polígonos, sendo um com k+2
vértices e o outro com n-k vértices;
    e
b) k+2 <= n-k   <==>   k <= [n/2] - 1.

Para 1 <= k <= [n/2] - 2, um polígono de n lados tem n diagonais de ordem k.

Se n for par, este polígono terá n/2 diagonais de ordem [n/2] - 1 = (n-2)/2
Se n for ímpar, o polígono terá n diagonais de ordem [n/2] - 1 = (n-3)/2

2. Considere uma dada diagonal (AB, digamos) de ordem k.
No sub-polígono de k+2 lados determinado por AB, existem (k-1)(k-2)/2
diagonais que não passam nem por A nem por B.
No outro sub-polígono, existem (n-k-3)(n-k-4)/2 diagonais que não passam nem
por A nem por B.

Todas estas diagonais interceptam AB em algum ponto exterior ao polígono
original. Além disso, estas são as únicas diagonais do polígono com essa
propriedade. Todas as outras encontram AB em A, B ou em algum ponto
interior.

Assim, o número total de diagonais que encontram AB fora do polígono é k^2 -
(n-2)*k + (n^2-7*n+14)/2.

3. Agora é só somar o número de pontos de interseção externos para cada
diagonal, levando em conta a ordem. No final, deve-se dividir por dois, pois
a soma computa o ponto onde AB intercepta CD e, depois, o ponto onde CD
intercepta AB que, naturalmente, é o mesmo ponto.

Depois de muita álgebra braçal eu cheguei a:
n*(n-3)*(n-4)*(n-5)/12

***********

Um abraço,
Claudio.



=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================