Difference between revisions of "2019 IMO Problems/Problem 3"
Line 5: | Line 5: | ||
Initially, <math>1010</math> users have <math>1009</math> friends each, and <math>1009</math> users have <math>1010</math> friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user. | Initially, <math>1010</math> users have <math>1009</math> friends each, and <math>1009</math> users have <math>1010</math> 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 | https://youtu.be/p16MaqdvBQQ | ||
Latest revision as of 00:50, 19 November 2023
Contents
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
This problem needs a solution. If you have a solution for it, please help us out by adding it.
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 |