[obm-l] Re: [obm-l] Quest�o IME 96

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

----- Original Message -----
From: "Tcheka Republica" <rep_tcheka@hotmail.com>
To: <obm-l@mat.puc-rio.br>
Sent: Tuesday, March 25, 2003 1:55 PM
Subject: [obm-l] Quest�o IME 96


>
> Essa � uma quest�o do IME do ano de 1996.
> Gostaria que alguem ajudasse-me a resolve-la:
>
> Seja um oct�gono convexo. Supondo que quando todas as suas digonais s�o
> tra�adas, n�o h� mais de duas diagonais se interceptando no mesmo ponto.
> Quantos pontos de interse��o (de diagonais) existem neste oct�gono ?
>
>
> Obrigado pela ajuda.
> Wander
>
>
Caro Wander:

O enunciado cont�m um erro, pois cada um dos 8 v�rtices do oct�gono �
extremidade de 5 diagonais - assim, n�o � poss�vel que apenas 2 diagonais se
encontrem em cada ponto.

No entanto, vamos supor que o problema pe�a o n�mero de pontos de interse��o
de diagonais que n�o s�o v�rtices do oct�gono.

Nesse caso, come�amos calculando o n�mero de diagonais de um oct�gono
convexo - igual a 8*(8-3)/2 = 20.

Se cada par de diagonais se encontra num ponto, teremos que o n�mero de
pontos de interse��o ser�:
C(20,2) = 20*19/2 = 190.

No entanto, alguns desses pontos s�o justamente os v�rtices do oct�gono,
onde 5 diagonais se encontram. Assim, em cada v�rtice existir�o C(5,2) =
5*4/2 = 10 pares de diagonais se encontrando.

Assim, devemos subtrair 8*C(5,2) = 80 do n�mero que achamos anteriormente, o
que dar� um total de:
190 - 80 = 110 pontos de interse��o de diagonais que n�o s�o v�rtices.

H� um outro detalhe a se considerar: o problema pede o n�mero de pontos de
interse��es de diagonais NO oct�gono. Isso pode significar duas coisas:
i) o n�mero de pontos NO PLANO do oct�gono, podendo algum ponto ser exterior
ao oct�gono  - nesse caso, vale a solu��o acima;

ou

ii) o n�mero de pontos NO INTERIOR do oct�gono:

Aqui, o racioc�nio � um pouco diferente.
Cada quatro v�rtices do oct�gono determinam um quadril�tero, o qual tem
apenas duas diagonais (as quais s�o tamb�m diagonais do oct�gono) que se
encontram num ponto, o qual � diferente para cada quadril�tero formado por
v�rtices do
oct�gono.

Assim, cada quadril�tero determina um ponto de interse��o e vice-versa.
Al�m disso, cada 4 v�rtices determinam um quadril�tero e vice-versa.
Segue-se que:
n�mero de pontos de interse��o =
n�mero de quadril�teros =
n�mero de maneiras de se escolher 4 v�rtices dentre os 8 existentes =
C(8,4) = 8*7*6*5/(4*3*2*1) = 70 pontos de interse��o de diagonais INTERIORES
ao oct�gono.


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