2012 Egmo 2012 P6
Hay infinitas personas registradas en la red social Mugbook. Algunos pares de usuarios (diferentes) están registrados como amigos, pero cada persona tiene solo un número finito de amigos. Cada usuario tiene al menos un amigo. (La amistad es simétrica; es decir, si $A$ es amigo de $B$, entonces $B$ es amigo de $A$). Se requiere que cada persona designe a uno de sus amigos como su mejor amigo. Si $A$ designa a $B$ como su mejor amigo, entonces (desafortunadamente) no se sigue que $B$ necesariamente designe a $A$ como su mejor amigo. Alguien designado como mejor amigo se llama $1$-mejor amigo. Más generalmente, si $n> 1$ es un entero positivo, entonces un usuario es un $n$-mejor amigo siempre que haya sido designado como el mejor amigo de alguien que es un $(n-1)$-mejor amigo. Alguien que es un $k$-mejor amigo para todo entero positivo $k$ se llama popular. (a) Demuestre que toda persona popular es el mejor amigo de una persona popular. (b) Demuestre que si las personas pueden tener infinitos amigos, entonces es posible que una persona popular no sea el mejor amigo de una persona popular. Rumania (Dan Schwarz)
Inicia sesión para agregar soluciones y pistas