Tổ hợp

Trong quốc hội Mỹ ,mỗi nghị sỹ có không quá 3 kẻ thù .chứng minh rằng có thể chia quốc hội thành 2 viện ,sao cho trong mỗi viện,mỗi nghị sỹ có không quá một kẻ thù

Giải
Giả sử phản chứng ngược lại. Khi đó mọi cách chia hai nhóm đều tồn tại một nhóm có ít nhất 1 nghị sĩ có kẻ thù ít nhất là $2$. Vì số cách chia là hữu hạn. Do đó ta tìm ra được cách chia mà tổng số kẻ thù ứng với từng nghị sĩ là nhỏ nhất. Ta xem xét cách chia như vậy. Gọi $A,B$ là các nhóm và $T(A)$ và $T(B)$ là tổng số kẻ thủ của các nghị sĩ của từng cách. Không mất tính tổng quát, ta có thể giả sử trong $A$ có 1 nghị sĩ $X$ có ít nhất là $2$ kẻ thù. Ta sẽ xây dựng cách chia nhóm mới như sau: Ta chuyển nhóm nghị sĩ $X$ từ $A$ qua $B$. Khi đó ta có 2 nhóm mới là $A'$ và $B'$ với tổng số kẻ thù của các nghị sĩ trong các nhóm là $T(A'), T(B')$. Số kẻ thù trong $B$ của $X$ rõ ràng không quá 1. Ta có :

 $T(A')+T(B')\le T(A)-2+T(B)-1\le T(A)+T(B)-1$

Đây là điều mâu thuẫn với cách chia nhóm $A,B$. Do đó ta có điều cần chứng minh.