Osvaldo Mello Sponquiado wrote:
Sobre o problema "pq o numero de tartarugas queÉ Ramsey.
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 ...
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
=========================================================================
