IMO 2019 Problema 3

Una red social tiene $2019$ usuarios, algunos de los cuales son amigos. Siempre que el usuario $A$ es amigo del usuario $B$, el usuario $B$ también es amigo del usuario $A$. Eventos del siguiente tipo pueden ocurrir repetidamente, uno a la vez: Tres usuarios $A$ ,$B$ ,y $C$ tales que $A$ es amigo de $B$ y de $C$, pero $B$ y $C$ no son amigos, cambian su estado de amistad de modo que $B$ y $C$ ahora son amigos, pero $A$ ya no es amigo ni de $B$ ni de $C$. Las otras relaciones de amistad no cambian. Inicialmente, hay $1010$ usuarios que tienen $1009$ amigos cada uno, y hay $1009$ usuarios que tienen $1010$ amigos cada uno. Demuestra que hay una sucesión de este tipo de eventos después de la cual cada usuario es amigo como máximo de uno de los otros usuarios.

5

0

Subido por: Kevin