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
>From: "Alexandre Tessarollo" <[EMAIL PROTECTED]>
>Reply-To: [EMAIL PROTECTED]
>To: [EMAIL PROTECTED]
>Subject: [obm-l] Re: CRUEL
>Date: Fri, 16 Aug 2002 02:56:26 -0300
>
>
>
> Estive fazendo umas contas e creio que posso ter chegado a uma resposta
>parcial. Por uma quest�o de praticidade, numerei os v�rtices de A[0] at�
>A[n-1], no sentido anti-hor�rio.
>
> Tome o v�rtice A[0] e v� ligando com os outros v�rtices (A[1]; A[2];
>...; A[n-1]). Note que cada diagonal A[0]A[i] divide o plano em dois
>semi-planos. Se o pol�gono � convexo, podemos determinar exatamente quantos
>v�rtices ficam em cada semi-plano.
>
> Para quem est� com a figura, � f�cil ver que, dada a diagonal A[0]A[i],
>todos os pontos A[j] com 0<j<i est�o em um semi-plano e todos os pontos com
>i<j<n est�o em outro semi-plano. Qualquer diagonal com v�rtices em
>semi-planos distintos ter� uma intersec��o com a diagonal A[0]A[i].
>
> Logo, cada diagonal possui SUM[i=1, n-1]{(i-1)(n-1-i)/2}
>Leia-se "somat�rio de (i-1)(n-1-i)/2 quando i varia de 1 at� n-1"
>
> Como s�o n diagonais, bastaria calcular n*SUM. Contudo, cada
>intersec��o est� sendo contada duas vezes (uma para cada diagonal que a
>"produz"). Assim, o resultado seria n*Sum/2.
>
> Devo confessar que n�o terminei as contas do somat�rio pq estou meio
>cansado, mas creio que esse seja o n�mero de intersec��es pedido. Aguardo
>coment�rios...
>
>PROBLEMA:
>
>(Admitindo que o valor encontrado antes esteja correto :-))
>
> O n�mero encontrado antes N�O necessariamente � o n�mero de
>intersec��es DISTINTAS. Pode-se afirmar com certeza que o n�mero de
>distintas � menor ou igual ao valor calculado.
>
> O problema agora �: Como descobrir quais intersec��es s�o m�ltiplas,
>isto �, formadas por mais de 2 diagonais? E como cont�-las?
>
>
>[]'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]>
>=========================================================================
_________________________________________________________________
Tenha voc� tamb�m um MSN Hotmail, o maior webmail do mundo:
http://www.hotmail.com/br
=========================================================================
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]>
=========================================================================
