(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 3 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 đồ 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 (đồ... 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 Chọn Học Sinh Giỏi Lần 17 Toán 10 Khu Vực DH&ĐB Bắc Bộ 2026 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 đồ 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 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ỡ .

**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 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 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 : 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 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 Chọn Học Sinh Giỏi Lần 17 Toán 10 Khu Vực DH&ĐB Bắc Bộ 2026

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 đề: Nguyên lý Dirichlet (19 câu)

Câu luyện thêm 1Trích từ: Kỳ Thi Chọn Học Sinh Vào Đội Tuyển Bồi Dưỡng Dự Thi Học Sinh Giỏi Quốc Gia 2026-2027 - Sở GD&ĐT Lâm Đồng
(4,0 điểm) Bạn Hải tô màu số nguyên dương đầu tiên bởi đúng màu, mỗi số chỉ tô đúng một màu . Tìm giá trị nhỏ nhất của sao cho với mọi cách tô luôn tồn tại hai số được tô cùng màu mà hiệu của chúng là số chính phương trong mỗi trường hợp sau:

a) .

b) .
Xem trang câu hỏi →
Câu luyện thêm 2Trích từ: Cuộc Thi Olympic THPT TP Hồ Chí Minh 2024-2025
Trong dịp lễ tổng kết, cô giáo tặng thưởng 229 quyển vở giống nhau cho 10 em học sinh, sao cho em nào cũng có nhận được vở. Chứng minh rằng với mọi cách tặng thì
a) luôn có 2 em có số vở là 2 số có chữ số tận cùng giống nhau.
b) luôn có 4 em mà tổng số vở của 3 em bất kỳ trong đó lớn hơn số vở của em còn lại.
Xem trang câu hỏi →
Câu luyện thêm 3Trích từ: Đề Thi Học Sinh Giỏi thành phố bằng chuyên cấp THPT và chọn đội tuyển dự thi học sinh giỏi quốc gia 2026-2027 - Môn Toán - Ngày 1 (14/9/2026)
Một câu lạc bộ có 99 thành viên, trong đó có một số cặp quen biết nhau (quan hệ quen biết có tính hai chiều). Giả sử số lượng người quen của mỗi thành viên trong câu lạc bộ đều từ 81 đến 90.

a) Chứng minh rằng tồn tại 2 thành viên của câu lạc bộ có ít nhất 67 người quen chung.

b) Chứng minh rằng tồn tại 10 thành viên của câu lạc bộ cùng quen chung một người và có số lượng người quen bằng nhau.
Xem trang câu hỏi →
Câu luyện thêm 4Trích từ: Kỳ Thi Chọn Học Sinh Giỏi Cấp Tỉnh THPT Toán 2024-2025
(3,00 điểm) Dãy các số tự nhiên , , , được xác định như sau: , là các số tự nhiên nhỏ hơn 2025, còn với mọi thì là số nhỏ nhất trong các giá trị tuyệt đối của hiệu hai số hạng bất kì đứng trước nó. Chứng minh rằng .
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