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.

Video Solution

https://youtu.be/p16MaqdvBQQ

Solution

Let $G$ be a graph with $2019$ vertices representing the users and edges corresponding to their friendships.

We have the following properties:

1. $G$ is connected, since two non-adjacent vertices with no common friends will have at least $1009+1009=2018$ vertices neighboring them, which is more than the rest of the vertices $2019-2=2017$ .

2. $G$ has vertices of odd degree, and this property remains invariant after an event. Note that the parity of the degrees of the vertices is invariant after an event.

3. The total number of edges strictly decreases after an event.

4. $G$ does not contain all possible edges (it is not a clique), and this property remains invariant after an event, since events decrease the number of edges.

Algorithm: Repeat the following operations, while possible.

If there is a cycle, and the smallest cycle is not a triangle, take $a$ not in the cycle but adjacent to it, $b$ adjacent to it in the cycle, and $c$ a adjacent to $b$ in the cycle. Apply that event. Note that this preserves Property 1.

If the smallest cycle is a triangle, let $K$ be a maximal clique in $G$ . By Property 4, $K\neq G$ . Take $a$ not in $K$ but adjacent to it, $b$ in $K$ adjacent to $a$ , and $c$ in $K$ not adjacent to $a$ . The $c$ must exist, since $K$ is maximal. Apply the event to $a,b,c$ . Note that this preserves Property 1.

This algorithm stops due to Property 3. When it stops, the resulting $G$ must still satisfy Property 1 (it is connected). Since no more steps can be applied, then there cannot be cycles. It is a tree.

5. Note that events can be applied to a tree whenever there is a vertex of degree at least 2, and that after the event, we get two trees.

Apply events until no more are possible. Due to Property 3, this iteration stops. Due to Property 5, it stops with a forest of trees with $2$ or $1$ vertices each.

2019 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

2019 IMO Problems/Problem 3

Contents

Problem

Video Solution

Solution

See Also