Re: [obm-l] sutileza

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Osvaldo Mello Sponquiado wrote:

>Sobre o problema "pq o numero de tartarugas que 
>  
>
>>acasalam um numero impar de vezes eh par."
>>    
>>
>eu ainda nao vi solu�ao mais axo que deve ter alguma 
>sacada pelo T. de Ransey (ou Ramsey, nao sei a grafia 
>correta)
>
>
>Alguem ai tem alguns problemas em que se usa Ramsey 
>para problemas de grafos nao hamiltonianos para 
>discutir ...
>
>  
>
� 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?
=========================================================================
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
=========================================================================