Bernardo, com o Joao no grupo de N+1 pessoas, marque um X nas costas dos amigos dele. Retire o Joao do grupo. Suponhamos que a conjetura valha para N, certo? Faca uma arrumacao legal com o que sobrou. Havera' pelo menos duas pessoas lado a lado e com X nas costas. Coloque o Joao entre estes dois.
[]'s Rogerio Ponce Em 25 de fevereiro de 2011 05:18, Bernardo Freitas Paulo da Costa < bernardo...@gmail.com> escreveu: > 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 > ========================================================================= >
