(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 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 vận động viên đôi một chưa từng thi đấu với nhau?
(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 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 vận động viên đôi một chưa từng thi đấu với nhau?
Phương pháp & hướng dẫn giải
Phương pháp & hướng dẫn giải: Biểu diễn bài toán bằng lý thuyết đồ thị: 20 vận động viên tương ứng với 20 đỉnh; hai đỉnh kề nhau nếu hai vận động viên đó đã thi đấu với nhau. Mỗi vòng đấu là một ghép cặp... Xem đáp án chính thức và trọn bộ lời giải chi tiết từng bước câu hỏi thuộc Đề Thi Học Sinh Giỏi Toán 11 Lần 17 2026 Khu Vực ĐH&ĐB Bắc Bộ trên dethichuan.com.
Xem chi tiết từng bước giải & đáp án chính thức
Biểu diễn bài toán bằng lý thuyết đồ thị: 20 vận động viên tương ứng với 20 đỉnh; hai đỉnh kề nhau nếu hai vận động viên đó đã 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ị đều bậc 4 trên 20 đỉnh, là hợp của 4 ghép cặp hoàn hảo đôi một không chung cạnh. Cần tìm lớn nhất sao cho mọi đồ thị như vậy đều có tập độc lập (tập các đỉnh đôi một không kề nhau) kích thước ít nhất .
**Bước 1: Chứng minh với mọi lịch thi đấu.**
Giả sử phản chứng rằng tồn tại cách chia cặp sao cho . Xét đồ thị bù : là đồ thị đều bậc 15 trên 20 đỉnh nên có cạnh. Điều kiện tương đương (tức không chứa ). Theo định lý Turán, số cạnh tối đa của đồ thị trên 20 đỉnh không chứa là:
Do có đúng 150 cạnh nên dấu bằng xảy ra, suy ra phải là đồ thị Turán (đồ thị 4-phần đầy đủ với mỗi phần gồm 5 đỉnh). Khi đó là hợp rời của 4 đồ thị đầy đủ .
Tuy nhiên, trong mỗi vòng đấu, các cặp đấu nội bộ trong một nhóm 5 người (tập đỉnh của một ) có nhiều nhất cạnh, và luôn lẻ ra ít nhất 1 người phải đấu với người thuộc nhóm khác (mâu thuẫn vì không có cạnh nối giữa các ; hơn nữa sau 4 vòng mỗi nhóm 5 người chỉ có tối đa cạnh của ). Vậy .
**Bước 2: Chỉ ra một lịch đấu 4 vòng hợp lệ có .**
Chia 20 vận động viên thành 5 nhóm , mỗi nhóm 4 người ký hiệu (). Ta thiết lập lịch đấu 4 vòng sao cho nội bộ mỗi nhóm đấu đủ 6 trận (tạo thành 5 đồ thị rời nhau), và mỗi người đấu thêm đúng 1 trận với người nhóm khác:
- **Vòng 1:** .
- **Vòng 2:** .
- **Vòng 3:** .
- **Vòng 4:** .
Dễ dàng kiểm tra ở mỗi vòng, cả 20 vận động viên đều xuất hiện đúng 1 lần, không có hai người nào gặp nhau quá 1 lần, và mỗi nhóm tạo thành một . Vì mỗi tập độc lập chứa tối đa 1 đỉnh trong mỗi nên , suy ra (không thể chọn được 6 vận động viên đôi một chưa từng gặp nhau).
Vậy giá trị nguyên dương lớn nhất cần tìm là .
**Bước 1: Chứng minh với mọi lịch thi đấu.**
Giả sử phản chứng rằng tồn tại cách chia cặp sao cho . Xét đồ thị bù : là đồ thị đều bậc 15 trên 20 đỉnh nên có cạnh. Điều kiện tương đương (tức không chứa ). Theo định lý Turán, số cạnh tối đa của đồ thị trên 20 đỉnh không chứa là:
Do có đúng 150 cạnh nên dấu bằng xảy ra, suy ra phải là đồ thị Turán (đồ thị 4-phần đầy đủ với mỗi phần gồm 5 đỉnh). Khi đó là hợp rời của 4 đồ thị đầy đủ .
Tuy nhiên, trong mỗi vòng đấu, các cặp đấu nội bộ trong một nhóm 5 người (tập đỉnh của một ) có nhiều nhất cạnh, và luôn lẻ ra ít nhất 1 người phải đấu với người thuộc nhóm khác (mâu thuẫn vì không có cạnh nối giữa các ; hơn nữa sau 4 vòng mỗi nhóm 5 người chỉ có tối đa cạnh của ). Vậy .
**Bước 2: Chỉ ra một lịch đấu 4 vòng hợp lệ có .**
Chia 20 vận động viên thành 5 nhóm , mỗi nhóm 4 người ký hiệu (). Ta thiết lập lịch đấu 4 vòng sao cho nội bộ mỗi nhóm đấu đủ 6 trận (tạo thành 5 đồ thị rời nhau), và mỗi người đấu thêm đúng 1 trận với người nhóm khác:
- **Vòng 1:** .
- **Vòng 2:** .
- **Vòng 3:** .
- **Vòng 4:** .
Dễ dàng kiểm tra ở mỗi vòng, cả 20 vận động viên đều xuất hiện đúng 1 lần, không có hai người nào gặp nhau quá 1 lần, và mỗi nhóm tạo thành một . Vì mỗi tập độc lập chứa tối đa 1 đỉnh trong mỗi nên , suy ra (không thể chọn được 6 vận động viên đôi một chưa từng gặp nhau).
Vậy giá trị nguyên dương lớn nhất cần tìm là .
Đáp án chính thức: Tự luận