Chuyên đề bồi dưỡng HSG - Chuyên đề 19: Nguyên lý Dirichlet - Toán 7

 Chuyên đề 19. NGUYÊN LÝ DIRICHLET
A. Kiến thức cần nhớ
1. Nội dung: Dirichlet (Điriklê) là tên của một nhà toán học người Đức (Pôngutáp Lêgien Điriklê) ông 
sinh năm 1805 và mất năm 1859. Trong quá trình nghiên cứu và giảng dạy toán ở các trường phổ thông 
ông đã đưa ra được một nguyên tắc giải toán rất hữu hiệu và được sử dụng nhiều trong lĩnh vực số học, 
hình học và đại số. Ngày nay người ta thường gọi nguyên tắc này là nguyên tắc Dirichlet hay nguyên lý 
Dirichlet (hay còn gọi là nguyên tắc “nhốt thỏ vào lồng”)
* Cụ thể: Nếu nhốt 7 con thỏ vào 3 cái lồng thì tồn tại ít nhất một lồng có từ 3 con thỏ trở lên. (Hay: 
Không thể nhốt 7 con thỏ vào 3 cái lồng lại không có cái lồng nào nhốt nhiều hơn 2 con thỏ).
* Tổng quát:
a. Nếu ta nhốt n chú thỏ vào n 1 cái lồng thì tồn tại một lồng có từ hai chú thỏ trở lên.
b. Khi nhốt n con thỏ vào k cái lồng:
+ Nếu n kp r 0 r k 1 thì tồn tại ít nhất một lồng chứa không ít hơn p 1 con thỏ.
+ Nếu n kp thì tồn tại ít nhất một lồng chứa không ít hơn p con thỏ và tồn tại ít nhất một lồng chứa 
không nhiều hơn p con thỏ.
2. Chú ý:
+ Nguyên lý Dirichlet thường được sử dụng để giải 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 chỉ ra một cách tường minh sự vật, sự việc đó.
+ Khi giải bài toán vận dụng nguyên lý Dirichlet, điều quan trọng là phải nhận ra (hay tạo ra) các yếu tố 
“thỏ”; “lồng”; “nhốt thỏ vào lồng”. Khi giải diễn đạt theo ngôn ngữ toán học.
+ Nhiều bài toán sau một số bước trung gian mới sử dụng được nguyên lý Dirichlet.
+ Thường kết hợp với phương pháp chứng minh phản chứng.
B. Một số ví dụ
Ví dụ 1: Chứng minh nguyên lý Dirichlet.
 Tìm cách giải: Chứng minh trực tiếp hoặc sử dụng phản chứng.
 Giải
* Chứng minh: Nếu nhốt 7 con thỏ vào 3 cái lồng thì tồn tại ít nhất một lồng có từ 3 con thỏ trở lên. 
(Hay: Không thể nhốt 7 con thỏ vào 3 cái lồng mà lại không có lồng nào nhốt nhiều hơn 2 con thỏ). Thật 
vậy, nếu mỗi lồng chứa không quá 2 con thỏ thì 3 lồng chứa không quá 2.3 6 con thỏ, vô lý. Vậy 
không thể nhốt 7 con thỏ vào 3 cái lồng mà không có lồng nào nhốt nhiều hơn 2 con thỏ.
* Chứng minh tổng quát:
a. Nếu ta nhốt n con thỏ vào n 1 cái lồng thì tồn tại một lồng có từ hai con thỏ trở lên.
Thật vậy giả sử không có lồng nào chứa từ hai con thỏ trở lên thì nhiều nhất mỗi lồng chỉ chứa một con 
thỏ. n 1 cái lồng chứa nhiều nhất n 1 con thỏ. Vô lý.
Vậy nếu ta nhốt n con thỏ vào n 1 cái lồng thì tồn tại một lồng có từ hai con thỏ trở lên. Số hàng: 4; Số cột: 4; Số đường chéo: 2. Như vậy sẽ có 
 10 tổng.
 Các giá trị có thể có khi cộng các số trong mỗi hàng, cột 
 hoặc đường chéo là 
 4a; 3a; 2a; a; 0; a; 2a; 3a; 4a. 
 Có 10 tổng, mỗi tổng nhận 1 trong 9 giá trị mà 
 10 9.1 1. Theo nguyên lý Dirichlet tồn tại hai tổng có 
 giá trị bằng nhau.
