Q19 Matemática  (Baltic Way 1997)

Em uma floresta, cada um dos $n$ animais ($n\ge 3$) vive em sua própria caverna, e há exatamente um caminho separado entre quaisquer duas dessas cavernas. Antes da eleição para Rei da Floresta alguns dos animais fazem campanha eleitoral. Cada animal de campanha visita cada uma das outras cavernas exatamente uma vez, usa apenas os caminhos para se mover de caverna em caverna, nunca muda de um caminho para outro entre as cavernas e retorna para sua própria caverna no final de sua campanha. Sabe-se também que nenhum caminho entre duas cavernas é usado por mais de um animal de campanha. a) Prove que para qualquer primo $n$, o número máximo possível de animais que fazem campanha é $\frac{n-1}{2}$. b) Encontre o número máximo de animais que fazem campanha para $n=9$.