tente generalizar e ai voce vai ver os pepinos desta sua demo...Mas ela ta correta
-- Mensagem original -- >Helptentei usar contagem (seguindo o esquema de vários teoremas do Proofs >from The Book), ficou interessante: > >seja V = {1, 2, ..., 2n} e G = (V, E) nosso querido grafo. >defina d[i] como o grau do vértice i. > >é claro que soma{d[i], i=1..2n} = 2|E| = 2(n²+1) >se (i, j) é uma aresta de E e d[i] + d[j] > 2n então há um triângulo >contendo a aresta (i, j). (isso me parece óbvio, mas se não for para o >leitor, faça um desenho, é aplicação imediata do PCP). > >suponha que d[i] + d[j] <= 2n para toda aresta (i, j) de E. > >então, somando sobre toda aresta de E: > >S := soma{d[i] + d[j], (i, j) em E} = soma{d[i]², i=1..2n} >= 1/(2n) * >soma{d[i], i = 1..2n}² = 2|E|²/n >(aqui eu uso a desigualdade de Cauchy) > >por outro lado, temos que S <= 2n|E| > >logo 2n|E| >= 2|E|²/n <=> n²|E| >= |E|², o que é absurdo! > >isso já mostra que existe pelo menos um triângulo... estou sem tempo pra >verificar a parte mais legal, mas talvez saia desta mesma lógica. > >[ ]'s > >========================================================================= >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 >========================================================================= > TRANSIRE SVVM PECTVS MVNDOQUE POTIRE CONGREGATI EX TOTO ORBE MATHEMATICI INSIGNIA TRIBVUERE ------------------------------------------ Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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 =========================================================================