Bộ 19 Chuyên đề Bồi dưỡng HSG Toán 7 - Chuyên đề 16: Ứng dụng nguyên lý Dirichlet

 CHUYÊN ĐỀ 16 :
 ỨNG DỤNG NGUYÊN LÝ DIRICHLET
I. TÓM TẮT LÍ THUYẾT.
 - Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet đề xuất từ thế kỷ XX đã được 
áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển 
từ một mệnh đề rất đơn giản gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý “chuồng chim bồ 
câu”: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc 
chắn có ít nhất một ngăn có nhiều hơn một con chim. 
- Một cách tổng quát, nguyên lý Dirichlet được phát biểu như sau: Nếu xếp nhiều hơn n+1 đối tượng 
vào n cái hộp thì tồn tại ít nhất một hộp chứa không ít hơn hai đối tượng.
- Việc chứng minh nguyên lý này có thể tiến hành bằng lập luận phản chứng rất đơn giản: Giả sử 
không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các 
hộp, trái với giả thiết là số đối tượng lớn hơn n.
- Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào m cái chuồng thì tồn tại một chuồng có ít nhất 
 n m 1 
 con thỏ .
 m 
* Một số chú ý:
1. Các bài toán áp dụng nguyên tắc Đirichle thường là các bài toán chứng minh sự tồn tại của sự vật, 
sự việc mà không cần phải chỉ ra một cách tường minh sự vật, sự việc đó.
2. Nhiều bài toán, nguyên tắc Đirichle chỉ xuất hiện sau khi biến đổi qua một bước trung gian, hoặc 
thành lập các dãy số mới.
3. Để giải bài toán áp dụng nguyên tắc Đirichle, nhiều khi ta phải kết hợp với phương pháp chứng 
minh phản chứng.
4. Khi giải các bài toán mà ta đã biết phải áp dụng nguyên tắc Đirichle hoặc dự đoán sẽ phải dùng 
nguyên tắc này, chúng ta cần suy nghĩ hoặc biến đổi bài toán để làm xuất hiện khái niệm "thỏ" và 
"lồng", khái niệm "nhốt thỏ vào lồng" và thỏa mãn các điều kiện:
+ Số thỏ phải nhiều hơn số lồng.
+ Thỏ phải được nhốt hết vào các lồng, nhưng không bắt buộc lồng nào cũng phải có thỏ.
5. Cũng có thể có những bài toán phải áp dụng 2, 3 lần nguyên tắc Đirichle.
6. Trong suy nghĩ khi giải toán ta cố gắng làm xuất hiện các khái niệm "thỏ" và "lồng", nhưng trong 
trình bày phần lời giải ta cố gắng diễn đạt theo ngôn ngữ toán học thông thường.
7. Khi giải xong các bài toán áp dụng nguyên tắc Điriclê, chúng ta cố gắng suy nghĩ để sáng tạo ra 
được các bài toán tổng quát hơn hoặc cụ thể hơn. Vì chỉ có như thế ta mới thật nắm chắc bài toán mà 
mình đã làm.
II.CÁC DẠNG BÀI TẬP:
DẠNG 1. SỰ TƯƠNG HỖ
Bài 1. Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong 
suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.
Phân tích: Ta thành lập được các cái lồng đó là các lồng chứa số trận đã đấu của các đấu thủ (có 4 
lồng), số đấu thủ ta coi là các con thỏ.
 Lời giải Giả sử 6 đội bóng đó là A, B, C, D, E, F . Xét đội A :
 Theo nguyên lý Dirichlet ta suy ra: A phải đấu hoặc không đấu với ít nhất 3 đội khác.
 Không mất tính tổng quát, giả sử A đã đấu với B, C, D .
 + Nếu B, C, D từng cặp chưa đấu với nhau thì bài toán được chứng minh.
 + Nếu B, C, D có 2 đội đã đấu với nhau, ví dụ B và C thì 3 đội A, B, C từng cặp đã đấu với 
nhau.
 Như vậy bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau hoặc chưa đấu với nhau 
trận nào.
Bài 4. Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2 và chỉ có 2 học sinh được điểm 
10 . Chứng minh rằng ít nhất cũng tìm được 6 học sinh có điểm kiểm tra bằng nhau ( điểm kiểm tra là 
một số tự nhiên từ 0 đến 10).
 Lời giải
Số học sinh có điểm kiểm tra từ 2 đến 9 là : 45 – 2 43
Ta có : 43 8.5 3
Như vậy , khi phân chia 43 học sinh vào 8 loại điểm kiểm tra ( từ 2 đến 9 ) thì theo nguyên lí Dirichlet 
luôn tồn tại ít nhất 5 1 6học sinh có điểm kiểm tra giống nhau (đpcm )
Bài 5. Có 17 nhà toán học trao đổi với nhau về 3 vấn đề. Mỗi người tra đổi với một người về 1 vấn đề. 
CMR cũng có ít nhất 3 nhà toán học trao đổi với nhau về cùng một vấn đề (I và II, II và III, III và I).
 Phân tích: Tương tự như 17 điểm được nối với nhau bằng 3 màu à luôn tồn tại một tam giác với 
