Nguyên lý Dirichlet

I.Định nghĩa:

Nguyên lý Đirichlê còn gọi là "nguyên tắc nhốt thỏ vào lồng " hoặc "nguyên tắc xếp đồ vật vào ngăn kéo" hoặc nguyên tắc lổ chuồng câu". Nội dung của nguyên lý này hết sức đơn giản và dễ hiểu, nhưng lại có tác dụng rất lớn trong giải toán. Nhiều khi có những bài toán, người ta đã dùng rất nhiều phương pháp toán học để giải mà vẫn chưa đi đến kết quả, nhưng nhờ nguyên lý Đirichlê mà bài toán trở nên dễ dàng giải quyết.
Nguyên tắc Đirichlê được phát biểu dưới dạng bài toán sau đây:
1. Nếu đem nhốt m con thỏ vào n chiếc lồng, với m>n (nghĩa là số thỏ nhiều hơn số lồng) thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ.
Hoặc là:
2. Nếu đem xếp m đồ vật vào n ô ngăn kéo, với m>n (nghĩa là số đồ vật nhiều hơn số ngăn kéo), thì ít nhất cũng phải có một ô ngăn kéo chứa không ít hơn 2 đồ vật.
Chứng minh (dùng phương pháp phản chứng):
Giả sử không có lồng nào nhốt từ 2 thỏ trở nên, thế thì cho dù mỗi lồng đều có nhốt một thỏ thì tổng số thỏ bị nhốt cũng chỉ là n thỏ, trong khi đó tổng số thỏ là m. Điều này vô lý. Vậy ít nhất cũng phải có 1 lồng nhốt từ 2 thỏ trở nên.(đpcm)
Nguyên lí Dirichlet là một định lí về tập hợp hữu hạn.Phát biểu chính xác nguyên lí này như sau
Cho A vàB là 2 tập không rỗng có số phần tử hữu hạn mà số phần tử ở A lớn hơn số lượng phần tử của B ,Nếu với quy tắc nào đấy, mỗi phần tử của A tương ứng với 1 phần tử của B thì tồn tại 2 phần tử khác nhau của A mà chúng tương ứng với cùng 1 phần tử của B

II)Mở rộng nguyên lí Dirichlet

Cho A là tập hữu hạn những phần tử , Kí hiệu s(A) là số lượng các phần tử thuộc A.Nguyên lý Dirichlet có thể phát biểu như sau
Nếu A và B là những tập hợp hữu hạn và s(A) > ks(B) ở đây k là 1 số tự nhiên nào đó và nếu mỗi phần tử của A cho tương ứng với 1 phần tử nào đó của B thì tồn tại ít nhất k+1 phần tử của A mà chúng tương ứng với cùng một phần tử của B

III. Các ví dụ:
A.Các bài toán số học:
1. Toán suy luận:

Ví dụ 1: Có 10 đội bóng thi đấu với nhau mỗi đội phải đấu một trận với các đội khác. CMR vào bất cứ lúc nào cũng có hai đội đã đấu số trận như nhau.

Giải: Rõ ràng nếu trong 10 đội bóng có 1 đội chưa đấu một trận nào thì trong các đội còn lại không có đội nào đã thi đấu 9 trận như vậy 10 đội chỉ có số trận đấu hoặc từ 0 đến 8 hoặc từ 1 đến 9. Vậy theo nguyên lý Đirichlê phải có ít nhất 2 đội có số trận đấu như nhau.

Ví dụ 2: Có 6 đội bóng thi đấu với nhau (mỗi đội phải đấu 1 trận với 5 đội khác). CMR vào 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.
Giải: Giả sử 6 đội bóng đó là A,B,C,D,E,F. Xét đội A.
Theo nguyên lý Đirichlê 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.

Ví dụ 3: CMR trong n người bất kì, tồn tại hai người có số người quen như nhau (kể cả trường hợp quen 0 người)
Giải: Tương tự ví dụ 1, ta xét n nhóm...

Ví dụ 4: Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2, chỉ có 2 học sinh được điểm 10. CMR í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)
Giải: Có 43 học sinh phân chia vào 8 loại điểm (từ 2 đến 9). Giả sử mỗi loại trong 8 loại điểm đều là điểm của không quá 5 học sinh thì lớp học có không quá 5.8=40 học sinh, ít hơn 43 học sinh. Vậy tồn tại 6 học sinh có điểm kiểm tra bằng nhau.

2.Sự chia hết:

Trong các phép tính trên số nguyên thì phép chia là rất đặc biệt.Phép chia có hàng loạt các tính chất mà các phép còn lại không có. Ví dụ các phép toán cộng , trừ , nhân đều thực hiện với số 0 còn phép chia thì không thể.Vì những lí do đặc biệt đó mà trong toán học xây dựng hẳn 1 lý thuyết về phép vchia . Những ví dụ sau có liên quan mật thiết giữa phép chia và nguyên lý Dirchlet
Ví dụ 1: CMR tồn tại một số tự nhiên gồm toàn chữ số 1 chia hết cho 2007.
Giải: Xét 2008 số có dạng 1,11,...,11...11. Theo nguyên tắc Đirichlê thì tồn tại hai số có cùng số dư khi chia cho 2007. Giả sử hai số đó là:
A={11...1}_{n} và B={11...1}_{k} với k<n.
Khi đó A-B={11...1}_{n-k}.10^k chia hết cho 2007
Do (2007, 10^k)=1 nên C={11...1}_{n-k} chia hết cho 2007.