Ví dụ 5: Chứng minh rằng: Trong n 1 số tự nhiên bất kỳ a1; a2; ...; an; an 1 luôn tìm được hai số sao 
cho hiệu của chúng chia hết cho n. 
 Tìm cách giải: Trong bài toán “thỏ” là các số tự nhiên bất kỳ, “lồng” là số số dư trong phép chia một số 
cho n . Chia một số bất kỳ cho n có thể nhận được một trong n số dư 0; 1; 2; ...; n 2; n 1. Có n 1 
con thỏ, có n cái lồng
 Giải
Chia một số bất kỳ cho n có thể nhận được một trong n số dư 0; 1; 2; ...; n 2; n 1. Có n 1 số, có n 
số dư. Do đó theo nguyên lý Dirichlet tồn tại hai số có cùng số dư khi chia cho n . Không mất tổng quát 
giả sử hai số đó là ap và aq p;q 1;2;....;n;n 1 và ap aq . Ta có:
ap n.kp r r N;0 r n 1 
aq n.kq r 
Khi đó ap aq n. kp kq n. 
Đây chính là hai số có hiệu của chúng chia hết cho n . Bài toán được chứng minh.
Ví dụ 6: Trong 2016 số tự nhiên bất kỳ a1; a2; ...; a2016 luôn tìm được một số chia hết cho 2016 hoặc hai 
số có hiệu chia hết cho 2016.
 Tìm cách giải: Trong bài toán số “thỏ” là số 2016 số tự nhiên bất kỳ, “Lồng” là số số dư trong phép 
chia một số cho 2016. Có hai khả năng xảy ra: hoặc có số chia hết cho 2016, hoặc tất cả các số đều không 
chia hết cho 2016.
 Giải
Nếu một trong n số chia hết cho 2016, bài toán được chứng minh.
Nếu tất cả 2016 số không có số nào chia hết cho 2016 thì mỗi số khi chia cho 2016 sẽ nhận một trong 
2015 số dư 1; 2; 3; ....; 2014; 2015. 
Có 2016 số mà có 2015 số dư nên tồn tại 2 số có cùng số dư khi chia cho 2016 hiệu của hai số chia 
hết cho 2016. (đpcm).
Ví dụ 7: - Nếu không có lũy thừa nào có tận cùng là 00001 thì số các số có 5 chữ số tận cùng khác nhau kể từ số 
00002; 00003; ...; đến 99998; 99999 nhỏ hơn 105 . Theo nguyên lý Dirichlet tồn tại ít nhất hai lũy thừa 
nào đó có 5 chữ số tận cùng giống nhau. Nếu n chẵn thì số 792k chữ số tận cùng là 1. Giả sử đó là hai số: 
 2k1 
A1 79 B1.10 abcd1. 
 2k2 5
A2 79 B2 .10 abcd1 với A1 A2 . 
 2k 2k 2k 2 k k 5
A A 79 1 79 2 79 2 79 1 2 1 10 B B . 
 1 2 1 2 
 2k 5 2 k k 
Do 79 2 có tận cùng là 1 và 10 B B có tận cùng không ít hơn 5 số 0 nên 79 1 2 1 có tận cùng 
 1 2 
 2 k1 k2 
không ít hơn 5 số 0 suy ra 79 có tận cùng là 00001. Vậy tìm được số k 2 k1 k2 thỏa mãn yêu 
cầu của bài.
 Cách 2. Ta cần chứng minh tồn tại k N sao cho 79k 1 chia hết cho105. 
 5
