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