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 3 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 đồ thị: 20 đỉnh là 20 vận động viên, nối cạnh giữa hai người đã thi đấu với nhau. Mỗi vòng mọi người đều đấu nên sau 3 vòng mỗi đỉnh có bậc đúng 3 (đồ thị 3-chính trên 20 đỉnh, có 60 cạnh). Cần tìm $k$ lớn nhất sao cho mọi đồ thị như vậy đều chứa một tập độc lập (các đỉnh đôi một không kề) cỡ $k$.

**Bước 1: Chắc chắn chọn được 5 người.** Chọn tập độc lập tham lam: chọn một đỉnh bất kỳ, loại bỏ nó cùng tất cả các đỉnh kề với nó. Vì mỗi đỉnh chỉ kề với đúng 3 đỉnh khác, mỗi bước loại đi nhiều nhất 4 đỉnh. Sau nhiều nhất $\lceil 20/4\rceil =5$ bước, mọi đỉnh đã bị loại, và các đỉnh đã chọn đôi một không kề. Vậy luôn chọn được ít nhất $k=5$ người đôi một chưa từng đấu với nhau.

**Bước 2: Không thể đảm bảo 6 người — dựng cách chia cặp phản ví dụ.** Chia 20 vận động viên thành 5 nhóm 4 người. Trong mỗi nhóm, cho 4 người đấu đủ 3 vòng tương ứng 3 cách ghép cặp hoàn hảo của $K_4$: vòng 1: (1-2),(3-4); vòng 2: (1-3),(2-4); vòng 3: (1-4),(2-3). Khi đó mỗi người đấu đúng 3 trận, hai người bất kỳ không đấu quá một lần, thỏa mãn đề bài. Trong mỗi nhóm 4 người, mọi cặp đều đã đấu với nhau, nên những người 'chưa từng đấu với nhau' phải thuộc các nhóm khác nhau, do đó chọn được nhiều nhất 1 người từ mỗi nhóm, tức nhiều nhất 5 người. Vậy có cách chia cặp mà không thể chọn 6 người đôi một chưa từng thi đấu.

**Kết luận:** Số nguyên dương $k$ lớn nhất cần tìm là $k=5$.