Câu 4. (5 điểm) Trong một giải cờ vua, có 20 vận động viên tham gia. Mỗi vòng, các vận động viên được chia thành 10 cặp thi đấu với nhau. Hai vận động viên bất kỳ thi đấu với nhau không quá một lần. Tìm số nguyên dương $k$ lớn nhất thỏa mãn: Sau 4 vòng đấu, bất kể cách chia cặp đấu ra sao, có thể chắc chắn chọn ra $k$ vận động viên đôi một chưa từng thi đấu với nhau?

(AI giải đề cho tôi)
Biểu diễn bài toán bằng lý thuyết đồ thị: 20 vận động viên là 20 đỉnh; hai đỉnh kề nhau nếu hai người đã thi đấu với nhau. Mỗi vòng đấu là một ghép cặp hoàn hảo (perfect matching) gồm 10 cạnh; sau 4 vòng ta được đồ thị $G$ đều bậc 4 trên 20 đỉnh, là hợp của 4 ghép cặp hoàn hảo, không có cặp cạnh lặp. Cần tìm $k$ lớn nhất sao cho mọi đồ thị như vậy đều có tập độc lập (các đỉnh đôi một không kề) cỡ ít nhất $k$.

BƯỚC 1: Chứng minh mọi cách đấu đều cho phép chọn được 5 người đôi một chưa từng gặp nhau, tức $\alpha (G)\ge 5$.

Giả sử ngược lại $\alpha (G)\le 4$. Xét đồ thị bổ $H=\overline{G}$: $H$ là đồ thị 15-chuẩn trên 20 đỉnh nên có $\frac{20\cdot 15}{2}=150$ cạnh. Điều kiện $\alpha (G)\le 4$ tức $\omega (H)\le 4$, nghĩa là $H$ không chứa $K_5$. Theo định lý Turán, số cạnh lớn nhất của đồ thị trên 20 đỉnh không chứa $K_5$ là $$t_4(20)=\left(1-\frac{1}{4}\right)\cdot \frac{20^2}{2}=150.$$ Vậy $H$ đạt đúng số cạnh cực đại, suy ra $H$ chính là đồ thị Turán $T_4(20)$ (đa phần hoàn chỉnh với 4 phần, mỗi phần 5 đỉnh), do đó $G=\overline{H}$ là hợp rời của 4 đồ thị $K_5$.

Nhưng điều này vô lý: trong một vòng đấu, các cặp đấu nội bộ một nhóm $K_5$ (5 người) tạo thành một ghép cặp trên 5 đỉnh nên gồm tối đa 2 cạnh, luôn còn ít nhất 1 người của nhóm phải đấu với người ngoài nhóm; trong khi $G$ không có cạnh nối giữa các nhóm. Mỗi vòng chỉ có tối đa 2 cạnh nội nhóm nên 4 vòng có tối đa 8 cạnh, nhỏ hơn 10 cạnh của $K_5$. Mâu thuẫn. Vậy $\alpha (G)\ge 5$ với mọi cách chia cặp.

BƯỚC 2: Xây dựng một lịch đấu 4 vòng cụ thể sao cho không chọn được 6 người đôi một chưa từng gặp, tức tồn tại cách đấu với $\alpha (G)=5$.

Chia 20 người thành 5 nhóm $A,B,C,D,E$, mỗi nhóm 4 người đánh số $0,1,2,3$. Mỗi nhóm sẽ đấu đủ 6 cặp nội bộ (tạo thành một $K_4$); mỗi người còn đấu đúng 1 ván chéo với người của nhóm khác. Lịch cụ thể:

- Vòng 1 (A, B, C mỗi nhóm 2 ván nội bộ; D, E mỗi nhóm 1 ván nội bộ; 2 ván chéo):
$$a_0{a}_1,a_2{a}_3,b_0{b}_1,b_2{b}_3,c_0{c}_1,c_2{c}_3,d_2{d}_3,e_2{e}_3,d_2{e}_2,d_3{e}_3.$$
- Vòng 2 (A, B, C mỗi nhóm 2 ván nội bộ; D, E mỗi nhóm 1 ván nội bộ; 2 ván chéo):
$$a_0{a}_2,a_1{a}_3,b_0{b}_2,b_1{b}_3,c_0{c}_2,c_1{c}_3,d_0{d}_1,e_0{e}_1,d_0{e}_0,d_1{e}_1.$$
- Vòng 3 (A, B, C mỗi nhóm 1 ván nội bộ; D, E mỗi nhóm 2 ván nội bộ; 3 ván chéo):
$$a_0{a}_3,b_0{b}_3,c_0{c}_3,d_0{d}_2,d_1{d}_3,e_0{e}_2,e_1{e}_3,a_1{b}_1,a_2{c}_1,b_2{c}_2.$$
- Vòng 4 (A, B, C mỗi nhóm 1 ván nội bộ; D, E mỗi nhóm 2 ván nội bộ; 3 ván chéo):
$$a_1{a}_2,b_1{b}_2,c_1{c}_2,d_0{d}_3,d_1{d}_2,e_0{e}_3,e_1{e}_2,a_0{b}_0,a_3{c}_3,b_3{c}_0.$$

Kiểm tra tính hợp lệ:
- Mỗi vòng đúng 10 ván; mỗi người đấu đúng 1 ván mỗi vòng (kiểm tra từng vòng: mỗi tên xuất hiện đúng một lần).
- Nội bộ mỗi nhóm: 6 cặp $x_0{x}_1,x_2{x}_3$ (vòng 1 hoặc 3 tùy nhóm), $x_0{x}_2,x_1{x}_3$, $x_0{x}_3$, $x_1{x}_2$ — đủ 6 cặp của $K_4$, mỗi cặp đúng một lần.
- Các ván chéo: mỗi người đúng 1 ván chéo, mọi ván chéo nối hai người khác nhóm, không ván nào lặp lại.

Vậy đây là một lịch đấu hợp lệ sau 4 vòng. Trong đồ thị tương ứng, mỗi nhóm là một $K_4$ nên một tập độc lập chứa tối đa 1 đỉnh từ mỗi nhóm, suy ra $\alpha (G)\le 5$; hiển nhiên $\alpha (G)=5$. Do đó với cách chia cặp này không thể chắc chắn chọn 6 người đôi một chưa từng thi đấu.

KẾT LUẬN: Giá trị $k$ lớn nhất cần tìm là $k=5$.