Difference between revisions of "2019 IMO Problems/Problem 3"
(Created page with "== 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</mat...") |
(No difference)
|
Revision as of 12:29, 7 November 2019
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.