[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Traducao dos Problemas Russos
Oi Alexandre e
demais colegas desta lista,
A sua solucao esta correta. Por ser simples e bonita, e e bonita porque e
simples.
Este e o primeiro problema russo. A sua solucao e identica a que apresentei
em outra lista,aqui do Brasil mas de outro estado. Ela tem os seguintes
principios :
1)Se o numero de lados do poligono e impar e o tracado comecar fora do
poligono, entao o tracado vai ter que terminar dentro dele. Reciprocamente,
se o tracado comecar no interior do poligono, vai ter que terminar fora.
2)Se o numero de lados do poligono e par, as coisas se invertem.
E explorando estes dois principios que se prova facilmente que nao e
possivel executar um tracado, isto e, o tracado e impossivel.
Mas eu apresentei a solucao assim porque queria que o maior numero possivel
de pessoas pudessem entender. Numa competicao eu nao faria assim, pois o
tempo e um fator importante. Inclusive na outra lista eu mostrei como era
possivel fazer de outra forma, a saber :
1) Nomeie cada regiao com uma letra, inclusive a regiao exterior.
2) transforme cada aresta que precisa ser ultrapassada pelo caminho em um
arco que liga as duas regioes envolvidas
3) As arestas se transformam em arcos e as regios em pontos ligados por
estes arcos : temos um grafo.
4) Determinar se o problema tem solucao equivalem a responder se ha um
CAMINHO EULERIANO neste grafo.
5) Ora, um grafo so tem um caminho euleriano se qualquer de seus vertices
tem grau par, isto e, se concorre um quantidade par de arcos naquele
vertice.
6) O grafo em questao tem vertices de grau impar : logo, nao ha um caminho
euleriano nele. Logo, o tracado procurado e impossivel.
Um abraco
Paulo Santa Rita
4,1435,051101
>From: "Alexandre F. Terezan" <aleterezan@wnetrj.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>Subject: Re: Traducao dos Problemas Russos
>Date: Tue, 4 Dec 2001 15:43:08 -0200
>
>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
>
>
_________________________________________________________________
Chegou o novo MSN Explorer. Instale já. É gratuito!
http://explorer.msn.com.br