2019 IMO Problems/Problem 3

Problem

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.

Page

Toolbox

Search

2019 IMO Problems/Problem 3

Problem