2011/2/23 Pedro Cardoso <pedrolaz...@gmail.com>: > Olá. > > Meu professor propôs essa questão (retirada de um livro), mas depois de > discutirmos > chegamos à conclusão de que a solução dele não estava certa. Queria saber se > alguém resolve. > > "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". > > Isso pede indução, mas eu não consegui provar. Foi fácil ir de N ímpar pra N > par... > > [I] Hipótese: num grupo de 2N+1 pessoas, cada pessoa tem N amigos e é > possível fazer > uma arrumação legal. Pedro: essa hipótese não corresponde à indução. Veja que teto(2N+1/2) = N+1, e não N. Talvez trocando par por ímpar e fazendo essa correção o passo par -> ímpar dê certo.
> [II] Num grupo de 2N+2 pessoas, cada pessoa tem N+1 amigos. Tire o João do > grupo. > Agora restam 2N+1 pessoas e cada uma tem N amigos (no mínimo). Por [I], é > possível > fazer uma arrumação legal com as 2N+1 pessoas restantes. Agora ponha o João > entre duas > pessoas que ele conhece e que estão juntas. Isso é possível pelo princípio > da casa dos pombos, > já que o João conhece N+1 das 2N+1 pessoas da roda. > > Agora, quando em [I] a quantidade de pessoas é par, a ideia não vinga. > > Abraços, > > Pedro Cardoso. > Outra idéia: um problema desses tem uma cara de "calcular a probabilidade". Tente ver qual é a chance que um arranjo aleatório das pessoas em círculo não seja uma arrumação legal. Deve ser difícil de calcular, mas talvez não seja tão difícil assim provar que é menor do que 1. Assim, você conclui que deve existir uma arrumação legal (mas você não saberá como fazê-la...) 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 =========================================================================
