Bài tập nguyên lý dirichlet toán rời rạc có lời giải

Trong bài viết này, TTnguyen xin gửi tới bạn bài viết các dạng bài tập nguyên lý dirichlet toán rời rạc giúp các bạn ôn tập được dễ dàng hơn.

Các dạng bài tập nguyên lý dirichlet

Bài 1. Có thể chia các số nguyên liên tiếp từ 1 đến 50 thành các nhóm rời nhau sao cho trong mỗi nhóm, số lớn nhất bằng tổng các số còn lại trong nhóm được hay không?

Giải

Bài 2. Có 17 cầu thủ và 15 cổ động viên xếp thành một hàng ngang. Chứng minh rằng có ít nhất 2 cầu thủ mà giữa họ có đúng 5 người khác đứng xen vào.

Giải

Giả sử đánh số 17 cầu thủ và 15 cổ động viên từ 1 đến 32 và chia thành các nhóm:

Nhóm 1: 1,7,13,19,25,31
Nhóm 2: 2,8,14,20,26,32
Nhóm 3: 3,9,15,21,27
Nhóm 4: 4,10,16,22,28
Nhóm 5: 5,11,17,23,29
Nhóm 6: 6,12,18,24,30

Coi 6 nhóm như 6 chuồng chim, 17 cầu thủ như 17 con chim bồ câu. Theo định lý Dirichlet có ít nhất 4 cầu thủ thuộc cùng 1 nhóm. Vì nếu chỉ có 3 cầu thủ thuộc cùng 1 nhóm thì chưa thoả mãn yêu cầu đề bài.

Ví dụ ta xét nhóm 1:

Trường hợp 1: 1,7,13,25
Trường hợp 2: 1,7,13,31
Trường hợp 3: 1,7,13,19
Trường hợp 4: 7,13,19,25
Trường hợp 5: 7,13,19,31
Trường hợp 6: 13,19,25,31

Như vậy trong mọi trường hợp luôn có 2 cầu thủ mà giữa chúng có 5 cổ động viên xen vào.

Xem thêm: Bài tập phép đếm toán rời rạc có lời giải

Bài 3. Lấy 21 số nguyên dương có giá trị không lớn hơn 40. Chứng minh rằng có ít nhất 6 cặp số mà hiệu giữa chúng có giá trị bằng nhau.

Giải

Cứ 2 số tạo thành 1 cặp và tạo thành 1 hiệu, lấy 21 số nên tạo thành \(C_{21}^2=210\) cặp(coi như 210 con chim bồ câu)

Hiệu 2 số có giá trị nhỏ nhất là: 1

Hiệu 2 số có giá trị lớn nhất là: 39(coi như 39 chuồng chim)

Theo nguyên lý Dirichlet có ít nhất \(] \frac{210}{39}=6 [\). Vậy có ít nhất 6  cặp thuộc cùng 1 nhóm tức là có ít nhất 6 cặp số mà hiệu giữa chúng có giá trị bằng nhau.

Bài 4. Chứng minh rằng trong số 9 số khác nhau lấy từ {1, 2, …, 225} có ít nhất 2 số x và y sao cho \(0<|\sqrt{x} -\sqrt{y}|<2\)

Giải

Xếp các số thoả mãn điều kiện \(0<|\sqrt{x} -\sqrt{y}|<2\) vào thành 1 nhóm:

Nhóm 1: {1,2,…,8}
Nhóm 2: {9,10,..,24}
Nhóm 3: {25,26,..,48}
Nhóm 4: {49,50,..,80}
Nhóm 5: {81,82,..,120}
Nhóm 6: {121,122,..,168}
Nhóm 7: {169,..,224}
Nhóm 8: {225}

Lấy 9 số mà có 8 nhóm => Theo nguyên lý Dirichlet có ít hất 2 số thuộc cùng 1 nhóm.

Bài 5. Chứng minh rằng trong số 10 người bất kỳ luôn tồn tại 2 người có tổng số hoặc hiệu số tuổi của họ chia hết cho 17.

Giải

Chọn ra các cặp sao cho tổng các cặp bằng 17

Nhóm 1:(0,0)
Nhóm 2:(1,16)
Nhóm 3:(2,15)
Nhóm 4:(3,14)
Nhóm 5:(4,13)
Nhóm 6:(5,12)
Nhóm 7:(6,11)
Nhóm 8:(7,10)
Nhóm 9:(8,9)

Coi 9 nhóm như 9 chuồng chim bồ câu, 10 người coi như 10 con chim bồ câu. Theo nguyên lý Dirichlet tồn tại ít nhất 2 người mà có tổng hoặc hiệu số tuổi chia hết cho 17

