Câu hỏi 32
Có vô hạn người đăng ký mạng xã hội Mugbook. Một số cặp người dùng khác nhau được đăng ký là bạn, nhưng mỗi người chỉ có hữu hạn bạn. Mỗi người có ít nhất một bạn. (Quan hệ bạn bè đối xứng: nếu $A$ là bạn của $B$ thì $B$ là bạn của $A$.)
Mỗi người phải chỉ định một người bạn làm bạn thân nhất. Nếu $A$ chọn $B$ làm bạn thân nhất thì, đáng tiếc, chưa chắc $B$ chọn $A$. Người được ai đó chọn làm bạn thân nhất gọi là bạn thân cấp $1$. Tổng quát, với số nguyên dương $n\gt 1$, một người là bạn thân cấp $n$ nếu được một người là bạn thân cấp $n-1$ chọn làm bạn thân nhất. Một người là bạn thân cấp $k$ với mọi số nguyên dương $k$ được gọi là nổi tiếng.
a. Chứng minh mỗi người nổi tiếng là bạn thân nhất của một người nổi tiếng.
b. Chỉ ra rằng nếu cho phép một người có vô hạn bạn, thì có thể có người nổi tiếng không là bạn thân nhất của bất kỳ người nổi tiếng nào.
Mỗi người phải chỉ định một người bạn làm bạn thân nhất. Nếu $A$ chọn $B$ làm bạn thân nhất thì, đáng tiếc, chưa chắc $B$ chọn $A$. Người được ai đó chọn làm bạn thân nhất gọi là bạn thân cấp $1$. Tổng quát, với số nguyên dương $n\gt 1$, một người là bạn thân cấp $n$ nếu được một người là bạn thân cấp $n-1$ chọn làm bạn thân nhất. Một người là bạn thân cấp $k$ với mọi số nguyên dương $k$ được gọi là nổi tiếng.
a. Chứng minh mỗi người nổi tiếng là bạn thân nhất của một người nổi tiếng.
b. Chỉ ra rằng nếu cho phép một người có vô hạn bạn, thì có thể có người nổi tiếng không là bạn thân nhất của bất kỳ người nổi tiếng nào.