3 cạnh cùng màu tức là 3 nhà toán học trao đổi với nhau về cùng một vấn đề.
 Lời giải
 Một nhà toán học trao đổi với 16 nhà toán học khác về 3 vấn đề nên theo nguyên lý Dirichlet có 
ít nhất 6 người sẽ được một người trao đổi về cùng một vấn đề, giả sử đó là vấn đề I.
 6 người này lại trao đổi với nhau về 3 vấn đề:
 + TH1: Nếu có 2 người nào đó cùng trao đổi về vấn đề I thì bài toán được chứng minh.
 + TH2: Nếu không có 2 người nào cùng trao đổi về vấn đề 1 thì 6 người này chỉ trao đổi về 2 
vấn đề II và III.
 Một người trao đổi với 5 người còn lại về 2 vấn đề II và III. Theo nguyên lý Dirichlet có ít nhất 
3 người cùng được một người trao đổi về 1 vấn đề, giả sử đó là vấn đề II. Ba người này lại tiếp tục trao 
đổi với nhau:
 + TH1: Nếu có 2 người nào đó cùng trao đổi với nhau về vấn đề II thì bài toán được chứng minh.
 + TH2: Nếu không có 2 người nào cùng trao đổi với nhau về vấn đề II thì cả 3 người này trao 
đổi với nhau về vấn đề III suy bài toán cũng đã được chứng minh.
 Vậy luôn có ít nhất 3 nhà toán học trao đổi với nhau về cùng một vấn đề
DẠNG 2. SỰ SẮP XẾP
Bài 1. Cho một bảng vuông 4 x 4. Trên 16 ô của bảng, ta đặt 16 số tự nhiên từ 1 đến 16. Chứng minh 
rằng tồn tại hai ô kề nhau (tức là hai ô có một cạnh chung ) sao cho hiệu các số ở hai ô đó lớn hơn hoặc 
bằng 3. b) Trên bảng ô vuông kích thước 6 6 ấy ta viết các số tự nhiên từ 1 đến 36, mỗi số viết vào một ô một 
cách tùy ý. Chứng minh rằng luôn tồn tại hai ô vuông chung cạnh mà hiệu các số ghi trong chúng không 
nhỏ hơn 4.
Phân tích: a) Bài toán yêu cầu kết quả liên quan đến tổng nên ta coi các tổng là các con thỏ còn các 
hàng, cột, đường chéo là các lồng.
b) Vì yêu cầu liên quan đến hiệu hai ô cạnh nhau (hiệu 2 số trong hai ô) nên ta coi số các hiệu có thể 
của hai ô cạnh nhau là số thỏ, số các cặp ô cạnh nhau từ ô ghi số 1 đến ô ghi số 36 là các lồng.
 Lời giải
a) Bảng ô vuông kích thước 6 6 có 6 dòng, 6 cột và 2 đường chéo nên sẽ có 14 tổng của các số được 
tính theo dòng, theo cột và theo đường chéo. Mỗi dòng, mỗi cột và đường chéo đều ghi 6 số thuộc tập 
 1;0;1 . Vì vậy giá trị mỗi tổng thuộc tập hợp 6; 5; 4; 3; 2; 1;0;1;2;3;4;5;6 có 13 phần tử. Có 
14 tổng nhận trong tập 13 giá trị khác nhau nên theo nguyên lý Dirichlet tồn tại ít nhất hai tổng có cùng 
một giá trị.
b) Xét hàng có ô ghi số 1 và cột có ô ghi số 36. Hiệu giữa hai số này là 35 (coi như là 35 thỏ). Số cặp ô 
kề nhau từ ô ghi số 1 đến ô ghi số 36 nhiều nhất là 10 (gồm 5 cặp ô chung cạnh tính theo hàng và 5 cặp 
ô chung cạnh tính theo cột) (coi như có 10 lồng). Ta có: 35 10.3 5. 
Vậy theo nguyên lý Dirichlet luôn tồn tại hai ô vuông chung cạnh mà hiệu các số ghi trong chúng không 
nhỏ hơn 4.
Bài 5. Mỗi ô vuông của bảng 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 sao cho bất kỳ hai số nào ghi trong hai ô chung một cạnh hoặc hai ô chung một đỉnh của 
bảng là hai số nguyên tố cùng nhau. Chứng minh rằng có số được ghi ít nhất 17 lần.
 Lời giải
