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