У соцiальнiй мережi 2019 користувачiв. Деякi користувачi товаришують з деякими iншими, при цьому якщо користувач \(A\) є другом користувача \(B\), то \(B\) також є другом \(A\). Змiни наступного типу здiйснюються послiдовно, по однiй змiнi за раз: обираються три користувачi \(A\), \(B\) та \(C\) такi, що \(A\) є другом для \(B\) та \(C\), але \(B\) i \(C\) не є друзями; пiсля цього \(B\) та \(C\) стають друзями, але \(A\) перестає бути другом для \(B\) i для \(C\). В усiх iнших парах вiдношення не змiнюються. Спочатку 1010 користувачiв мають по 1009 друзiв кожний, а 1009 користувачiв мають по 1010 друзiв кожний. \( \newline \) Доведiть, що iснує послiдовнiсть змiн, пiсля яких кожен користувач матиме не бiльше одного друга.
| Attributes | Олімпіадна |
|---|---|
| Source | International Mathematical Olympiad |
| Year | 2019 |
| Number | 3 |
| Difficulty | 10.0 |
| Themes |