Chuyên đề HSG Toán đại 6 (Cánh diều) - Chuyên đề 8: Nguyên lí Dirichlet

 S6-CHUYÊN ĐỀ 8. NGUYÊN LÍ DIRICHLET
PHẦN I. TÓM TẮT LÝ THUYẾT
1. Nội dung nguyên lí
Nếu nhốt n.m + r (trong đó m,n,r Î ¥ * ) con thỏ vào n cái chuồng thì phải có ít nhất một chuồng 
chứa không ít hơn m + 1 con thỏ.
Chứng minh
Giả sử ngược lại mỗi chuồng chứa không quá m con thỏ thì tổng số thỏ nhốt trong n chuồng sẽ không 
quá m.n con thỏ :Mâu thuẫn với giả thiết là số thỏ bằng m.n + r .Vậy phải có ít nhất một chuồng chứa 
không ít hơn m + 1 con thỏ.
2. Nhận xét
Bản thân nguyên li Dirichlet khá đơn giản và dễ hiểu, tuy nhiên việc ứng dụng nguyên lí này lại không hề 
đơn giản .Vấn đề ở đây là phát hiện ra “chất Dirichlet “ trong các bài toán , dạng toán của mình và sau đó 
xác định trong đó đâu là chuồng và đâu là thỏ.Có những trường hợp chuồng và thỏ gần như đã có sẵn, 
nhưng có những trường hợp chúng ta phải “xây chuồng , tạo thỏ”.
PHẦN II.CÁC DẠNG BÀI
Dạng 1: Toán chia hết
Khi chia số a cho số m ¹ 0 luôn có m khả năng về số dư là 0,1,.,m - 1 (“m chuồng “).Do vậy, khi 
chia m + 1 số khác nhau a1,a2,.....,am+ 1 cho m ta sẽ có m + 1 số dư (“m + 1 thỏ”) và do đó luôn 
có hai phép chia có cùng số dư.Giả sử hai số bị chia trong hai phép chia đó là ai và aj (với 
1 £ j < i £ m + 1 ). Ta có (ai - aj )Mm .
Bài 1:
Chứng minh rằng có thể tìm được một số có dạng 19781978.....197800...0 chia hết cho 2012.
Lời giải
Xét dãy số : 1978,19781978,.....,11494748414947284.4..414947483. Khi chia các số hạng của dãy này cho 2012 sẽ có 
 2013 so 1978
hai phép chia có cùng số dư. Giả sử hai số hạng của dãy trong hai phép chia đó là a = 11494748414947284.4..414947483 
 m so 1978
