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
=========================================================================