Re: [obm-l] sutileza

["Osvaldo Mello Sponquiado" <1osv1@xxxxxxxxxx>]

> É Ramsey.
> Não precisa usar teoria de Ramsey não, isso é um dos 
primeiros teoremas 
> na teoria dos grafos, se não me engano foi o próprio 
Euler que provou.
> A idéia é simples, construa um grafo onde os 
vértices são tartarugas e 
> as arestas unem tartarugas que já acasalaram. Some 
os graus (nrs. de 
> arestas saindo de um vértice) de cada vértice, é 
evidente que essa soma 
> dá um número par pois cada aresta tem dois extremos 
e deve ter sido 
> contada duas vezes. Sendo assim, o número de 
vértices com grau ímpar tem 
> que ser par, pegou?

Sim ! valeu !
Eu tinha pensado nisto também, na Eureka me lembro de 
ter um problema parecido, porém fala sobre conhecer ou 
desconhecer mutuamente, que é um fato semelhante a 
acasalar. 

Até mais.





Atenciosamente,

Osvaldo Mello Sponquiado 
2º ano em Engenharia Elétrica 
UNESP - Ilha Solteira

 
__________________________________________________________________________
Acabe com aquelas janelinhas que pulam na sua tela.
AntiPop-up UOL - É grátis!
http://antipopup.uol.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
=========================================================================