2019 IMO Problems/Problem 3
Contents
[hide]Problem
A social network has users, some pairs of whom are friends. Whenever user is friends with user , user is also friends with user . Events of the following kind may happen repeatedly, one at a time: Three users , , and such that is friends with both and , but and are not friends, change their friendship statuses such that and are now friends, but is no longer friends with , and no longer friends with . All other friendship statuses are unchanged. Initially, users have friends each, and users have 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
Solution
Let be a graph with vertices representing the users and edges corresponding to their friendships.
We have the following properties:
1. is connected, since two non-adjacent vertices with no common friends will have at least vertices neighboring them, which is more than the rest of the vertices .
2. 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. 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 not in the cycle but adjacent to it, adjacent to it in the cycle, and a adjacent to in the cycle. Apply that event. Note that this preserves Property 1.
- If the smallest cycle is a triangle, let be a maximal clique in . By Property 4, . Take not in but adjacent to it, in adjacent to , and in not adjacent to . The must exist, since is maximal. Apply the event to . Note that this preserves Property 1.
This algorithm stops due to Property 3. When it stops, the resulting 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 or vertices each.
See Also
2019 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |