>
> Date: Fri, 16 Aug 2002 13:28:59 +0000
> From: "Paulo Santa Rita" <[EMAIL PROTECTED]>
> 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 � <[EMAIL PROTECTED]>
=========================================================================
