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). 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 Em 24 de fevereiro de 2011 16:33, Pedro Cardoso <pedrolaz...@gmail.com>escreveu: > Opa, perdão! Confundi teto[ (2N+1)/2] = N+1. De qualquer forma, não > funciona do N ímpar pro N par mesmo. Olha só, Bernardo, Rogério e os > demais... > > -------- repetindo o enunciado por questão de clareza ----------- > > > "Prove que num grupo de N pessoas - onde cada pessoa tem pelo menos > teto(N/2) amigos - é > possível organizar todo mundo numa roda, de modo que cada pessoa fique > entre amigos." > > > Obs.1: se A é amigo de B, então B é amigo de A. > Obs.2: eu vou chamar a <maneira de arrumar as pessoas de modo que elas > entre amigos> > de "arrumação legal". > > > ------------------------------------------------------------------------------------- > > [I] Hipótese: num grupo de *2K+1* pessoas, cada pessoa tem *K+1* amigos e > é possível fazer > uma arrumação legal. > > [II] Num grupo de *2K+2* pessoas, cada pessoa tem *K+1* amigos. Tire o > João do grupo. > Agora restam *2K+1* pessoas e cada uma tem *K* amigos (no mínimo). Por > [I]... OPA! Não > dá pra usar [I]. > > > ---------------------------------------------------------------------------------------------------------------- > > Bernardo, não consegui ainda ter uma ideia pra achar a probabilidade de um > arranjo > aleatório ser uma arrumação legal. Mas continuo tentando! >
