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

Note that if there's a relation between any two users, then it will satisfy the case. However, we are having too much overlaps because after we remove one of the existing relations, the model still satisfies the requirement. Therefore, this is asking the situation which will be not acceptable once a relation between two random users are removed. Since it's asking for an overlapping of minimum of 2 friends, then we have the lemma: The model with the fewest relations has the characteristic of being invalid once a relationship is removed, which is a model composed by 2020 users who each has a relation between the and the user. Proof: Firstly, it's easy to see that this satisfies the requirement. However, if we remove one of the 4040 relations, then there will be a user that has only one relation with the rest of the users, which is invalid. Hence, this is the required model, and our answer is 4040. DONE!

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.