2011/2/25 Rogerio Ponce <abrlw...@gmail.com>: > Oi Pedro, vamos la'... > > 1) Sabemos que a conjetura e' valida para um grupo com 3 pessoas. > > 2) Seja um grupo com 2K pessoas, incluindo Joao que, como todos, tem K > amigos no grupo. > Suponhamos que a conjetura seja valida para o grupo de 2K-1 pessoas > (excluindo Joao). Opa, Ponce, quando você tira o João do grupo, os K amigos dele passam a ter talvez apenas K-1 amigos, e como K-1 != Teto(2k-1/2) isso não é a conjectura original. Pense assim, você tem 4 pessoas, ABCD, amigas exclusivamente nessa ordem cíclica (A amigo de B e D, B amigo de A e C, ...). Se você retirar qualquer um dos participantes de grupo, já era, porque sobram (sem perda de generalidade) A,B e C, e você não pode botar A do lado de C... Acho que justamente você tem que tomar cuidado e fazer 2k => 2k-2 e ver que você pode entrar com um par na história... a idéia sendo que você vai retirar os caras com "menos amigos" (mas pelo menos K, senão você pode ir como você disse) e ao mesmo tempo fazer com que os amigos comuns sejam o mínimo possível, para depois de retirados esses dois você ter 2k-2 pessoas cada uma com pelo menos k-1 amigos.
> Portanto existe uma arrumacao legal com 2K-1 pessoas, sendo que K sao amigos > de Joao. > Pela "casa de pombos" existem pelo menos 2 amigos lado a lado. > Logo e' possivel inserir Joao entre estes dois amigos, e conseguir uma > arrumacao legal para 2K pessoas. > Ou seja, se for valido para um numero impar, sera' valido para o proximo > numero (par). > > 3) Seja um grupo com 2K+1 pessoas, incluindo Joao que, como todos, tem K+1 > amigos no grupo. > Suponhamos que a conjetura seja valida para o grupo de 2K pessoas (excluindo > Joao). > Portanto existe uma arrumacao legal com 2K pessoas, sendo que K+1 sao amigos > de Joao. > Pela "casa de pombos" existem pelo menos 2 amigos lado a lado. > Logo e' possivel inserir Joao entre estes dois amigos, e conseguir uma > arrumacao legal para 2K+1 pessoas. > Ou seja, se for valido para um numero par, sera' valido para o proximo > numero (impar). > > Portanto, a conjetura e' verdadeira. > > []'s > Rogerio Ponce Abraços, -- Bernardo Freitas Paulo da Costa ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
