Câu hỏi 25
Có $n$ con cừu và một con sói đội lốt cừu. Một số con cừu là bạn của nhau (quan hệ bạn bè có tính hai chiều). Mục tiêu của sói là ăn hết tất cả các con cừu. Đầu tiên, nó chọn một số con trong $n$ con cừu để kết bạn. Sau đó mỗi ngày, nó chọn một con cừu trong số bạn của mình để ăn thịt. Mỗi khi nó ăn một con cừu $A$:
(i) mỗi con cừu là bạn của $A$ mà vốn là bạn của sói sẽ cắt đứt quan hệ bạn bè với sói;
(ii) mỗi con cừu là bạn của $A$ mà vốn không phải bạn của sói sẽ trở thành bạn của sói.
Quá trình lặp lại cho đến khi sói không còn người bạn nào.
Tìm số nguyên dương $m$ lớn nhất (theo $n$) thỏa mãn điều kiện sau:
tồn tại một quan hệ bạn bè giữa $n$ con cừu sao cho sói có tổng cộng $m$ cách khác nhau chọn tập bạn ban đầu để có thể ăn hết tất cả các con cừu.
(i) mỗi con cừu là bạn của $A$ mà vốn là bạn của sói sẽ cắt đứt quan hệ bạn bè với sói;
(ii) mỗi con cừu là bạn của $A$ mà vốn không phải bạn của sói sẽ trở thành bạn của sói.
Quá trình lặp lại cho đến khi sói không còn người bạn nào.
Tìm số nguyên dương $m$ lớn nhất (theo $n$) thỏa mãn điều kiện sau:
tồn tại một quan hệ bạn bè giữa $n$ con cừu sao cho sói có tổng cộng $m$ cách khác nhau chọn tập bạn ban đầu để có thể ăn hết tất cả các con cừu.