Combinatorics

Bài toán : Trong một trường học có $b$ thầy cô giáo và $c$ học sinh thỏa điều kiện :

a) Mỗi thầy cô giáo dạy đúng $k$ học sinh.

b) Với hai học sinh bất kì có đúng $h$ thầy cô dạy chung. 

Chứng minh rằng 

$$\frac{b}{h}=\frac{c(c-1)}{k(k-1)}$$

Lời giải :

Gọi $T_r$ là thầy dạy hai học sinh $S_i,S_j$. Ta đếm số bộ ba $(T_r,S_i,S_j)$ bằng hai cách.

Số cách chọn $T_r$ là $b$. Vì $T_r$ dạy đúng $k$ học sinh nên số cách chọn cặp học sinh $S_i,S_j$ là $C_k^2=k(k-1)$

Do đó số cách chọn bộ ba $(T_r,S_i,S_j)$ là $bk(k-1)$

Mặt khác vì $S_i,S_j$ có đúng $h$ thầy cô dạy chung nên $T_r$ có $h$ cách chọn. Mà số cặp $(S_i,S_j)$ có thể chọn là $C_c^2=c(c-1)$

Do đó số cách chọn bộ ba $(T_r,S_i,S_j)$ là $hc(c-1)$

Từ hai điều trên ta có :

$$\frac{b}{h}=\frac{c(c-1)}{k(k-1)}$$

Đây là điều phải chứng minh.