10 bài toán chuyên đề Tổ hợp - Rời rạc dành cho HSG lớp 9 và thi lên 10 chuyên

Câu 1: Trên bảng ghi 20 câu khẳng định trong đó có một số câu đúng và một số câu sai.

Ban tổ chức đưa cho bạn Việt các phiếu sau:

1.Trên bảng có ít nhất 1 khẳng định sai

2.Trên bảng có ít nhất 2 khẳng định sai

3.Trên bảng có ít nhất 3 khẳng định sai

…

20.Trên bảng có ít nhất 20 khẳng định sai.

Việt có thể giữ nguyên thứ tự các phiếu trên hoặc đổi chỗ các phiếu đó với điều kiện: Nếu câu m đúng thì nhận thưởng 200.000 đồng  x m từ ban tổ chức. Hãy giúp bạn Việt sắp xếp hợp lí các câu trên để bạn Việt nhận được số tiền lớn nhất từ ban tổ chức.

Câu 2: Chứng minh rằng không thể phủ kín hình vuông 10 x 10 bằng 25 hình chữ nhật 1 x 4.

Câu 3:
a) Cho 6 điểm bất kỳ trên mặt phẳng trong đó không có 3 điểm nào thẳng hàng. Mỗi đoạn thẳng nối 2 điểm trong đó được tô màu xanh hoặc đỏ. CMR: tồn tại một tam giác có 3 cạnh cùng màu.

b) Cho 17 điểm bất kỳ trên mặt phẳng trong đó không có 3 điểm nào thẳng hàng. Mỗi đoạn thẳng nối 2 điểm trong đó được tô màu xanh, màu đỏ hoặc màu vàng. CMR: tồn tại một tam giác có 3 cạnh cùng màu.

Câu 4: Cho 20 số tự nhiên \({a_1} < {a_2} <  \ldots  < {a_{20}}\) không quá 70. Chứng minh rằng giữa các hiệu \({a_j}-{a_k},1 \le k < j \le 20\) luôn tìm được ít nhất 4 hiệu bằng nhau.

Câu 5: Cho 2015 số thực. Biết rằng tổng 4 số tùy ý trong 2015 số đã cho lớn hơn tổng 3 số tùy ý trong 2011 số còn lại. Chứng minh rằng tổng của 3 số tùy ý trong 2015 số đã cho lớn hơn tổng 2 số tùy ý trong 2012 số còn lại.

Câu 6: Xét tập X = {2, 3,4, …, 2100}. Tô màu các phần tử của X bởi một trong 5 màu: xanh, đỏ, tím, vàng, nâu. Chứng minh rằng tồn tại ba phần tử phân biệt a, b, c của X cùng màu sao cho: a là bội của b và b là bội của c.

Câu 7: Chứng minh rằng , mọi bưu phí không nhỏ hơn 12 xu, đều có thể tạo ra bằng các con tem có mệnh giá 4 xu và 5xu.

Câu 8: Tại mỗi đỉnh của đa giác đều 11 cạnh ta ghi số bất kì trong các số \(31;32;61;62;91;92;331;332;361;362;961\) (mỗi số chỉ dùng một lần). Vậy có tồn tại ba đỉnh của đa giác là 3 đỉnh của một tam giác cân và tổng các số ghi trên đỉnh là một số chia hết cho 3 không?

Câu 9: Mỗi đỉnh của một hình 7 cạnh đều được tô bằng một trong 2 màu xanh và đỏ. Chứng minh rằng với mọi cách tô như thế, luôn tìm được một tam giác cân có các đỉnh được tô cùng màu.

Câu 10: Trong mặt phẳng cho 2n điểm, trong đó không có 3 điểm nào thẳng hàng, có n điểm màu đỏ và n điểm màu xanh. Chứng minh rằng tồn tại một cách nối tất cả các điểm đỏ với các điẻm xanh bởi n đoạn thẳng, mỗi đoạn có hai đầu mút khác màu, mà không có đoạn thẳng nào cắt nhau.

PHẦN HƯỚNG DẪN GIẢI

Câu 1:

+ Ta gọi là bạn Việt được thưởng m điểm nếu câu m đúng.

+ Giả sử trong 20 câu trên bảng có a câu khẳng định sai với 1 \(\le \) a \(\le \) 19.

+ Xét các phiếu theo thứ tự mà ban tổ chức đưa cho bạn Việt thì từ phiếu số 1 đến phiếu số a có nội dung đúng, còn phiếu a + 1 đến phiếu 20 (phần còn lại) có nội dung sai.

+ Để nhận được tiền thưởng nhiều nhất thì bạn Việt cần chuyển các phiếu số 1, 2,3,..., a, a +1,..., 20 trở thành đúng thứ tự 20, 19, 18,.... a+1, a,...,2,1.

+ Vậy tổng số phiếu bạn Việt có được là: \(20 + 19 + 18 + ... + 21 - a = \frac{{(20 + 21 - a)a}}{2} = \frac{{a(41 - a)}}{2}\)

+ Tổng số tiền Việt nhận được \(\frac{{a(41 - a)}}{2}.200000 = 100000{\rm{a}}(41 - a)\) đồng

Câu 2:

+ Ta sẽ lần lượt tô các ô như hình, khi đó ta có tất cả 25 ô được tô màu đen.

+ Cứ mỗi lần đặt hình chữ nhật 1x4 vào ô thì hoặc là che đi 2 ô đen hoặc 0 ô đen (mỗi lần che đi chẵn ô đen).

+ Mà số 25 lẻ nên ta không thể phủ hết bằng các hình chữ nhật 1x4 được.

Câu 3: 

+ Xét 1 điểm bất kỳ thì sẽ nối được 5 đoạn với 5 điểm còn lại. Vì chỉ có hai màu nên có một màu có ít nhất 3 đoạn trở lên, giả sử 3 đoạn ấy màu đỏ.

+ Khi xét 3 điểm mà 3 đoạn màu đỏ đó, ta có tam giác màu đỏ, hoặc tương tự nếu là xanh, ta cũng có tam giác màu xanh.

+ Xét 1 điểm bất kỳ sẽ có 16 đoạn với 16 điểm còn lại, vì chỉ các đoạn có thể có 3 màu nên sẽ có loại cùng màu ít nhất 6 đoạn .

+ Giả sử đó là màu xanh, xét 6 điểm nối với điểm ban đầu màu xanh đó, nếu trong 6 điểm đó được nối ít nhất 1 đoạn màu xanh thì ta có tam giác màu xanh.

+ Nếu 6 điểm được nối với nhau bằng màu đỏ với vàng, thì ta sẽ thu được kết quả như câu a, ta sẽ có được 1 tam giác có ba cạnh cùng màu.

.....

---(Để xem tiếp nội dung của tài liệu các em vui lòng xem tại online hoặc đăng nhập để tải về máy)--- 

Trên đây là một phần nội dung tài liệu 10 Bài Toán bồi dưỡng HSG 9 và Luyện thi lên lớp 10 Chuyên. Để xem thêm nhiều tài liệu tham khảo hữu ích khác các em chọn chức năng xem online hoặc đăng nhập vào trang hoc247.net để tải tài liệu về máy tính.

Hi vọng tài liệu này sẽ giúp các em học sinh ôn tập tốt và đạt thành tích cao trong kì thi sắp tới. Chúc các em học tốt!