[obm-l] Re: mais que CRUEL

["Alexandre Tessarollo" <tessa@xxxxxxxx>]

> 
> Date: Fri, 16 Aug 2002 13:28:59 +0000
> From: "Paulo Santa Rita" <p_ssr@hotmail.com>
> Subject: [obm-l] mais que CRUEL
> 
> Ola Alexandre e demais
> colegas desta lista ... OBM-L
> 
> Talvez nao seja exagero dizer que o problema a que se refere a mensagem do 
> Alexandre, abaixo, é mais que que CRUEL ...
> 
> Um dos discipulos de EULER propos ao seu mestre o seguinte problema :
> 
> Num poligono convexo de N lados, no qual duas diagonais quaisquer não sao 
> paralelas, quantos pontos no exterior do poligono sao pontos de interseccoes 
> de diagonais se, nesta regiao exterior e tambem no interior do poligono, 
> nenhum ponto e intersecao de mais de duas diagonais ?
> 
> EULER nao resolveu a questao, nao obstante ter lutado durante cerca de tres 
> meses com ela. O discipulo resolveu, alguns meses apos, mas morreu muito 
> jovem e nao se tornou o Grande Matematico que todos esperavam.
> 
> Eu nao li esta historia. A pessoa que me propos a questao contou. Independe 
> de tudo isso, a existencia da historia e o fato do problema ser antigo sao 
> indicativos de sua complexidade.
> 
> A ideia que tive e muito parecida com a do Tessarolo, na mensagem abaixo.
> 
> Existem D=(N(N-3))/2 diagonais. Duas diagonais quaisquer representam um 
> ponto, que e a interseccao entre elas. Claramente que em um vertice mais que 
> uma combinacao esta representando o mesmo ponto ...
> 
> As intersecoes podem ser :
> 
> 1) Um vertice ( total S1)
> 2) Num ponto no interior do poligono (total S2)
> 3) Num ponto no exterior do poligono (total S2)
> 
> Claramente que :
> 
> S1+S2+S3 = total de interseccoes !
> 
> Num vertice concorrem N-3 diagonais, isto fornece BINOM(N-3,2). Ha, porem, N 
> vertices. Segue que :
> 
> S2 + S3 = BINOM(D,2) - N*BINOM(N-3,2)
> 
> O numero  BINOM(D,2) - N*BINOM(N-3,2) e a soma dos pontos de interseccoes no 
> interior e no exterior do poligono.
> 
> Aqui, agora, entra a ideia do Tessarolo :
> 
> Uma diagonal e uma cisao nos vertices. Se { V1, V2, ..., Vn} sao os vertices 
> do poligono, a diagonal {V1,V5} cinde os vertices em dois subconjuntos : 
> {V2,V3,V4} e {V6,V7,...,Vn}. Escolhendo um ponto qualquer no primeiro 
> conjunto e um ponto qualquer no segundo, teremos uma interseccao com a 
> diagonal {V1,V3}. O total de escolhas possiveis e uma mera aplicacao do 
> principio multiplicativo da analise combinatoria e entao passa-se ao 
> somatorio.
> 
> Se o poligono tem N lados, basta se computar as diagonais que tem ate [N/2] 
> lados do poligono, onde [N/2] e o maior inteiro que nao supera [N/2].
> 
> Exemplo: Poligono convexo de 9 lados
> 
> Vertices : {V1,V2,...,V9}
> 
> Diagonais : {V1,V3},{V2,V4},{V3,V5}, ..., {V9,V2}
> Estas diagonais tem, ao seu lado, 2 lados do poligono
> 
> Diagonais : {V1,V4},{V2,V5},{V3,V6},...,{V9,V3}
> Estas diagonsi tem, ao seu lado, 3 lados do poligono
> 
> Diagonais : {V1,V5},{V2,V6},{V3,V7},...,{V9,V4}
> Estas diagonais tem, ao seu lado, 4 lados do poligono
> 
> como 4=[9/2]. Paramos aqui !
> 
> A diagonal {V1,V6} ja foi computada.
> 
> O calculo das somas acima e facil. O somatorio fornecera S2. Dai, usando
> S2 + S3 = BINOM(D,2) - N*BINOM(N-3,2), calculamos S3. E o tio Euler descansa 
> em paz !
> 
> Todavia, tudo isso e burocracia e malabarismo. A ideia brilhante e genial 
> cabe ao Tessarolo, com sua visao de cindir os vertices em dois conjuntos. E 
> sem saber ele resolveu um problema que venceu o Tio Euler...
> 
> Claramente que fizemos as restricoes necessarias. Uma abordagem da 
> existencia de diagonais paralelas talvez fique melhor no ambiente da 
> Geometri Analitica, mais que no da sintetica.
> 
> Seja da um poligono convexo de N lados, com vertices 
> (X1,Y1),(X2,Y2),...(Xn,Yn). Que condicao(oes) devem satisfazer estes pontos 
> para que existam ao menos duas diagonais paralelas ? É possivel caracterizar 
> todos os feixes de paralelas que podem existir ?
> 
> Um abraco a todos
> Paulo Santa Rita
> 6,1028,160802


   Muito obrigado pelos elogios. Realmente são de levantar a moral de qualquer um :-))

   Mas vamos ao que interessa: Por um certo apreço a pouca sanidade que me resta, ative-me aos polígonos regulares. Acreditei que suas particularidades deveriam nos ajudar um pouco.

   Como disse o Paulo, existem 3 tipos de intersecções. Vou acrescentar um quarto tipo, "entre diagonais paralelas". (Só p/facilitar as contas. Contudo, se vc acrscentar completar o plano euclidiano com a linha no infinito... :-)))
   
