Câu hỏi 12
Trên một mạng xã hội nào đó, có 2019 người dùng, một số trong số đó là bạn bè, trong đó tình bạn là một mối quan hệ đối xứng. Ban đầu, có 1010 người với 1009 bạn và 1009 người với 1010 bạn mỗi người. Tuy nhiên, tình bạn khá không ổn định, vì vậy các sự kiện thuộc loại sau có thể xảy ra liên tục, lần lượt:
Hãy để $A, B$ và $C$ là những người sao cho $A$ là bạn của cả $B$ và $C$, nhưng $B$ và $C$ không phải là bạn bè; sau đó $B$ và $C$ trở thành bạn bè, nhưng $A$ không còn là bạn với họ nữa.
Chứng minh rằng, bất kể tình bạn ban đầu là gì, vẫn tồn tại dãy các sự kiện như vậy mà sau đó mỗi người dùng là bạn của tối đa một người dùng khác.
Hãy để $A, B$ và $C$ là những người sao cho $A$ là bạn của cả $B$ và $C$, nhưng $B$ và $C$ không phải là bạn bè; sau đó $B$ và $C$ trở thành bạn bè, nhưng $A$ không còn là bạn với họ nữa.
Chứng minh rằng, bất kể tình bạn ban đầu là gì, vẫn tồn tại dãy các sự kiện như vậy mà sau đó mỗi người dùng là bạn của tối đa một người dùng khác.