Q12 Matemática  (IMO Shortlist 2019)

Uma rede social tem usuários de $2019$, alguns dos quais são amigos. Sempre que o usuário $A$ for amigo do usuário $B$, o usuário $B$ também será amigo do usuário $A$. Eventos do tipo a seguir podem acontecer repetidamente, um de cada vez: Três usuários $A$, $B$ e $C$ de modo que $A$ seja amigo de $B$ e $C$, mas $B$ e $C$ não são amigos, altere seus status de amizade de modo que $B$ e $C$ agora sejam amigos, mas $A$ não seja mais amigo de $B$ e não seja mais amigo de $C$. Todos os outros status de amizade permanecem inalterados. Inicialmente, usuários de $1.010$ têm amigos de $1.009$ cada, e usuários de $1.009$ têm amigos de $1.010$ cada. Prove que existe uma sequência de tais eventos após a qual cada usuário é amigo de no máximo um outro usuário. Proposto por Adrian Beker, Croácia