và b = 11494748414947284.4..414947483 ( với 1 £ n < m £ 2013) .
 n so 1978
 Hiệu của a và b chia hết cho 2012 hay a - b = 114947484149447284..4.4.1494744830{0...0M2012 (đpcm)
 m- n so 1978 4n so 0
Nhận xét: Phương pháp để giải dạng toán này là tạo ra dãy số (theo cấu tạo số) từ yêu cầu của bài toán 
(“tạo thỏ”) . Sau đó áp dụng nguyên lí Dirichlet cho các số hạng của dãy số mới (mỗi số hạng thay cho 
một “thỏ”, 2012 là số “chuồng”). Do đó tổng các chữ số của mỗi số cũng là một dãy 10 số tự nhiên liên tiếp, vì thế tồn tại số có tổng các 
chữ số chia hết cho 10.
Bài 4:
Cho 12 số tự nhiên khác nhau có hai chữ số. Chứng minh rằng khô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ó 12 số 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 5:
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 cho 10.
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ó 10 khả 
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 10 có 
cùng số dư do đó hiệu của chúng chia hết cho 10 (đpcm).
Bài 6:
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
Ta có 19941994...199400...0 = 19941994...1994 100...0
Xét 1995 số có dạng: 1994 ; 19941994 ; ... ; .
+) Nếu một trong các số trên chia hết cho 1995 thì dễ dàng có điều phải chứng minh.
+) Nếu các số trên đều không chia hết cho 1995 thì khi chia từng số cho 1995 sẽ chỉ có 1994 khả năng dư 
là 1 ; 2 ; 3 ; ... ; 1994.
Vì có 1995 số dư mà chỉ có 1994 khả năng dư, theo nguyên lí Đi-rích-lê tồn tại ít nhất 2 số khi chia cho 
1995 có cùng số dư, hiệu của chúng chia hết cho 1995.
Khi đó 1994...199400...0 chia hết cho 1995 (đpcm).
Bài 7:
Chứng minh rằng tồn tại số tự nhiên k sao cho (1999^k - 1) chia hết cho104.
Lời giải
Xét 104 số có dạng: 1999^1 ; 1999^2 ; ... ; 1999^104.
Lấy tất cả các số trên chia cho 104 sẽ chỉ có 103 khả năng dư là 1 ; 2 ; 3 ; ...; 103 (chú ý: sẽ không có số 
dư 0 vì 1999 và 104 là hai số nguyên tố cùng nhau nên 1999 mũ bao nhiêu cũng không chia hết cho 104)
Mà dãy số trên có 104 số nên sẽ có ít nhất hai số khi chia cho 104 có cùng số dư.
Gọi hai số có cùng số dư khi chia cho 104 là 1999^a và 1999^b (với a > b)
Ta có: 1999^a - 1999^b ⋮ 104 => 1999^b[1999^(a-b) – 1] ⋮ 104 Lời giải
Gọi A là một nhà Toán học nào đó trong 17 nhà Toán học thì A phải trao đổi với 16 người còn lại về 3 
vấn đề khoa học ( kí hiệu là vấn đề I,II,III).
Vì 16 = 3.5 + 1 nên A phải trao đổi với ít nhất 5 + 1 = 6 nhà Toán học khác về cùng một vấn đề ( theo 
nguyên lí Dirichlet) .
Gọi 6 nhà Toán học cùng trao đổi với A về một vấn đề (chẳng hạn là vấn đề 1) là A1,A2,.....,A6 .Ta thấy 
6 nhà Toán học này lại trao đổi với nhau về 3 vấn đề nên có hai khả năng xảy ra:
1) Nếu có 2 nhà Toán học nào đó cùng trao đổi với nhau về vấn đề I thì cùng với A sẽ có 3 nhà Toán học 
cùng trao đổi về vấn đề I.
2) Nếu không có 2 nhà Toán học nào cùng trao đổi với nhau về vấn đề I , thì 6 nhà Toán học này chỉ trao 
đổi với nhau về 2 vấn đề II và III.Theo nguyên lí Dirichlet , có ít nhất 3 nhà Toán học cùng trao đổi với 
nhau về một vấn đề ( II hoặc III).
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 đề .
Nhận xét: Trong ví dụ trên ta đã phải phân chia bài toán thành hai lớp và sử dụng hai lần nguyên lí 
Dirichlet : Lần thứ nhất với 16 thỏ và 3 chuồng ; lần thứ hai với 6 thỏ và 2 chuồng.
Bài 4:
Chứng minh rằng tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2013.
Lời giải
Xét 2014 có dạng 1,11,111,., 1{1...1 . Theo nguyên lý Dirichlet thì tồn tại hai số có cùng số dư khi chia 
 2014sè1
cho 2013. Giả sử hai số đó là a = 1{1...1, b = 1{1...1 với n>k.
 n sè1 k sè1
 k
Khi đó a - b = 1{1...1.10 M2013.
 n- k sè1
 k
Vì (2007,10 ) = 1 nên số c = 1{1...1 chia hết cho 2013
 n - k sè1
Bài 5:
Cho 5 số tự nhiên phân biệt a1 > a2 > a3 > a4 > a5 . Xét tích
P = (a1 - a2)(a1 - a3)(a1 - a4)(a1 - a5)(a2 - a3)(a2 - a4)(a2 - a5)(a3 - a4)(a3 - a5)(a4 - a5)
Chứng minh rằng P M228
Lời giải
Ta có 288 = 32.25
1. Chứng minh P M32 - Nếu không có số hạng nào chia hết cho 100 thì trong 100 số này khi chia cho 100 sẽ có hai số hạng có 
cùng số dư . Hiệu của chúng cho ta tổng cần tìm.
Bài 8:
Cho 69 số tự nhiên khác 0 phân biệt và không vượt quá 100 .Chứng minh rằng có thể chọnđược 4 số trong 
69 số đó thỏa mãn tổng của ba số bằng số còn lại
Lời giải
Giả sử 69 số đã cho là 1 £ a1 + a3 < a1 + a4 < ... < a1 + a69 £ 100. Khi đó a1 £ 32. Xét hai dãy 
sau:
1 < a1 + a3 < a1 + a3 < ... < a1 + a69 £ 132(1)
1 £ a3 - a2 < a4 - a2 < ... < a69 - a2 £ 132(2)
Từ (1) và (2) ta có 134 số hạng có giá trị từ 1 đến 132, suy ra có 2 số bằng nhau mỗi số thuộc một dãy, 
chẳng hạn: a1 + am = an - a2 (với 3 £ m < n £ 69) tức là ta tìm được 4 số a1;a2;an ;am với 
a1 < a2 < am mà a1 + a2 + am = an (đpcm)
Bài 9:
Chứng minh rằng trong 39 số tự nhiên liên tiếp bất kì luôn có ít nhất một số có tổng cácchữ số chia hết 
cho 11.
Lời giải
Giả sử 39 số tự nhiên liên tiếp đó là a1 < a2 < ... < a39 .
Trong 20 số hạng đầu tiên của dãy này sẽ có hai số tận cùng là 0 và có một số (trong hai số này) có chữ số 
đứng trước số tận cùng khác 9. Gọi số này là N.
Xét các số N + 1,N + 2,...,N + 19 thuộc 39 số đã cho. Khi đó:
S(N + i) = S(N ) + i với i = 1,2,...,9 và S(N + 19) = S(N ) + 10.
(kí hiệu S(a) là tổng các chữ số của a).
Trong 11 số tự nhiên liên tiếp S(N ),S(N ) + 1,...,S(N ) + 9,S(N ) + 10 luôn có một số chia hết cho 
11, chẳng hạn: S(N + m)M11 với m Î {1;2;...;9;19}
Vậy N + m là số thỏa mãn.
Bài 10:
Cho 15 số tự nhiên phân biệt, khác 0, không lớn hơn 28. Chứng minh rằng trong 15 số đó luôn tìm được ít 
nhất một bộ 3 số mà số này bằng tổng của hai số còn lại hoặc một cặp 2 số mà số này gấp đôi số kia.
Lời giải
Gọi 15 số tự nhiên sắp xếp theo thứ tự từ nhỏ đến lớn là : a1,a2,...,a15 . Ta hãy tưởng tượng mỗi cây thông là một "thỏ", như vậy có 800.000 "thỏ" được nhốt vào không quá 
 500.000 "chiếc lồng". Lồng 1 ứng với cây thông có 1 chiếc lá trên cây, lồng 2 ứng với cây thông có 2 
 chiếc lá trên cây v.v... Số thỏ lớn hơn số lồng, theo nguyên tắc Điriclê ít nhất có 1 lồng nhốt không ít hơn 
 2 thỏ nghĩa là có ít nhất 2 cây thông có cùng số lá.
 Bài 14:
 Một lớp học có 40 học sinh. Chứng minh rằng có ít nhất 4 học sinh có tháng sinh giống nhau
 Lời giải
 Một năm có 12 tháng. Ta phân chia 40 học sinh vào 12 tháng đó. Nếu mỗi tháng có không quá 3 học sinh 
 được sinh ra thì số học sinh không quá: 3.12 = 36mà 36 < 40: vô lý.
 Vậy tồn tại một tháng có ít nhất 4 học sinh trùng tháng sinh ( trong bài này 40 thỏ là 40 học sinh, 12 lồng 
 là 12 tên tháng).
 Bài 15:
 Cho dãy số gồm 5 số tự nhiên bất kìa1, a2, a3, a4, a5 . Chứng minh rằng tồn tại một số chia hết cho 5 
 hoặc tổng của một số số liên tiếp trong dãy đã cho chia hết cho 5.
 Lời giải
Ta sẽ thành lập dãy số mới gồm 5 số sau đây:
 S1 = a1
 S2 = a1 + a2
 S3 = a1 + a2 + a3
 S4 = a1 + a2 + a3 + a4
 S5 = a1 + a2 + a3 + a4 + a5
 - Nếu một trong cách Si (i = 1, ... 5)chia hết cho 5 thì bài toán đã được chứng minh.
 - Nếu không có số nào chia hết cho 5 thì khi đem chia các số Si cho 5 sẽ được 5 số dư có giá trị từ 1 đến 4.
 Có 5 số dư mà chỉ có 4 giá trị (5 thỏ, 4 lồng). Theo nguyên tắc Điriclê ít nhất phải có 2 số dư có cùng giá 
 trị. Hiệu của chúng chia hết cho 5. Hiệu này chính là tổng các ai liên tiếp nhau hoặc là ai nào đó.
 Bài 16:
 Với 39 số tự nhiên liên tiếp, hỏi rằng ta có thể tìm được một số mà tổng các chữ số của nó chia hết cho 11 
 hay không?
 Lời giải
 Từ 20 số đầu tiên của dãy bao giờ ta cũng có thể tìm được 2 số mà chữ số hàng đơn vị là 0, và trong hai số 
 đó ít nhất phải có một số có chữ số hàng chục khác 9. Giả sử N là số đó, và ta gọi S là tổng các chữ số của 
 N.