1) Um vertice ( total S1)

   Dada uma diagonal qualquer do polígono, ela intersecta outras 2(n-4) diagonais em um dos seus 2 vértices. Tomemos a diagonal V1V5. O total de diagonais que possuem V1 OU V5 com vértice (afora a própria V1V5, claro) é sempre (n-4)+(n-4).

   Logo, S1=2(n-4)

2) Num ponto no interior do poligono (total S2)

   Bem, se o que falei naquele e-mail anterior estiver certo, então S2=somatório

3) Num ponto no exterior do poligono (total S3)

   Hum.... Vamos calcular S4 primeiro.

4) Diagonais paralelas (total S4)

   Tomemos a diagonal V1V4 num octógono regular. Basta uma figura minimamente razoável para vermos que as dagonais V2V3, V5V8 e V6V7 são as únicas paralelas a V1V4. Some os ínidces dos vértices de cada diagonal. Vc obterá 5 ou 13 nesses resultados, certo? Detalhe importante, nós estamos num OCTÓgono (8) e 13=5+8, certo?

   A partir daí eu elaborei uma conjectura para polígonos regulares mas ainda não consegui enunciá-la formalmente. Algo como: 

"Numere, no sentido anti-horário, os vértices de V1 até Vn. Tome um daigonal ViVj qualquer, com j>i (por praticidade). As diagonais paralelas a ViVj serão da forma V[i+k]V[j-k], para (i-j)/2<k<(j-i)/2 EM Z[n] (ou seja, sempre fazendo a congruência módulo n)."

   É, algo assim... Aguardo comentários.

   Ah, antes que eu me esqueça, sabemos que S1+S2+S3+S4=total de intersecções entre dua diagonais distintas quaisquer. Ou seja, 
S1+S2+S3+S4=[n(n-3)/2]*[n(n-3)/2 -1]/2
S1+S2+S3+S4=n(n-3)[n(n-3)-2]/8

Sabendo S1, S2 e S4, é fácil calcular o S3 que eu tinha pulado antes. O único prob é efetivamente calcular o S4...

[]'s

Alexandre Tessarollo
-- 
__________________________________________________________
Sign-up for your own FREE Personalized E-mail at Mail.com
http://www.mail.com/?sr=signup

=========================================================================
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>
=========================================================================