(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à .
Đáp án chính thức: Tự luận
Quảng cáo
Câu hỏi này trích từ đề thi chính thức:

Đề Thi Học Sinh Giỏi Toán 11 Lần 17 2026 Khu Vực ĐH&ĐB Bắc Bộ

4 câu hỏi•Thời gian 180 phút•Chấm điểm & giải thích chi tiết

Các câu hỏi khác trong đề (4 câu)

Xem toàn bộ đề →
Chuyên đề Toán • Lớp 10, 11, 12

Bài tập trắc nghiệm cùng chuyên đề: Chứng minh tổ hợp (37 câu)

Câu luyện thêm 1Trích từ: Đề thi chọn HSG Toán 10 - THPT Chuyên KHTN - 2026-2027
Có 4 bạn nam và 4 bạn nữ tham gia các dự án ngoại khóa. Biết rằng:
+ Mỗi người tham gia tối đa 2 dự án.
+ Bất kỳ cặp 1 nam và 1 nữ nào cũng làm chung với nhau ít nhất 1 dự án.
Chứng minh rằng có ít nhất 1 dự án có từ 2 bạn nam và 2 bạn nữ trở lên cùng tham gia.
Xem trang câu hỏi →
Câu luyện thêm 2Trích từ: Kỳ Thi Chọn HSG Thành Phố Môn Toán Bảng B 2025-2026 - Ngày Thi 22/9/2025 - Đề Số 1
Cho tập hợp gồm 2025 số nguyên dương đầu tiên. Xét một tập con của tập hợp có nhiều hơn một phần tử thỏa mãn: với mỗi , nếu thì .

Gọi là số phần tử của tập hợp . Chứng minh tồn tại tập hợp là các tập con của tập hợp số tự nhiên và thỏa mãn đồng thời hai điều kiện sau:

i) và .

ii) Với mỗi , tồn tại sao cho .
Xem trang câu hỏi →
Câu luyện thêm 3Trích từ: Đề Chọn ĐTQG Tỉnh Đắk Lắk 2026-2027 - Ngày thi thứ nhất (22/09/2026) - Đề Số 1
Câu 4 (5,00 điểm). Một số nguyên dương được gọi là số cân bằng nếu như tồn tại một tập hợp gồm số nguyên dương sao cho nếu ta bỏ đi bất kì một phần tử nào của thì tất cả các phần tử còn lại có thể chia ra làm hai tập mà tổng các phần tử trong mỗi tập bằng nhau (số các số trong các tập có thể khác nhau).

a) Chứng minh rằng nếu là số cân bằng thì lẻ và .

b) Hãy tìm tất cả các số cân bằng.
Xem trang câu hỏi →
Câu luyện thêm 4Trích từ: Đề thi chọn học sinh giỏi cấp trường - Sở GD&ĐT Hải Phòng - THPT Chuyên Trần Phú - Môn Toán - 2026-2027
Trong bảng ô vuông xếp 661 quân đôminô sao cho mỗi quân đôminô phủ kín đúng 2 ô vuông hoặc , ngoài ra hai quân đôminô bất kỳ không chạm nhau (không có điểm chung kể cả ô cạnh hay đỉnh). Tìm giá trị nhỏ nhất của .
Xem trang câu hỏi →

Muốn biết hiện tại bạn đạt khoảng bao nhiêu điểm ở môn này? Làm thử đề nhanh 15 phút để hệ thống chấm điểm ngay.

Làm đề nhanh 15 phút ngay