Câu hỏi 77
Trên một mạng xã hội nọ có $2019$ người dùng, một số cặp trong đó là bạn bè, và quan hệ bạn bè có tính đối xứng. Ban đầu có $1010$ người mà mỗi người có $1009$ bạn và $1009$ người mà mỗi người có $1010$ bạn. Tuy nhiên, các quan hệ bạn bè khá bất ổn, nên các sự kiện dạng sau có thể xảy ra nhiều lần, mỗi lần một sự kiện:
Giả sử $A$, $B$, $C$ là ba người sao cho $A$ là bạn của cả $B$ và $C$, nhưng $B$ và $C$ không là bạn của nhau; khi đó $B$ và $C$ trở thành bạn, nhưng $A$ không còn là bạn của họ nữa.
Chứng minh rằng, bất kể quan hệ bạn bè ban đầu như thế nào, luôn tồn tại một dãy các sự kiện như vậy mà sau đó mỗi người dùng là bạn của nhiều nhất một người dùng khác.
Giả sử $A$, $B$, $C$ là ba người sao cho $A$ là bạn của cả $B$ và $C$, nhưng $B$ và $C$ không là bạn của nhau; khi đó $B$ và $C$ trở thành bạn, nhưng $A$ không còn là bạn của họ nữa.
Chứng minh rằng, bất kể quan hệ bạn bè ban đầu như thế nào, luôn tồn tại một dãy các sự kiện như vậy mà sau đó mỗi người dùng là bạn của nhiều nhất một người dùng khác.