Câu hỏi 99
Cho các số nguyên dương $n,k$ với $n\ge k+1$. Trên một hành tinh có $n$ quốc gia. Một số cặp quốc gia có quan hệ ngoại giao, và mỗi quốc gia có quan hệ với ít nhất $k$ quốc gia khác. Kẻ phản diện Duransha thực hiện kế hoạch sau.
- Trước tiên hắn chọn hai quốc gia phân biệt $A,B$ làm thủ lĩnh của hai phe $\mathcal A,\mathcal B$ tương ứng, với $A\in\mathcal A$ và $B\in\mathcal B$.
- Mỗi quốc gia còn lại chọn gia nhập một trong hai phe.
- Sau khi tất cả đã lựa chọn, mọi quan hệ ngoại giao giữa một quốc gia thuộc $\mathcal A$ và một quốc gia thuộc $\mathcal B$ đều bị cắt đứt.
Chứng minh rằng, bất kể các quan hệ ngoại giao ban đầu như thế nào, hắn luôn chọn được $A,B$ để ít nhất $k$ quan hệ bị cắt đứt, dù các quốc gia chọn phe ra sao.
- Trước tiên hắn chọn hai quốc gia phân biệt $A,B$ làm thủ lĩnh của hai phe $\mathcal A,\mathcal B$ tương ứng, với $A\in\mathcal A$ và $B\in\mathcal B$.
- Mỗi quốc gia còn lại chọn gia nhập một trong hai phe.
- Sau khi tất cả đã lựa chọn, mọi quan hệ ngoại giao giữa một quốc gia thuộc $\mathcal A$ và một quốc gia thuộc $\mathcal B$ đều bị cắt đứt.
Chứng minh rằng, bất kể các quan hệ ngoại giao ban đầu như thế nào, hắn luôn chọn được $A,B$ để ít nhất $k$ quan hệ bị cắt đứt, dù các quốc gia chọn phe ra sao.