Xét 105 1 số: 79; 792; 793; 794; ...; 7910 1 . Tất cả các số này đều không chia hết cho 105 nên nếu lấy 
105 1 số này chia cho số 105 thì theo nguyên lý Dirichlet tồn tại hai số có cùng số dư trong phép chia 
cho 105 . Khi đó hiệu của chúng chia hết cho 105 . Giả sử hai số đó là 79m và 79n 
 m,n N; 1 n m 105 1 . 
Ta có 79m 79n 105 hay 79n 79m n 1 105. 
Vì 79n;105 1 nên 79m n 1 105 
Ta chọn m n k lúc đó 79k chia cho 105 dư 1 tức là 79k có chữ số tận cùng là 00001 (đpcm).
Ví dụ 9: Để chuẩn bị cho buổi sinh hoạt câu lạc bộ toán của khối 7 của một trường THCS, 6 bạn học sinh 
giỏi toán của 6 lớp 7A, 7B, 7C, 7D, 7E, 7G viết thư trao đổi với nhau về hai nội dung: (I): “Thống kê” và 
(II): “Biểu thức đại số”. Biết rằng mỗi bạn đều viết thư cho 5 bạn còn lại (trong các bạn nói trên) về một 
trong hai nội dung trên.
Chứng minh rằng có ít nhất 3 bạn cùng trao đổi với nhau về một nội dung.
 Tìm cách giải: Ta gọi 6 học sinh giỏi toán (ta coi là 6 “thỏ”) của 6 lớp lần lượt là A, B, C, D, E, G. Giả 
sử một bạn nào đó A chẳng hạn viết thư cho 5 bạn còn lại về mỗi bạn một trong hai nội dung “Thống kê” 
và “Biểu thức đại số”.
Ta thành lập các “lồng” bằng cách sau đây:
- “Lồng I” nhốt những ai trao đổi với A về nội dung (I).
- “Lồng II” nhốt những ai trao đổi với A về nội dung (II). 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.
19.6. Chứng minh rằng trong 2016 số tự nhiên bất kỳ tồn tại hai số có hiệu chia hết cho 2015.
19.7. Chứng minh rằng trong n số tự nhiên liên tiếp luôn tìm được một số chia hết cho n.
19.8. Trong n số tự nhiên bất kỳ a1; a2; ...; an luôn tìm được một số chia hết cho n hoặc hai số có hiệu 
chia hết cho n.
19.9. Chứng minh rằng trong ba số lẻ bất kỳ bao giờ cũng tìm được hai số có tổng hoặc hiệu chia hết cho 
8.
19.10. Chứng minh rằng luôn tìm được số có dạng
19741974...19740000...0000 chia hết cho 1975.
19.11. Tồn tại hay không một số có dạng 20162016...20162016 chia hết cho 2017.
19.12. Chứng minh rằng trong 20 số tự nhiên liên tiếp bất kỳ ta luôn tìm được một số mà tổng các chữ số 
của nó chia hết cho 10.
19.13.
a) Cho 1001 số nguyên dương khác nhau nhỏ hơn 2000. Chứng minh rằng ta có thể chọn ra 3 số mà một 
số bằng tổng của hai số còn lại.
b) Hãy tổng quát hóa bài toán và chứng minh.
19.14. Chứng minh rằng trong 52 số tự nhiên tùy ý luôn tồn tại hai số sao cho tổng hoặc hiệu của chúng 
chia hết cho 100.
19.15. Có 17 nhà khoa học viết thư cho nhau trao đổi về ba đề tài: “Biến đổi khí hậu”; “Môi trường”; 
“Dân số”. Mỗi người viết thư cho một người về một đề tài. Chứng minh rằng ít nhất cũng có 3 nhà khoa 
học trao đổi với nhau về cùng một đề tài.
(Chú ý: Bài toán trên có thể diễn đạt cách khác theo ngôn ngữ hình học như sau: “Cho 17 điểm phân biệt 
nằm trên một đường tròn.. Hai điểm bất kì trong 17 điểm này đều được nối bằng một đoạn màu xanh, 
màu đỏ hoặc màu vàng. Chứng minh luôn tồn tại ít nhất một tam giác có ba cạnh cùng màu”).
19.16. Cho dãy số 101; 102; 103; 104; ...; 1020 . Chứng minh rằng có một số trong dãy số ấy chia cho 19 thì 
dư 1.
 (Thi chọn học sinh giỏi lớp 9. Quận 10. TP Hồ Chí Minh,
 năm học 2005 – 2006)
