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!