2022 USAMO Problems/Problem 6
Problem
There are 
users on a social network called Mathbook, and some of them are Mathbook-friends. (On Mathbook, friendship is always mutual and permanent.)
Starting now, Mathbook will only allow a new friendship to be formed between two users if they have at least two friends in common. What is the minimum number of friendships that must already exist so that every user could eventually become friends with every other user?
Solution 1
To answer this question, we need to consider how friendships on Mathbook are formed. If two users have at least two friends in common, then they will be able to become friends with each other. This means that the minimum number of friendships that must already exist in order for every user to eventually become friends with every other user is the smallest number of friendships that guarantees that each pair of users has at least two friends in common.
One way to guarantee that each pair of users has at least two friends in common is to create a complete graph, where each user is friends with every other user. In this case, each pair of users has exactly 
friends in common. However, this is not the minimum number of friendships required, since some pairs of users may have more than two friends in common without forming a complete graph.
To find the minimum number of friendships required, we can use the fact that a friendship between two users implies that they share all of their mutual friends. In other words, if two users are friends, then they must have at least two friends in common. This means that if we want to guarantee that each pair of users has at least two friends in common, we can do so by ensuring that each user has at least two friends.
Therefore, the minimum number of friendships that must already exist in order for every user to eventually become friends with every other user is 
.
See also
| 2022 USAMO (Problems • Resources) | ||
| Preceded by Problem 5 |
Followed by Last Problem | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