Ví dụ 2: CMR trong n+1 số bất kì thuộc tập hợp \{1,2,3,...,2n\} luôn chọn được hai số mà số này là bội của số kia.
Giải: Viết n+1 số đã cho dưới dạng:
a_1=2^{k_1}b_1, a_2=2^{k_2}b_2,..., a_{n+1}=2^{k_{n+1}}b_{n+1}
Trong đó b_1,b_2,...,b_{n+1} là các số lẻ. Ta có: 1<= b_1, b_2,...,b_{n+1}<= 2n-1. Mặt khác trong khoảng từ 1 đến 2n-1 có đúng n số lẻ nên tồn tại hai số m<= n sao cho b_n=b_m. Khi đó, trong hai số a_n và a_m có một số là bội của số kia.

Ví dụ 3: Cho 5 số nguyên phân biệt a_i (i=1,2,3,4,5). Xét tích:
P=(a_1-a_2)(a_1-a_3)(a_1-a_4)(a_1-a_5)(a_2-a_3)(a_2-a_4)(a_2-a_5)(a_3-a_4)(a_3-a_5)(a_4-a_5).
CMR P chia hết cho 288
Giải: 288=3^2.2^5
-Chứng minh P chia hết cho 9.
Xét 4 số a_1,a_2,a_3,a_4 tồn tại 2 số có cùng số dư khi chia cho 3. Giả sử a_1 đồng dư a_2 (mod 3) thì a_1-a_2 chia hết cho 3.Lại xét a_2,a_3,a_4,a_5 trong 4 số này lại tồn tại 2 số có cùng số dư khi chia cho 3. Suy ra P chia hết cho 9.
-Chứng minh P chia hết cho 2^5
Trong 5 số đã cho có 3 số cùng tính chẵn lẻ.
-Nếu có 4 số chẵn, chẳng hạn a_1=2k_1, a_2=2k_2, a_3=2k_3, a_4=2k_4 thì :
P=32(k_1-k_2)(k_1-k_3)(k_1-k_4)(a_1-a_5)(k_2-k_4)(k_2-k_3)(a_2-a_5)(a_3-a_4)(a_3-a_5)(a_4-a_5) chia hết cho 32.
-Nếu có 3 số chẵn, 2 số lẻ thì đặt:
a_1=2k_1, a_2=2k_2, a_3=2k_3, a_4=2k_4+1, a_5=2k_5+1
Ta có P=16(k_1-k_2)(k_1-k_3)(k_2-k_3).M
Trong 3 số k_1,k_2,k_3 có 2 số cùng tính chẵn lẻ. Giả sử k_1 đồng dư k_1 (mod 2) thì k_1-k_2 chia hết cho 2 nên P chia hết cho 32.
-Nếu có 3 số lẻ là a_1,a_2,a_3 còn a_4,a_5 chẵn thì đặt a_1=2k_1+1, a_2=2k_2+1, a_3=2k_3+1, a_4=2k_4, a_5=2k_5
Xét tương tự cũng có P chia hết cho 32.
Vậy ta có P chia hết cho 288.

3. Toán về tổng, hiệu, chữ số tận cùng...các loại:

Ví dụ 1: Cho 51 số nguyên dương khác nhau có 1 chữ số và có 2 chữ số. CMR ta có thể chọn ra 6 số nào đó mà bất cứ 2 số nào trong số đã lấy ra ấy không có chữ số hàng đơn vị giống nhau cũng không có chữ số hàng chục giống nhau.
Giải:
Vì có 51 số nên tìm được 6 chục sao cho một nhóm có không ít hơn 6 số rơi vào một trong các số chục đó, một nhóm có không ít hơn 5 số rơi vào chục khác... Cuối cùng có ít nhất một trong các số đã cho rơi vào một chục nào đó (như vậy số các chục khác nhau không ít hơn 6) về các số đã cho là khác nhau (chú ý các số dạng xét nhiều nhất có 2 chữ số ) do đó ở nhóm cuối cùng ta lấy một số , sau đó nhóm trước đó (vì có ít nhất 2 chữ số hàng đơn vị của hai số trong nhóm ấy khác nhau) ta lấy một số khác với chữ số hàng đơn vị khác số chọn trước, rồi nhóm trước đó lại lấy 1 số có chữ số hàng đơn vị khác 2 số chọn trước... Cuối cùng sẽ được 6 số phải tìm với các chữ số khác nhau.

Ví dụ 2: Chọn bất kì n+1 số trong 2n số tự nhiên từ 1 đến 2n (n>=2). CMR trong các số được chọn có ít nhất 1 số bằng tổng của 2 số được chọn (kể cả các trường hợp 2 số hạng của tổng bằng nhau ).

Giải:Giả sử a_1<a_2<...<a_n<a_{n+1} là n+1 số được chọn.
Xét n số: a_{n+1}-a_1=b_1
a_{n+1}-a_2=b_2
........................ (mỗi hiệu đều nhỏ hơn 2n)
a_{n+1}-a_n=b_n
Trong tập 2n+1 số đó là a_1,a_2,...,a_{n+1}, b_1,b_2,...,b_n tồn tại 2 số bằng nhau, hai số ấy không thể cùng thuộc dãy a_1,a_2,...,a_{n+1} cũng không thể cùng thuộc dãy b_1,b_2,...,b_n . Ta có:
a_{n+1}-a_1=a_i suy ra a_{n+1}=a_1+a_i (đpcm)