[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[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
>From: "Alexandre Tessarollo" <tessa@mail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>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 é <nicolau@mat.puc-rio.br>
>=========================================================================
_________________________________________________________________
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 é <nicolau@mat.puc-rio.br>
=========================================================================