Q6 Matemática  (EGMO 2012)

Existem infinitas pessoas cadastradas na rede social Mugbook. Alguns pares de usuários (diferentes) são registrados como amigos, mas cada pessoa tem apenas um número finito de amigos. Cada usuário tem pelo menos um amigo. (A amizade é simétrica; isto é, se $A$ é amigo de $B$, então $B$ é amigo de $A$.) Cada pessoa deve designar um de seus amigos como seu melhor amigo. Se $A$ designa $B$ como seu melhor amigo, então (infelizmente) não se segue que $B$ necessariamente designa $A$ como seu melhor amigo. Alguém designado como melhor amigo é chamado de melhor amigo de $1$. Mais geralmente, se $n>1$ for um número inteiro positivo, então um usuário é um $n$-melhor amigo, desde que tenha sido designado o melhor amigo de alguém que é um $(n-1)$-melhor amigo. Alguém que é um $k$-melhor amigo para cada inteiro positivo $k$ é chamado de popular. (a) Prove que toda pessoa popular é o melhor amigo de uma pessoa popular. (b) Mostre que se as pessoas podem ter infinitos amigos, então é possível que uma pessoa popular não seja a melhor amiga de uma pessoa popular. Romênia (Dan Schwarz)