IMO 2019/P3

Discussion on International Mathematical Olympiad (IMO)
tanmoy
Posts: 288
Joined: Fri Oct 18, 2013 11:56 pm
Location: Rangpur,Bangladesh

IMO 2019/P3

Unread post by tanmoy » Thu Jul 18, 2019 11:02 pm

A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time:
  • Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged.
Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Proposed by Adrian Beker, Croatia
"Questions we can't answer are far better than answers we can't question"

Post Reply