Bài 7a. Ứng với mỗi chương trình văn nghệ, ta mô phỏng việc ghép cặp của các cặp nam nữ song ca thành một bảng gồm $m$ hàng và $n$ cột như sau:
Bảng sẽ được đánh số 1 hoặc 0, trong đó: số 1 chỉ trong chương trình này, học sinh nữ ở hàng và học sinh nam ở cột tương ứng có song ca với nhau, số 0 chỉ hai học sinh đó không song ca.
Một bảng gọi là “tốt” nếu trên mỗi hàng và mỗi cột đều phải có ít nhất một số 1.
Xét một học sinh $X$ nào đó, giả sử đó là nữ; trường hợp học sinh nam chứng minh tương tự.
Chương trình tương ứng lệ thuộc học sinh $X$ nếu như tồn tại ít nhất 1 cột có đúng 1 số 1 nằm trên hàng của $X$, ta gọi bảng này là lệ thuộc X và cột như thế là cột lệ thuộc $X$.
Ta cần chứng minh rằng trong các bảng lệ thuộc $X$ thì số bảng có số các số 1 chẵn bằng số bảng có số các số 1 lẻ.
Thật vậy,
Xét trường hợp trong bảng có $k$ cột lệ thuộc $X$. Rõ ràng $k<m$ vì nếu không $k=m$ thì toàn bộ các ô trên hàng $X$ đều là 1, còn tất cả các ô còn lại của bảng đều là 0. Do $n\ge 2$ nên tồn tại 1 dòng toàn là số 0, mâu thuẫn.
Với $k<m$, ta bỏ $k$ cột đó ra khỏi bảng thì trên bảng sẽ mất đi đúng $k$ số 1. Mỗi ô trong $m-k$ ô còn lại của hàng $X$ sẽ được điền số 0 hoặc 1 tùy ý vì các cột còn lại đều còn ít nhất một số 1 nữa không thuộc hàng $X$. Do đó, nếu ta bỏ luôn hàng $X$ đi thì bảng còn lại vẫn là tốt.
Suy ra số bảng lệ thuộc $X$ trong trường hợp này sẽ là ${{2}^{m-k}}$ nhân với số lượng bảng tốt có kích thước $(m-k)\times (n-1)$ còn lại. Trong mỗi bảng sau khi đã bỏ các cột lệ thuộc $X$ đi, ta chọn một ô bất kỳ của hàng $X$ và thay đổi số từ $0\to 1,1\to 0$ thì sẽ dẫn đến thay đổi tính chẵn lẻ của số các số 1 trên bảng nên có số bảng có số các số 1 lẻ và chẵn là bằng nhau.
Ứng với mỗi $k=\overline{1,m-1}$ thì số lượng bảng có số 1 lẻ và chẵn đều bằng nhau nên tổng số bảng phụ thuộc $X$ có số các số 1 lẻ bằng với bảng có số các số 1 chẵn.
Ta có đpcm.
09-01-2015, 05:23 PM 
Chế độ Dạng cây