IMO 2019 Shortlist C5
On a certain social network, there are 2019 users, some pairs of which are friends, where friendship is a symmetric rela...
Category: Combinatorics
Problem
On a certain social network, there are 2019 users, some pairs of which are friends, where friendship is a symmetric relation. Initially, there are 1010 people with 1009 friends each and 1009 people with 1010 friends each. However, the friendships are rather unstable, so events of the following kind may happen repeatedly, one at a time: Let A, B, and C be people such that A is friends with both B and C, but B and C are not friends; then B and C become friends, but A is no longer friends with them. Prove that, regardless of the initial friendships, there exists a sequence of such events after which each user is friends with at most one other user. (Croatia) Shortlisted problems 7