Phân tích đề bài ta tạo ra các con thỏ và các cái lồng như sau: Số các con thỏ chính là các số cách c
Trên mỗi hình vuông con kích thước 2 2 có không quá 1 số chia hết cho 2, không quá 1 số chia hết 
cho 3.
Lát kín bảng bởi 25 hình vuông, kích thước 2 2 , 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 và cũng không chia hết cho 3. Vì 
vậy chúng phải là một trong ba số1;5;7 . Ta có 50 3.16 2 . Từ đó theo nguyên lý Dirichlet có một số 
xuất hiện ít nhất 17 lần.
Bài 6. Có 20 người quyết định đi bơi thuyền bằng 10 chiếc thuyền đôi. Biết rằng nếu hai người A và B 
mà không quen nhau thì tổng số những người quen của A và những người quen của B không nhỏ hơn 
19. Chứng minh rằng có thể phân công vào các thuyền đôi sao cho mỗi thuyền đều là hai người quen 
nhau.
 Lời giải
 Nếu trong 20 người không có hai người nào quen nhau thì tổng số người quen của hai người bất 
kì là 0. Điều này mâu thuẫn với giả thiết là tổng số người quen của hai người không nhỏ hơn 19. Vậy 
tồn tại một số cặp quen nhau.
 Ta xếp mỗi cặp quen nhau đó vào một thuyền đôi. 
 Gọi k là số lượng thuyền lớn nhất mà trong đó ta có thể xếp được những cặp quen nhau vào một 
thuyền và kí hiệu thuyền thứ i xếp hai người Ai và Bi quen nhau (1 i k) . Nhận xét rằng: A; A 1; A 2;...; A 9; A 10
+ 11 số trên thuộc tập S
+ 11 số đó có tổng các chữ số là 11 số tự nhiên liên tiếp vì tổng đó là:
s A ;s A 1;s A 2;...;s A 9;s A 10 , với s A là tổng các chữ số của A.
Trong 11 số tự nhiên liên tiếp luôn tồn tại một số chia hết cho 11.
Do vậy, ta có điều phải chứng minh.
Bài 2. Cho 2021 số tự nhiên bất kì. Chứng minh rằng trong các số đó có một số chia hết cho 2021 hoặc 
một tổng các số trong các số đã cho chia hết cho 2021.
 Lời giải
Gọi 2014 số tự nhiên đã cho là a1;a2 ;...;a2021
Xét dãy S1 a1;S2 a1 a2 ;...;S2021 a1 a2 ... a2021
Chia tất cả các số hạng của dãy cho 2021 ta có các trường hợp sau:
 • Trường hợp 1: Nếu có một số hạng nào của dãy chia hết cho 2021 thì bài toán được chứng minh.
 • Trường hợp 2: Nếu không có số hạng nào của dãy chia hết cho 2021 thì vì có tất cả 2021 phép 
 chia mà số dư chỉ gồm 1, 2, ..., 2020 do đó theo nguyên lý Dirichle có ít nhất hai số hạng của dãy 
 có cùng số dư khi chia cho 2021. Gọi hai số hạng đó là: Si ; S j
 Không mất tính tổng quát, giả sử 1 i j 2021
 Với Si a1 a2 ... ai ;S j a1 a2 ... ai ... a j
 Si S j 2021 ai 1 ... a j 2021
 Từ đó ta có điều phải chứng minh.
Bài 3. Cho 12 số tự nhiên khác nhau có hai chữ số. Chứng minh rằng tồn tại hai số có hiệu là một số 
có hai chữ số như nhau.
 Lời giải
 Có 12số tự nhiên khác nhau, mà chỉ có 11 số dư trong phép chia cho 11, do đó tồn tại hai số có 
cùng số dư trong phép chia cho 11. Hiệu của chúng là một số chia hết cho 11, đó là số có hai chữ số 
như nhau.
Bài 4. Chứng minh rằng trong 11 số tự nhiên bất kì bao giờ cũng tồn tại ít nhất 2 số có hiệu chia hết 
cho10. 
 Lời giải
 Với 11 số tự nhiên khi chia cho 10 ta được 11 số dư, mà một số tự nhiên bất kì khi chia cho 10 
có 10khả năng dư là 0 ; 1 ; 2 ; 3 ; ... ; 9.
 Vì có 11 số dư mà chỉ có 10 khả năng dư, theo nguyên lí Đi-rích-lê, tồn tại ít nhất 2 số khi chia 
cho 10có cùng số dư do đó hiệu của chúng chia hết cho 10 (đpcm).
Bài 5. Chứng minh rằng tồn tại số có dạng 19941994...199400...0 chia hết cho 1995.
 Lời giải
 Xét dãy số có dạng: 1994 ; 19941994 ; ... ; .