Tổ hợp

[Đề kiểm tra ĐTQG Hà Tĩnh 2013-2014]
Trên bàn cờ vua có một số quân cờ. Biết rằng nếu một ô nào đó còn trống thì tổng số lượng những quân cờ đứng cùng hàng và cùng cột với ô đó không nhỏ hơn $8$. Chứng minh rằng trên bàn cờ đó có ít nhất $32$ quân cờ.
Lời giải
 Ý tưởng phản chứng:

Giả sử có $\ge33$ ô trống. Theo nguyên lí Đi-rích-lê tồn tại một hàng X có $\ge5$ ô trống. 

Nếu hàng X đó có $0$ ô cờ thì xét bất kì $1$ ô trống ta thấy tổng số ô có cờ trên cột và hàng chứa ô đó $\le7$, mâu thuẫn. 

Nếu hàng X có $1$ ô cờ, $7$ ô trống thì trong $7$ cột chứa $7$ ô trống có $\ge33-7=26$ ô trống, theo nguyên lí Đi-rích-lê có $1$ cột có $\ge4$ ô trống, xét $1$ ô trống bất kì trong $7$ ô trống ta có điều mâu thuẫn. 

Nếu có $2$ ô cờ và $6$ ô trống xét tương tự.                

Nếu có $5$ ô trống và $3$ ô cờ, khi đó ở mỗi cột chứa ô trống có $\ge5$ cờ nên có $\le3$ ô trống. Do đó ở $3$ cột chứa $3$ ô có cờ ở hàng X có $\ge33-3\text{x}5=18$ ô trống. Chú ý trong $3$ cột này nếu có $1$ cột $\ge7$ ô trống thì vô lí nên chứng tỏ cột nào cũng có $6$ ô trống khi đó thì sẽ có một hàng có $3$ ô trống, xét bất kì $1$ trong $3$ ô trống này ta có mâu thuẫn.