Một trường hè toán học gồm $3n$ (với $n\ge 2,n\in \mathbb{N}$) học sinh tham gia, trong đó hai học sinh quen nhau bất kỳ có đúng $n$ học sinh quen chung và hai học sinh không quen nhau bất kỳ có đúng $2n$ học sinh quen chung. Nếu ba học sinh đôi một quen nhau thì ta gọi là một nhóm "Bạn bè".

a) Xác định số lượng các nhóm "Bạn bè".

b) Chứng minh rằng: có thể chia $3n$ học sinh trường hè toán học trên thành ba tổ, mỗi tổ có $n$ học sinh sao cho khi lấy ngẫu nhiên mỗi tổ một học sinh thì ba học sinh này tạo thành một nhóm "Bạn bè".

Lời giải.

Với mỗi học sinh $A$, ký hiệu $d_A$ là số học sinh quen $A$.

Trước hết chứng minh mọi học sinh đều có cùng số người quen.

Lấy hai học sinh phân biệt $A,B$ và ta sẽ đếm số dãy $A-X-Y-B$ mà hai học sinh liên tiếp quen nhau.

Nếu $A,B$ không quen nhau, trong số $d_A$ học sinh $X$ quen $A$ có đúng $2n$ học sinh cũng quen $B$. Do đó số dãy trên bằng $2n\cdot n+(d_A-2n)\cdot 2n=2n{d}_A-2n^2$. Tương tự cũng có số dãy trên bằng $2n{d}_B-2n^2$, suy ra $d_A=d_B$.

Nếu $A,B$ quen nhau, trường hợp $X=B$ cho $d_B$ cách chọn $Y$. Ngoài ra có $n$ học sinh $X$ quen cả $A,B$, và $d_A-n-1$ học sinh $X$ quen $A$ nhưng không quen $B$. Vì vậy số dãy là $d_B+n^2+2n(d_A-n-1)$, tương tự cũng bằng $d_A+n^2+2n(d_B-n-1)$. Suy ra $(2n-1)(d_A-d_B)=0$, nên $d_A=d_B$.

Vậy mọi học sinh đều có cùng số người quen, kí hiệu là $d$.

Cố định một học sinh $A$ và ta sẽ đếm số cặp có thứ tự $(B,C)$ sao cho $A$ quen $B$, $B$ quen $C$ và $C\ne A$. Dễ dàng tính được số cặp như trên bằng $d(d-1)$.

Mặt khác, nếu $C$ quen $A$ thì có $n$ cách chọn $B$, còn nếu $C$ không quen $A$ thì có $2n$ cách. Do đó
$$d(d-1)=dn+2n(3n-1-d)$$
Khi đó $(d-2n)(d+3n-1)=0$, và vì $d>0$ suy ra $d=2n$.

Do đó mỗi học sinh đều quen đúng $2n$ người khác.

a) Số cặp học sinh quen nhau là $\frac{3n\cdot 2n}{2}=3n^2$. Mỗi cặp quen nhau có đúng $n$ người quen chung, nên nằm trong đúng $n$ nhóm "Bạn bè". Mỗi nhóm "Bạn bè" có ba cặp học sinh quen nhau. Vì vậy số nhóm "Bạn bè" là
$$\frac{3n^2\cdot n}{3}=n^3.$$

b) Với mỗi học sinh $A$, gọi $T_A$ là tập gồm $A$ và tất cả những học sinh không quen $A$. Vì $A$ quen đúng $2n$ học sinh nên $|T_A|=n$.

Nếu $A$ không quen $B$, hai học sinh này có đúng $2n$ người quen chung. Mà cả $A$ và $B$ đều có đúng $2n$ người quen, nên tập những người quen của $A$ và của $B$ trùng nhau. Do đó $T_A=T_B$.

Suy ra các tập $T_A$ hoặc trùng nhau, hoặc rời nhau, và mỗi tập có đúng $n$ phần tử. Vì có $3n$ học sinh nên toàn bộ học sinh được chia thành đúng ba tập như vậy, gọi là $T_1,T_2,T_3$.

Hai học sinh thuộc hai tập khác nhau phải quen nhau; nếu không thì chúng phải thuộc cùng một tập. Vì thế, chọn một học sinh từ mỗi $T_1,T_2,T_3$ thì ba học sinh đó đôi một quen nhau.

Vậy ba tập $T_1,T_2,T_3$ là ba tổ cần tìm.