Re: Traducao dos Problemas Russos

["Alexandre F. Terezan" <aleterezan@xxxxxxxxxxxxx>]

Ol� Paulo e demais integrantes da lista.
Eu nao sei se algu�m j� respondeu ao problema antes, mas l� vai uma
tentativa.

Gostaria que comentassem, minha solucao � tao elementar que acho q est�
errada, hehehe

Imaginemos separadamente cada um dos 5 "pol�gonos" delimitados.

2 deles sao verdadeiros retangulos, cada um com 4 "arestas". Mas h� 3 deles
que eu vou encarar como "pent�gonos" pois possuem 5 "arestas".

Os "pent�gonos" sao:

- O pol�gono superior esquerdo
- O pol�gono superior direito
- O pol�gono inferior central

Imaginemos um destes "pent�gonos". Chamemos de PS o ponto em que comecamos a
desenhar a suposta curva e PF o ponto em que "terminamos" de desenh�-la.
Cada vez que a curva cortar uma aresta do "pent�gono" contaremos como 1
CORTE.

Vamos imaginar um contra-exemplo para o enunciado, ou seja, ao menos uma
curva que n�o passa por qualquer dos v�rtices e que cruza todas as arestas
APENAS uma vez.

Caso nao haja tal contra-exemplo estar� demonstrado que:

"Qualquer curva que n�o passa por qualquer dos v�rtices mas que cruza todas
as arestas devera cruzar ao menos uma das arestas mais de uma vez".


H� 2 hip�teses:

 a) PS � interior ao "pent�gono"  --> neste caso, ap�s 5 CORTES em arestas
distintas (1 CORTE por aresta), PF tem de ser EXTERIOR ao pent�gono;

 b) PS � exterior ao "pent�gono" --> neste caso, ap�s 5 CORTES em arestas
distintas (1 CORTE por aresta),  PF tem de ser INTERIOR ao pent�gono;

Ora, o mesmo racioc�no pode ser aplicado aos 2 outros pent�gonos.

Agora, verifique que h� 2 casos que devemos considerar:

 I) PS � interior ao pent�gono superior direito:

 Neste caso, � evidente que PS tem de ser exterior aos 2 outros pent�gonos.
PS ser exterior ao pent�gono superior esquerdo (hip�tese b) faz com que PF
seja interior a ele. Mas PS ser exterior ao pent�gono inferior central
(hip�tese b) faz com que PF seja tamb�m interior a ele. Como PF nao pode ser
interior a 2 pent�gonos distintos simultaneamente, chegamos a um ABSURDO.

 II) PS � exterior ao pent�gono superior direito:

 Neste caso, pela hip�tese b, PF deve ser interior a este pent�gono. Assim,
� evidente que PF tem de ser exterior aos 2 outros pent�gonos. Mas PF ser
exterior ao pent�gono superior esquerdo implica que PS seja interior a ele
(pois caso contr�rio, pela hip�tese b, PF seria interior a este pent�gono, o
que � imposs�vel). Pela mesma razao, PF ser exterior ao pent�gono inferior
central faz com que PS seja tamb�m interior a ele. Como PS nao pode ser
interior a 2 pent�gonos distintos simultaneamente, chegamos a um ABSURDO.

Como nao h� contra-exemplo para o enunciado que nao nos leve a um absurdo,

CONLUSAO:
"Qualquer curva que n�o passa por qualquer dos v�rtices mas que cruza todas
as arestas devera cruzar ao menos uma das arestas mais de uma vez".

C.Q.D.

[ ]'s

Alexandre Terezan
-----Mensagem Original-----
De: "Paulo Santa Rita" <p_ssr@hotmail.com>
Para: <obm-l@sucuri.mat.puc-rio.br>; <obm-l@mat.puc-rio.br>
Enviada em: Quarta-feira, 14 de Novembro de 2001 14:52 Terezan
Assunto: Traducao dos Problemas Russos


Ola Pessoal,
Tudo Legal ?

Talvez interesse a alguns estudantes que se preparam para Olimpiadas a
traducao que fiz dos 100 primeiros problemas russos. Coloquei em formato
Word para Windows.

Como nao podemos remeter para esta lista mensagens com arquivos anexados,
quem se interessar em ter estas traducoes basta me enviar um pedido por
e-mail que responderei com as traducoes anexadas.

Acrescento abaixo o primeiro problema :

1) Dados 12 v�rtices e 16 arestas dispostos como no diagrama abaixo :

X-----X-----X
|     |     |
X--X--X--X--X
|  |     |  |
X--X-----X--X

Prove que qualquer curva que n�o passa por qualquer dos v�rtices mas que
cruza todas as arestas devera cruzar ao menos uma das aresta mais de uma
vez.

Um Grande abraco a Todos !
Paulo Santa Rita
4,1251,141101





_________________________________________________________________
Chegou o novo MSN Explorer. Instale j�. � gratuito!
http://explorer.msn.com.br