Bài toán. Cho $k\leq \frac{n}{2}$ và $F$ là một họ các ma trận con của một ma trận $n\times n$ sao cho hai ma trận con bất kì đều giao nhau ( có những phần tử chung ) thì $\left | F \right |\leq \left ( C_{n-1}^{k-1} \right )^{2}$, trong đó $\left | A \right |$ kí hiệu số phần tử của tập A.
Lời giải.
Với mọi ma trận con M thuộc họ F, đặt $R_{M};C_{M}$ là các bộ k- số chỉ thứ tự của các hàng và các cột . Dể dàng nhận thấy $R_{M};C_{M}$ xác định duy nhất ma trận M. Theo giả thiết của bài toán
$R_{M_{1}}\bigcap R_{M_{2}}\neq \varnothing ;C_{M_{1}}\bigcap C_{M_{2}}\neq \varnothing$ trong đó $M_{1};M_{2}$ là hai phần tử bất kì thuộc họ F.
Khi đó nếu đặt $R=\left \{ R_{M};M\in F \right \}$;$C=\left \{ C_{M};M\in F \right \}$ là hai họ con chứa các bộ k -số lấy từ n số sao cho hai bộ k- số bất kỳ đều có phần tử chung .
Theo định lý Erdos-Ko-Rado ( xem tuyển tập các chuyên đề tổ hợp ) ta thấy
$\left | R \right |\leq C_{n-1}^{k-1};\left | C \right |\leq C_{n-1}^{k-1}\textrm{}$
Theo nhận xét trên ta suy ra$\left | F \right |\leq \left ( C_{n-1}^{k-1}\right )^{2}$ (đpcm )
