Tuyển tập các câu hỏi có đáp án chi tiết về toán tổ hợp, rời rạc bồi dưỡng học sinh giỏi 9

CÂU 5 ROIRACHSG9HP318 QN

1QN.Mỗi ô vuông đơn vị của một bảng có kích thước 10 × 10 ( 10 dòng , 10 cột) được ghi một

số nguyên dương không vượt quá 10. Hai số nào được ghi trong hai ô chung một cạnh hoặc hai ô

chung một đỉnh của bảng là hai số trùng nhau. Chứng minh rằng có số được ghi ít nhất 17 lần.

DAPAN

Trên hình vuông con kích thước 2x2 có không quá 1 số chia hết cho 2, có không quá một số chia

hết cho 3.

- Lát kín bảng bởi 25 hình vuông , kích thước 2x2 có nhiều nhất 25 số chia hết cho 2, có nhiều

nhất 25 số chia hết cho 3. Do đó có ít nhất 50 số còn lại không chia hết cho 2, cũng không chia

hết cho 3, vì vậy chúng phải là một trong các số 1; 5; 7.

Theo nguyên lý Đich-Le có một số xuất hiện ít nhất 17 lần .

2QN. Trên mặt phẳng cho điểm, trong đó không có bất kỳ 3 điểm nào thẳng hàng.

Người ta tô 2016 điểm bẳng màu đỏ và tô 2018 điểm còn lại bằng màu xanh. Chứng minh rằng:

bao giờ cũng tồn tại một cách nối tất cả các điểm màu đỏ với tất cả các điểm màu xanh bởi 2018

đoạn thẳng không có điểm nào chung.

Ta nhận thấy rằng luôn tồn tại cách nối 2018 cặp điểm với

nhau bằng 2018 đoạn thẳng và vì có 2018 cặp điểm nên số cách nối là hữu hạn. Và hiển nhiên là trong

hữu hạn cách nối đó ta luôn tìm ra được một cách nối có tổng độ dài các đoạn thẳng là ngắn nhất. Ta

chứng minh cách nối đó là cách mà chúng ta cần tìm. Thật vậy: Giả sử ngược lại ta có hai đoạn thẳng

AX và BY cắt nhau tại điểm O (giả sử A và B tô màu đỏ, còn X và Y tô màu xanh).

O

Y

B

A

X

Khi đó, nếu ta thay đoạn thẳng AX và BY bằng hai đoạn AY và BX, các đoạn còn lại giữ nguyên thì

cách nối này có tính chất:

1