19.17. Cho X là một tập hợp gồm 700 số nguyên dương đôi một khác nhau mỗi số không lớn hơn 2006. 
Chứng minh rằng trong tập hợp X luôn tìm được hai phần tử x, y sao cho x y thuộc tập hợp 
E 3;6;9. 
 (Đề thi vào khối THPT Chuyên, Đại học Sư phạm Hà Nội, HƯỚNG DẪN GIẢI – ĐÁP SỐ
19.1. Trừ hai bạn đạt điểm 10 còn lại 10 bạn đạt 7 loại điểm 3; 4; 5; 6; 7; 8; 9. Giả sử trong số đó không 
có ít nhất hai bạn nào có số điểm giống nhau thì mỗi loại điểm chỉ nhiều nhất có một bạn đạt nên tổ còn 
lại nhiều nhất 7 bạn. Vô lý.
19.2. Một năm có 12 tháng. Giả sử trong năm không có một tháng nào có ít nhất 4 học sinh cùng tổ chức 
sinh nhật, thì một tháng nhiều nhất có 3 học sinh tổ chức sinh nhật. Số học sinh của lớp nhiều nhất là 
21.3 36 37 . Vô lý.
19.3. Số trận đấu của mỗi đấu thủ với các đấu thủ khác gồm 8 loại là 0; 1; 2; 3; 4; 5; 6; 7. Các số 0 và 7 
không đồng thời tồn tại vì nếu có 1 ai chưa đấu trận nào thì không ai đấu đủ 7 trận. Nếu đã có một người 
đấu đủ 7 trận thì không ai chưa đấu trận nào. Có 8 đấu thủ, có 7 loại số trận đấu do đó phải tồn tại ít nhất 
hai đấu thủ có số trận đấu như nhau ở mọi thời điểm giữa các cuộc đấu.
19.4. Giả sử trong số 5 người có một người không quen với tất cả những người còn lại thì mỗi người còn 
lại không ai có thể có số người quen quá 3 người. Số người quen chỉ có thể có các loại 0; 1; 2; 3. Có 5 
người (5 thỏ) mà chỉ có 4 loại số người quen (4 lồng). Theo nguyên lý Dirichlet tồn tại ít nhất hai người 
có số người quen như nhau trong 5 người đó.
Giả sử trong số 5 người có một người quen với tất cả những người còn lại thì mỗi người còn lại có số 
người quen chỉ có thể là 1; 2; 3; 4. Có 5 người (5 thỏ) mà chỉ có 4 loại số người quen (4 lồng). Theo 
nguyên lý Dirichlet tồn tại ít nhất hai người có số người quen như nhau trong 5 người đó.
Tổng quát: Một phòng họp có n người, bao giờ cũng có ít nhất 2 người có số người quen như nhau trong 
số n người đó.
19.5.
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.
19.6. Chia một số cho 2015 ta nhận được một trong 2015 số dư: 0; 1; 2; ; 2013; 2014. Có 2016 số tự 
nhiên bất kỳ nên theo nguyên lý Dirichlet tồn tại 2 số có cùng số dư khi chia cho 2015 hiệu của hai số 
chia hết cho 2015.