[obm-l] O Primeiro Problema Russo

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Ola Pessoal !

Esta mensagem e uma resposta a todos aqueles que me escreveram em off 
perguntando sobre o Primeiro Problema Russo. Se, para alguns, a resposta foi 
demorada, e por absoluta falta de tempo.

O Primeiro Problema Russo ( e 99 outros ) esta em :

http://www.mat.puc-rio.br/~nicolau/psr

Todas as perguntas podem ser resumidas nas 7 respostas abaixo.

1) Eu verifiquei o enunciado. Esta correto.

2) O Problema foi proposto na Olimpiada Nacional da Russia para alunos que 
estudam numa serie proxima ao nosso 3 ano do nivel medio.

3) Sim, voces podem resolve-lo usando a teoria dos grafos : considere cada 
regiao como um ponto e o caminho ligando duas regioes como uma aresta. 
Lembrem-se que que num grafo so ha um caminho euleriano se o grau de cada 
vertice e par

4) Sim, existe uma maneira de resolver sem usar a teoria dos grafos.
Basta observar que se ha um poligono convexo de N lados em um plano e N e 
par, entao se eu partir de fora do poligono e cruzar todas as arestas uma 
unica vez vou terminar tambem do lado de fora do poligono. Se N for impar, 
ocorre o contrario : se eu partir de fora termino dentro e vice-versa.

5) Claramente Sim. Voces podem generalizar o raciocinio acima para uma 
regiao arbitaria.

6) Nao. Caminho euleriano e uma coisa, caminho hamiltoniano e outra.

7) Nao. ( em minha opiniao ! ) Nao e necessario usar o teorema de Ramsey. Em 
verdade, nao vejo em que esse teorema pode ser util naquele caso.

Um Abraco a Todos
Paulo Santa Rita
2,1733,240203



_________________________________________________________________
MSN Messenger: converse com os seus amigos online.  
http://messenger.msn.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>
=========================================================================