NGUYÊN LÝ DIRICHLET VỚI CÁC BÀI TOÁN ĐẠI SỐ HÌNH HỌC

I. Giới thiệu nguyên Tắc Dirichlet:
Nguyên tắc Dirichlet là một định lý có thể chứng minh dễ dàng bằng phản chứng đã được nhà toán học Đức Dirichlet (1805-1859) áp dụng để chứng minh nhiều định lý toán học.
Nguyên tắc Dirichlet thường được phát biểu dưới dạng hình ảnh đơn giản như sau:” Nếu nhốt 9 chú thỏ vào 4 cái chuồng thì phải có một cái chuồng nhốt ít nhất là 3 chú thỏ. Nguyên tắc này còn phát biểu dưới dạng khác:
-Dạng 1: nếu có một ánh xạ từ tập hợp M có n+1 phần tử vào tập hợp N có n phần tử thì ít nhất cũng có hai phần tử của tập hợp M có cùng một ảnh là một phần tử của tập hợp M có cùng một ảnh là một phần tử của tập hợp N qua ánh xạ đó
-Dạng 2: Nếu tập hợp E gồm n phần tử được phân ra thành n tập hợp con đôi một không giao nhau mà N>nk thì có ít nhất một tập hợp con chứa nhiều hơn k phần tử
-Dạng 3: Minh hoạ bằng hình ảnh
Nếu nhốt N chú thỏ vào n chuồng mà N>nk thì có ít nhất một chuồng nhốt nhiều hơn k chú thỏ .
II. Vận dung nguyên lý Dirichlet vào các bài toán đại số:
Bài 1: Chứng minh rằng tồn tại số có dạng 20032003 …. 200300…0 chia hết cho 2002
Hướng dẫn giải
-Xét dãy số gồm 2002 số hạng sau:
2003,2003 …. 2003 2003 ….2003
2002 lần 2003
Chia tất cả các số hạng của dãy cho 2002 có 2002 số dư từ 1 đến 2002 (không thể có số dư 0 vì các số hạng của dãy là các số lẻ). Có 2002 phép chia, nên theo nguyên tắc Dirichlet phải có ít nhất hai số có cùng số dư khi chia cho 2002.
Giả sử hai số đó là am và an (m,n N ); 1<=m n) Thế thì hiệu của hai số này phải chia hết cho 105 (1983m-1)-(1983m-1)chia hết cho 105.
Mà (1983m-1)-(1983n-1)=1983m-1983n=1983n(1983m-n-1).
Nhưng 105và 1983n nguyên tố cùng nhau, do đó phải có 1983m-n-1 chia hết cho 105. Như vậy có số k’=m-n sao cho 1983k –1 chia hết cho 105.
Bài 6: a) CMR trong m số nguyên bất kỳ bao giờ cũng có một số chia hết cho m hoặc tổng của một nhóm các số trong m số đó chia hết cho m.
b) Có hay không một số có dạng 19911991 …. 1991 0000000 chia hết cho 1990
Giải
a) Gọi m số nguyên đã cho là a1, a2, …. , am. Nếu không có số nào chia hết cho m thì ta lập m tổng :
a1
a1+a2
a1+a2+a3
…..
a1+a2+a3+…am
Có tất cả hai trừơng hợp
-Một trong các tổng trên chia hết cho m
-Không có một tổng nào trong các tổng trên chia hết cho m như vậy số dư khi chia mỗi tổng trên cho m là một số từ 1 đến m-1 (Có tất cả m-1 số dư). Ta có m tổng, do đó theo nguyên tắc Dirichlet, phải có hai tổng có cùng số dư (# 0) khi chia cho m. Hiệu của hai tổng này ( là tổng của một số các số đã cho) chia hết cho m .
b) Ta lặp dãy số có dạng:
1991
19911991
199119911991
….
19911991….1991
Chia các số trên đây cho 1990, ta có 1989 số dư khác 0. Theo nguyên tắc Dirichlet phải có ít nhất hai số cho cùng một số dư, hiệu hai số này (là một số có dạng 1991,1991….0000) chia hết cho 1990
Bài 7: Trong 1 lớp học có 30 học sinh. Chứng tỏ rằng trong số học sinh ta sẽ tìm thấy 2 học sinh có tên bắt đầu bằng một chữ cái giống nhau.
Giải
Bảng chữ cái tiếng việt gồm 29 chữ cái , trong lúc đó số học sinh lớn hơn, những 30 em. Ở đây, các chữ cái đóng vai trò các lồng, còn các bạn học sinh đóng vai trò các chú thỏ mà ta phải nhốt vào lồng ,vì số thỏ lớn hơn số lồng nên ta sẽ tìm được ít nhất một lồng nhốt nhiều hơn 1 chú thỏ, tức là tìm được ít nhất 2 học sinh có tên bắt đầu cùng một chữ cái .
Bài 8:Với một lượng tối thiểu là bao nhiêu hs thì ta có thể tìm được một cặp hs có ngày tháng sinh giốâng nhau ?
Giải
Năm thường 366, Năm nhuận 367
Bài 9:Có 25 số tự nhiên có 4 chữ số và đươc lập nên từ các chữ số 1,2,3 và 4. Chứng tỏ rằng ta có thể tìm thấy trong 25 số ấy hai số bằng nhau
Lượng các số khác nhau lập nên là:
1.2.3.4 = 24
Mà số các số cần lập nên là 25 . Vậy theo nguyên tắc Dirichlet thì phải có hai số trùng nhau.
Bài 10 : CMR trong n+1 số tự nhiên thì bao giờ cũng tìm được hai số khi chia hết cho n thì cho cùng một số dư .
Giải
Ta chia mỗi số trong n+1số này cho n, ta được n+1 số dư ,và các số dư này nhận một trong các giá trị 0, 1, 2…, n-1 tức là các số dư nhận không quá n giá trị khác nhau .
Mà ta lại có n+1 số . Vậy phải có hai số ta chia cho n cho ta cùng một số dư .
Bài 11: CMR trong các số tự nhiên 2-1, 22-1, 23-1, …, 2n-1 trong đó n là số lẻ ,lớn hơn 1, có ít nhất một số chia hết cho n
Giải
Giả sử trong các số đã cho có 2 số: 2k-1,2k+l-1, khi chia cho n ,cho ta cùng môt số dư ,tức là hiệu [2k+l-1] – [2k-1] = 2k[2l-1}chia hết cho n. Như vậy thì 2l-1 phải chia hết cho n
Bài 12: Từ 5 số tự nhiên bất kì , hiệu có thể tìm được hai số mà hiệu các bình phương của chúng chia hết cho 7
Giải
-Bình phương của một số tự nhiên khi chia cho 7 thì chỉ cho các số dư 0,1,2 và 4 .Gỉa thiết cho 5 số .Trong 5 bình phương của 5 số này sẽ có hai số mà khi chia cho 7 thì cùng một sồ dư ,nghĩa là hiệu của chúng thì chia hết cho 7.
Bài 13:Cho hai số đa thức cùng 1 biến ,mỗi đa thức là tổng của bốn hạng tử bậc lẻ không vượt quá 15. Liệu có đúng không khi nói rằng trong tích của hai đa thức này ta tìm được hai hạng tử đồng dạng ?
Giải
– Đúng. Tổng số các hạng tử của tích là 4.4=16 hạng tử. Thế mà các số mũ (Bậc của hạng tử) nhận 15 giá trị khác nhau 2; 4; 6; ……….; 30.
Bài 14: Trong một thùng có đựng 105 quả táo, gồm 4 loại . CMR trong số táo ấy, bao giờ ta cũng có thể tìm được ít ra 27 quả táo cùng một loại táo nào đó.
Giải
– Qủa táo đóng vai trò của các chú thỏ .
– Loại táo đóng vai trò các lồng ,chia 105 cho 4,ta có:
105 = 4.26+1
Trường hợp này ta có n=4, k=26.Vì số thỏ lớn hơn n.k nên ta phải tìm được một lồng nhốt nhiều hơn k chú thỏ, tức là tìm được một loại táo có nhiều hơn 26 quả, tức là ít nhất có 27 quả.
Bài 15: Trong 1 chuyến du lịch có hs của 3 lớp tham gia .Người phụ trách không biết rõ ai học ở lớp nào .Vậy cần phải chọn ít nhất bao nhiêu người vào đội trực ban để đảm bảo cho đội này có không ít hơn 3 nguời cuả 1 lớp nào đó ?
ĐS: 7 người.
Bài 16: Trong một thùng có 25 quả cầu trắng ,25 quả cầu đen và 20 quả cầu xanh, 10 quả cầu đỏ (các quả cầu đều như nhau). Các quả cầu được cho ra từ trong bóng tối, không thể phân biệt được màu sắc .Hỏi số quả cầu tối thiểu phải chọn là bao nhiêu để có:
a.Không ít hơn 10 quả cầu có cùng một màu .
b.Không ít hơn mười quả cầu trắng .
Giải
a. 9.4 + 1=37 b. 25 + 20 + 10 + 10 = 65
Bài 17: CMR trong số 82 khối vuông mà mỗi khối được sơn một màu khác nhau hoặc 10 khối có cùng 1 màu sơn.
Giải
+TH 1: Gỉa sử rằng khi sơn các khối vuông ta dùng không ít hơn 10 màu khác nhau. Khi đó ta tìm được 10 khối có màu khác nhau .
+TH 2: Gỉa sử khi sơn ta sử dụng không nhiều hơn 9 màu khác nhau, chia 82 cho 9.
82=9.9 + 1 ở đây n=9; k=9
Theo nguyên tắc Dirichlet mở rộng, ta tìm được 10 khối cùng màu
Bài 18: CMR trong 7 số tự nhiên bất kì ta cũng tìm được 3 số mà tổng của chúng chia hết cho 3.
Giải
Một số tự nhiên khi chia cho 3 thì cho ta các số dư 0, 1 hoặc 2 .Vì 7 = 3.2 + 1 nên tồn tại 3 số mà khi chia cho 3 cho ta cùng một số dư .Tổng 3 số này sẽ chia hết cho 3
Bài 19: CMR trong số 100 số tự nhiên tuỳ ý bao giờ ta cũng chọn được 15 số mà hiệu của 2 số bất kì trong 15 số ấy chia hết cho 4.
Giải
Các số dư trong phép chia cho 7 của các số nhận nhiều nhất là 7 giá trị . Vì 100= 7.14 + 2 nên ta sẽ tìm được 15 số mà khi chia cho 7 thì cho cùng một số dư.
Bài 20: Có 15 đội bóng tham dự giải vô địch quốc gia theo thể thức đấu vòng tròn một lượt. Chứng minh rằng tại bất kì thời điểm nào của giải ta luôn tìm được 2 đội có cùng số trận đấu bằng nhau tại thời điểm đó (có thể là 0 trận ).
Giải
Số lần gặp nhau mà mỗi đội có, có thể nhận 15 giá trị khác nhau : 0; 1; 2; ………..; 14.Trong trường hợp này không thể áp dụng nguyên tắc Dirichlet được vì số đội cũng là 15.
Hai trường hợp 0 trận và 14 trận không thể xảy ra đồng thời vì nếu có một đội nào chưa đấu trận nào thì đồng thời không thể có một đội nào đó đã đấu hết 14 trận, ngược lại nếu có một đội đã đá 14 trận thì không thể có 1 đội chưa đá một trận nào . Vì vậy số lần gặp nhau mà mỗi đội đã thực hiện trong thực tế có thể nhận thêm 14 giá trị từ 0 đến 13 hoặc từ 1 đến 14.Khi đó theo nguyên tắc Dirichlet ta luôn có thể tìm được hai đội có cùng một số trận đấu .
Bài 21: CMR trong số 65 số tự nhiên bất kì bao giờ cũng tìm được 9 số mà tổng của chúng chia hết cho 9.
Giải
-TH 1: Gỉa sử trong số 65 số đã cho ta tìm được 9 số mà số dư của chúng chia hết cho 9 nhận 9 giá trị khác nhau. Khi đó tổng các số này chia hết cho 9 vì tổng các số dư là :
0 + 1 + 2 + ……………. + 8 = 36
-TH 2: Gỉa sử ta không tìm được 9 số như vậy. Khi đó số dư của các phép chia các số này cho 9 sẽ nhận nhiều hơn 8 giá trị khác nhau, vì: 65 = 8.8 + 1. Ở đây số k theo nguyên tắc Dirichlet là 8.Nên ta sẽ có 9 con thỏ cùng chuồng .
Bài 22: CMR tồn tại 1 số tự nhiên, tất cả các chữ số bằng 1, chia hết cho 1993
Giải
-Xét dãy số hữu hạn :
1; 11; 111; …………; 11 …. 1
1994 chữ số 1
Dãy này có 1994 số hạng ,mà ta có thể tìm được hai số hạng của dãy hiệu của chúng chia hết cho 1993 .Ta hí hiệu các số này là :
11…1 và 11…….1
k chữ sô1 k+l chữ số 1
Lấy số lớn trừ cho số nhỏ ,ta được hiệu :
11…1 00…..0
l chữ số 1 k chữ số 0
Chia hết cho 1993. Rõ ràng là các chữ số 0 trong số này có thể bỏ đi .Vậy, số 11…1 chia hết cho 1993 l chữ số
III.Vận dụng nguyên lí Dirichlet vào các bài toán hình học :
Một số bài toán có dạng nguyên tắc Dirichlet :
-Trên đoạn thẳng có độ dài bằng 1, đặt 1 số đoạn thẳng mà tổng độ dài của chúng lớn hơn 1 thì ít nhất có 2 trong các đoạn thẳng đó có 1 điểm chung .
– Trên đường tròn có bán kính bằng 1; đặt một số cung và tổng độ dài của chúng lớn hơn 2 thì ít nhất hai trong các cung đó có cùng một điểm chung .
-Trong một hình có diện tích bằng 1 ,đặt một số hình sao cho tổng diện tích của chúng lớn hơn 1 thì ít nhất 2 trong các hình đó có một điểm chung.
Bài 1: Cho bảng vuông gồm n.n ô vuông .Mỗi ô vuông ghi một trong các số 1; 0,2. CMR không tìm được bảng vuông nào mà tổng các số trên cột , trên hàng , trên đường chéo là các số khác nhau.
Giải
Tổng các số trên cột hoặc trên hàng hoặc trên đường chéo có giá trị nhỏ nhất là 0.n = 0, giá trị lớn nhất là 2.n = 2n
Có 2n + 2 tổng (n cột, n hàng, 2 đường chéo nhận một trong 2n+1 giá trị số nguyên từ 0 đến 2n.Theo nguyên tắc Dirichlet phải có ít nhất 2 tổng có giá trị bằng nhau.
Bài 2: Trong một hình tròn diện tích S ta thấy 1995 điểm bất kì . Chứng minh rằng ít nhất có 3 điểm tạo thành một tam giác có diện tích nhỏ hơn S/997.
Giải
Chia hình tròn thành 997 hình quạt bằng nhau .Theo nguyên tắc Dirichlet thì ít nhất có một phần chứa 3 điểm .Ba điểm này tạo thành một tam giác có diện tích nhỏ S/997
Bài3: Trong mặt phẳng cho 1995 điểm và trong ba điểm bất kì bao giờ cũng tìm được 2 điểm có khoảng cách giữa chúng nhỏ hơn một. CMR tồn tại 1 hình tròn có bán kính bằng 1 chứa không ít hơn 998 điểm đó .
Giải
Gọi A là một trong các điểm đã cho .Vẽ đường tròn (A;1) .Nếu các điểm còn lại nằm trong hình tròn (A;1) thì bài toán giải xong. Xét điểm B nằm ngoài hình tròn (A;1) tức AB lớn hơn 1. Vẽ hình tròn (B;1) rõ ràng các điểm còn lại nằm trong hai đường tròn này .
Thật vậy, giả sử có C không thuộc 1 trong 2 hình tròn này.
Tam giác ABC có AB>1, AC>1, BC>1 (Mâu thuẫn giả thiết )
Hai hình tròn này chứa 1995 điểm nên theo nguyên tắc Dirichlet có 1 hình tròn chứa không ít hơn 998 điểm có (Đpcm )
Bài 4: Trong hình chữ nhật 3.4 đặt 6 điểm. CMR trong các điểm này tìm được hai điểm mà khoảng cách giữa chúng không lớn hơn
Giải
Chia hình chữ nhật thành 5 hình giống nhau .Theo nguyên tắc Dirichlet một trong các hình này chứa ít nhất 2 điểm mà khoảng cách giữa 2 điểm bất kì của 1 hình không lớn hơn
Bài 4: Trong 1 hình vuông cạnh 5 cm ,có 126 điểm .CMR trong các điểm ấy ,có 6 điểm nằm trong 1 đường tròn có bán kính 1 cm
Giải
Chia hình vuông đã cho thành 25 hình vuông nhỏ ,cạnh 1 cm và chứng minh rằng trong 1 hình vuông có thể được chứa trong 1 hình tròn bán kính 1 cm
Ta lại có :
126 = 5.25 + 1
Bài 5: Cho 2005 điểm trên mặt phẳng ,biết rằng trong mỗi nhóm 3 điểm bất kì của các điểm trên bao giờ cũng có thể chọn ra được 2 điểm có khoảng cách bé hơn 1. CMR trong các điểm trên có ít nhất 1003 điểm nằm trong 1 đường tròn có bán kính bằng 1.
Giải
Ta có 2005 = 2.1002 + 1
Gọi A là 1 điểm trong 2005 điểm đã cho. Vẽ đường tròn tâm A bán kính 1. Nếu tất cả 2004 điểm còn lại đều nằm trong hình tròn tâm A bán kính 1 thì bài toán được giải.
Gỉa sử có điểm B nằm ngoài đường tròn (A;1) tức là AB>1. Vẽ đường tròn tâm B bán kính 1 ,kí hiệu (B;1). Ta chứng ming tất cả 2005 điểm đã cho đều nằm trong (A;1) hoặc (B;1).
Thật vậy, lấy C bất kì, xếp 3 điểm A,B,C theo giả thuyết AB>1 nên AC<1 hoặc AB<1, khi đó C nằm trong đường tròn (A;1) hoặc C nằm trong (B;1 ) 2005 điểm nằm trong hai đường tròn nên theo nguyên tắc Dirichlet có 1 đường tròn chứa ít nhất 1003 điểm . Bài 6: Cho 6 điểm trong mặt phẳng sao cho bất kì 3 điểm nào cũng là đỉnh của 1 tam giác có các cạnh chiều dài khác nhau. CMR tồn tại 1 cạnh là cạnh nhỏ nhất của 1 tam giác, vừa là canh lớn nhất của 1 tam giác khác. Giải Tô màu đỏ cạnh nhỏ nhất của tam gíac và tô màu xanh hai cạnh kia. Ta chứng minh tồn tại 1 tam giác có các cạnh cùng màu đỏ. Từ điểm A trong 6 điểm đã cho, nối với 5 điểm còn lại,ta được 5 cạnh trong 5 cạnh này ít nhất có 3 cạnh cùng màu, giả sử là hai cạnh AB, AC, AD. Nếu AB,AC,AD cùng màu đỏ:tamgiác BCD có các cạnh cùng màu đỏ , giả sử đó là BC. Khi đó ta có tam giác ABC có các canh cùng màu đỏ. Nếu AB, AC, AD cùng màu xanh thì tam giác BCD có các cạnh cùng màu đỏ với tam giác có ba cạnh cùng màu đỏ thì canh lớn nhất của tam giác này là cạnh cần tìm. Bài 7: Trong hình vuông mà độ dài mỗi cạnh bằng 4 có cho trước 33n điểm trong đó không có 3 điểm nào thẳng hàng. Người ta vẽ các đường tròn có bán kính đều bằng có tâm là các điểm đã cho. Hỏi có hay không 3 điểm trong số các điểm nói trên sao cho chúng đều thuộc vào phần chung của 3 hình tròn có các tâm cũng chính là 3 điểm đó . Giải -Chia hình vuông đã cho thành 16 hình vuông có cạnh là 1 -Do đó 33 điểm được chứa trong 16 hình vuông nên theo nguyên tắc Dirichlet, ít nhất có một hình vuông chứa không ít hơn 3 điểm (33 = 2.16+1 ) Khoảng cách giữa 2 điểm bất kì trong hình vuông chứa không vượt quá đường chéo cuả nó, nghĩa là không lớn hơn . Gọi O1,O2,O3 là 3 điểm cùng nằm trong 1 hình vuông đơn vị nào đó , có thể rơi vào canh hình vuông. Vẽ 3 đường tròn tâm O1, O2, O3 bán kính ,chắc chắn 3 điểm O1, O2, O3 đều nằm trong cả 3 đường tròn này, nghĩa lànằm trong phần chung của 3 hình tròn có tâm cũng chính là các điểm O1, O2, O3.