Difference between revisions of "2019 IMO Problems/Problem 3"
(→Problem) |
|||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| + | |||
A social network has <math>2019</math> users, some pairs of whom are friends. Whenever user <math>A</math> is friends with user <math>B</math>, user <math>B</math> is also friends with user <math>A</math>. Events of the following kind may happen repeatedly, one at a time: | A social network has <math>2019</math> users, some pairs of whom are friends. Whenever user <math>A</math> is friends with user <math>B</math>, user <math>B</math> is also friends with user <math>A</math>. Events of the following kind may happen repeatedly, one at a time: | ||
Three users <math>A</math>, <math>B</math>, and <math>C</math> such that <math>A</math> is friends with both <math>B</math> and <math>C</math>, but <math>B</math> and <math>C</math> are not friends, change their friendship statuses such that <math>B</math> and <math>C</math> are now friends, but <math>A</math> is no longer friends with <math>B</math>, and no longer friends with <math>C</math>. All other friendship statuses are unchanged. | Three users <math>A</math>, <math>B</math>, and <math>C</math> such that <math>A</math> is friends with both <math>B</math> and <math>C</math>, but <math>B</math> and <math>C</math> are not friends, change their friendship statuses such that <math>B</math> and <math>C</math> are now friends, but <math>A</math> is no longer friends with <math>B</math>, and no longer friends with <math>C</math>. All other friendship statuses are unchanged. | ||
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 | ||
| + | |||
| + | ==Solution== | ||
| + | {{solution}} | ||
| + | |||
| + | ==See Also== | ||
| + | |||
| + | {{IMO box|year=2019|num-b=2|num-a=4}} | ||
Revision as of 00:49, 19 November 2023
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 | ||