Bài 6. Cho A là một tập gồm các chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Chứng minh rằng trong các số có 4 chữ số lấy từ tập A mà các chữ số tạo thành 1 dãy giảm sẽ có ít nhất 9 số có tổng các chữ số bằng nhau

Giải

Cứ 4 chữ số tạo thành 1 tập con và tạo thành dãy giảm => Các cách để sắp xếp sao cho các chữ số tạo thành dãy giảm là: \(C_{10}^4\) = 210 cách (coi như 210 con chim bồ câu)

Các tập con có tổng bằng nhau tạo thành 1 nhóm:

Nhóm 1: tổng bằng 6 (3,2,1,0)
Nhóm 2: tổng bằng 7
…
Nhóm 25: tổng bằng 30 (9,8,7,6)

Coi 25 nhóm như 25 chuồng chim bồ câu. Theo nguyên lý Dirichlet có ít nhất \(] \frac{210}{30}=9 [\) tập con có tổng bằng nhau.

Bài 7: Chứng minh rằng trong 14 số lấy bất kì từ các số{1,2,3,..,25} có ít nhất 2 số có tổng bằng 26

Giải

Phân tập X thành 13 nhóm, trong đó 12 nhóm có tổng bằng 26, 1 nhóm bằng 13

Nhóm 1: (1,25)
Nhóm 2:(2,24)
Nhóm 3:(3,23)
Nhóm 4:(4,22)
Nhóm 5:(5,21)
Nhóm 6:(6,20)
Nhóm 7:(7,19)
Nhóm 8:(7,18)
Nhóm 9:(8,17)
Nhóm 10:(10,16)
Nhóm 11:(11,15)
Nhóm 12:(12,14)
Nhóm 13:(13)

Có 13 nhóm và lấy 14 số. Nên theo nguyên lý Dirichlet có ít nhất 2 số thuộc cùng 1 nhóm có tổng bằng 26(dpcm)

Bài 8:Cho 9 điểm có toạ độ nguyên trong không gian 3 chiều. Chứng minh rằng có ít nhất 2 điểm mà trung điểm của chúng có cùng toạ độ nguyên

Giải

Giả sử trong mặt phẳng Oxyz có A(x₁,y₁,z₁), B(x₂,y₂,z₂). Vậy trung điểm của đoạn thẳng AB sẽ là:

Các tọa độ này nguyên khi:

• Các tọa độ này có cùng tính chẵn lẻ

Chia các số thành các nhóm

Nhóm 1: (chẵn, chẵn, chẵn)
Nhóm 2: (chẵn, lẻ, chẵn)
Nhóm 3: (chẵn, chẵn, lẻ)
Nhóm 4: (chẵn, lẻ, lẻ)
Nhóm 5: (lẻ, lẻ, lẻ)
Nhóm 6: (lẻ, chẵn, lẻ)
Nhóm 7: (lẻ, chẵn, chẵn)
Nhóm 8: (lẻ, lẻ, chẵn)

Vì có 8 nhóm có tính chẵn lẻ với nhau. Nên theo nguyên lý Dirichlet có ít nhất 2 điểm thuộc cùng 1 nhóm có tính chẵn lẻ như nhau. Do đó trung điểm của 2 điểm đó sẽ có tọa độ nguyên (đpcm)

Giả sử lấy ngẫu nhiên 9 điểm trong không gian Oxyz:

(2;4;6) , (2,4,5) , (1,3,6) , (7,8,9) , (2,5,1) , (1,2,6) , (6,4,9) , (4,6,7) , (3,5,8)

Chia thành 8 nhóm như trên ta được:

Nhóm 1: (chẵn, chẵn, chẵn) (2;4;6)
Nhóm 2: (chẵn, lẻ, chẵn)
Nhóm 3: (chẵn, chẵn, lẻ) (2,4,5) (6,4,9) (4,6,7)
Nhóm 4: (chẵn, lẻ, lẻ) (2,5,1)
Nhóm 5: (lẻ, lẻ, lẻ)
Nhóm 6: (lẻ, chẵn, lẻ) (7,8,9)
Nhóm 7: (lẻ, chẵn, chẵn) (1,2,6)
Nhóm 8: (lẻ, lẻ, chẵn) (1,3,6) (3,5,8)

=> có ít nhất 2 điểm có trung điểm là tọa độ nguyên.

Bài viết của mình đến đây là kết thúc. Hy vọng với tài liệu trên các bạn đã biết cách giải bài tập nguyên lý dirichlet cơ bản trong môn toán rời rạc. Cảm ơn các bạn đã tham khảo bài viết trên ttnguyen.net. Chúc các bạn học tập tốt!