Bài toán về nguyên tắc đi ri klê

Đặt vấn đề Có một thực tế mà bất cứ người nào đã từng cắp sách đến trừơng , đã từng tham dự các kì thi chuyển cấp , thi tuyển sinh , thi học sinh giỏi đều nhận thấy : Nếu chỉ thuộc lòng kiến thức trong sách giáo khoa không thôi thì chưa đủ vẫn không giải quyết được các bài toán trong các kì thi . Đặc biệt là các đề thi học sinh giỏi .Sỡ dĩ như vậy vì trong các đề thi toán đòi hỏi sự vận dụng linh hoạt các kiến thức đã học , uyển chuyển trong phương pháp giải học sinh phải được rèn luyện nhiều dạng toán khác nhau . Do vậy việc bồi dưỡng học sinh giỏi là một trong những mục tiêu quan trọng của nghành giáo dục. Là mũi nhọn trong phong trào thi đua học tốt dạy tốt . Bồi dưỡng học sinh giỏi trong các trường nhằm nâng cao kỹ năng giải toán cho học sinh phát triển tư duy lô rich và tư duy trìu tựơng cho học sinh . Bồi dưỡng học sinh giỏi, giúp học sinh đào sâu kiến thức, phát triển từng bước năng lực tư duy linh hoạt và sáng tạo đồng thời nhằm trang bị kiến thức cơ bản đào sâu tạo nền tảng tin cậy để các em học tiếp các lớp trên và rèn luyện tinh thần tự học . Song tài liệu dành cho học sinh tham khảo thì phong phú đa dạng do vậy giáo viên phải biết phân chia kiến thức phù hợp với đối tượng học sinh, phải biết chọn lọc và hệ thống kiến thức tối thiểu cho từng lớp. Xuất phát từ tình hình trên tôi đã tập hợp một số bài toán về nguyên tắc Đi ri k lê ở dạng đơn giản để bồi dưỡng học sinh giỏi, tôi cũng coi đây là sáng kién kinh nghiệm của bản thân mình trong việc bồi dưỡng học sinh giỏi . *Các bài toán ứng dụng nguyên tắc Đi ri klê 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 đó . *Nhiều bài toán nguyên tắc Đi ri klê 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 *Để giải bài toán ứng dụng nguyên tắc Đi ri kllê nhiều khi ta phải kết hợp phương pháp chứng minh phản chứng *Khi giải các bài toán mà ta biết phải áp dụng nguyên tắc Đi ri klê hoặc dự đoán phải sử dụng phương pháp này chúng ta cần biến đổi để xuất hiện khái niệm “thỏ” “ lồng” *Cũng có những bài toán phải sử dụng 2 lần nguyên tắc Đi ri klê *Khi giải song các bài toán áp dụng nguyên tắc Đi ri klê cần sáng tạo các bài toán tổng quát và cụ thể hơn để nắm vững kiến thức. Tôi cũng coi đây là sáng kiến trong việc bồi dưỡng học sinh giỏi của bản thân có điều chi khiếm khuyết mong bạn bè cùng đồng nghiệp thông cảm. Tôi xin cảm ơn. II Vài bài toán về nguyên tắc Đi ri klê Bài 1 : Cho 100 số tự nhiên chứng minh rằng có thể tìm được một số hoặc tổng một số số chia hết cho 100 Bài giải: Gọi 100 số đó là a1 , a2 ,a3 … a100 ta thiết lập 100 tổng sau S1 = a1 S2 = a1 +a2 S3 =a1 +a2 +a 3 …. S100 = a1 +a2 +a3 +…a100 Nếu 1 trong 100 tổng trên chia hết cho 100 thì đó là điều phải chứng minh Nếu không có tổng nào chia hế cho 100 thì chia 100 tổng trên cho 100 ta có 100 phép chia nên có 100 số dư nhưng chỉ có 99 giá trị dư là 1 , 2 , 3 , … 99. Theo nguyên tắc đia ric lê thì có 2 tổng chia cho 100 cùng số dư có nghĩa là hiệu của 2 tổng đó chia hết cho 100 Tức là tổng một số số chia hết cho 100 (ĐPCM) Bài 2 : Chứng minh rằng tồn tại số có dạng 19941994…1994 1993 Bài giải : Xét dãy số (gồm 1993 số) a1 =1994 a2=19941994 a3 =199419941994 ………………….. a1993 =19941994…1994 (1994 số 1994 ) Chia 1993 số này cho 1993. Nếu có một số nào đó chia hết cho 1993 thì đó là điều phải chứng minh. Nếu không có số nào chia hết cho 1993 thì 1993 phép chia trên có 1993 số dư nhưng chỉ có 1992 giá trị dư đó là: 1, 2, 3, …, 1992. Theo nguyên tắc Đia- ric- lê có 2 số chia cho 1993 cùng số dư. Gọi 2 số đó là ai = 19941994…1994 (i số 1994) aj = 19941994…1994 (j số 1994) (1 i j 1994) Ta có ai – aj 1993 19941994… 1994000…000 1993 19941994…1994 . 104i 1993 Mà ( 1993 , 104i ) =1 vậy 19941994…1994 1993 Chú ý : Có i - j số 1994 và có 4i chữ số 0 Bài 3 : Chứng minh rằng trong 5 số tự nhiên bât kì tồn tại một số hoặc tổng một số số có tổng chia hết cho 5. Bài giải : Gọi 5 số đó là a1 , a2 ,a3 , a4 ,a . Ta thiết lập 5 tổng sau : S1 = a1 S2 = a1 + a2 S3 = a1 +a2 + a3 ……………….(cách làm tương tự bài 1 ) Bài 4: Chứng minh rằng tồn tại n N sao cho: 3n -1 106 Hoặc: Chứng minh rằng tồn tại số tự nhiên n sao cho 3n có tận cùng là 000001 Bài giải: Xét dãy số : ( 1000000 số) a1 = 3 a2 = 32 a3 = 33 …….. a1000000 = Chia 1000000 số này cho 106 có 1000000 phép chia nên có 1000000 số dư nhưng chỉ có 99999 giá trị đó là 1, 2 ,3 , 4 …, 99999 . Theo nguyên tắc Đia- ric- klê có 2 số chia cho 106 cùng số dư . Gọi 2 số đó là 3i và 3j . Ta có 3i – 3j 106 3j( 3i-j -1) 106 Mà ( 3, 10 ) =1 ( 3j , 106) = 1 3i-j - 1 106 , do vậy tồn tại 3n -1 106 Hay 3n có tận cùng là 000001 Bài 5 : Chứng minh rằng tồn tại số tự nhiên x < 17 sao cho 25x - 1 17 Bài giải: Xét dãy số gồm 17 số hạng sau : 25 , 252 , 253 .,… 2517 . Vì (25,17) = 1 nên (25n , 17) = 1 (n 1). Chia 25 số trên cho 17 do không có số nào chia hết cho 17 nên có 17 số dư nhưng chỉ có 16 giá trị là : 1 , 2 , 3, 4 ,…, 16. Theo nguyên tắc Đia ric klê có 2 số chia cho 17 cùng số dư Gọi 2 số đó la 25i và 25j ta có 25i -25j 17 25j (25i-j -1) 17 mà (25j , 17) = 1 Nên 25i-j – 1 17 .Điều đó chứng tỏ tồn tại số tự nhiên x sao cho 25x -1 17 Bài 6 : P là số nguyên tố lớn hơn 5. Chứng minh rằng tồn tại số viết bởi chỉ toàn bộ chữ số 1 mà số đó chia hết cho p Bài giải: Xét p số a1 = 1 a2 = 11 a3 = 111 …………. Ap =111…1 (p chữ số) Giả sử không có số nào chi hết cho p thì chia p số này cho p có p số dư nhưng chỉ có p – 1 giá trị : 1 , 2 , 3 … p-1. Theo nguyên tắc Đia ric klê có 2 số chia cho p cùng số dư có nghĩa là 111…1000…0 chia hết cho p mà 111…1000…0111…1 . 10n mà (p , 10n) = 1 nên 111…1 p (ĐPCM) Bài 7: Lớp 6A có 37 học sinh. Chứng tỏ rằng có ít nhất 4 bạn sinh trong cùng một tháng Bài giải Thật vậy: 1 năm có 12 tháng. Chia 37 học sinh làm 3 nhóm, mỗi nhóm 12 học sinh, như vậy còn dư 1 học sinh. Trường hợp không may mắn xảy ra: - 12 HS trong nhóm thứ nhất có tháng sinh khác nhau: em sinh tháng 1, tháng 2, … - 12 HS trong nhóm thứ 2 có tháng sinh khác nhau: em sinh tháng 1, tháng 2, … - 12 HS trong nhóm thứ 3 có tháng sinh khác nhau: em sinh tháng 1, tháng 2, … Còn lại 1 HS hoặc sinh tháng 1, hoặc sinh tháng 2,…… Điều đó chứng tỏ rằng có ít nhất có 4 bạn sinh trong cùng một tháng. Bài 8 : Có tồn tại hay không số có dạng 3131…31000…000 chia hết cho 32? Bài giải Xét dãy số (gồm 32 số) a1 =31 a2 = 3131 a3 = 313131 ……………… A32 3131…31 (32 số 31 ) Vì dãy trên là các số lẽ nên không chia hết cho 32. Chia 32 số trên cho 32 ta có 32 phép chia nhưng chỉ có 31 giá trị dư đó là : 0 , 1, 2 ,3 …., 31. Theo nguyên tắc Đi- ric klê có 2 số chia cho 32 cùng số dư Gọi 2 số đó là ai và aj (1 j i 32 ) Ta có ai – aj 32 . Hay số có dạng: 3131…31000..000 32 Bài 9 : Có 17 nhà toán học viết thư cho nhau trao đổi về 3 vấn đề khoa học mỗi người viết thư cho một người khác về một vấn đề .Chứng minh rằng ít nhất cũng có 3 nhà toán học trao đổi với nhau về cùng một vấn đề. Bài giải: Gọi A là một nhà toán học nào đó trong 17 nhà toán học thì nhà toán học A phải trao đổi với 16 nhà toán học còn lại về 3 vấn đề. Như vậy nhà toán học được trao đổi ít nhất với 16 nhà toán học còn lại về cùng một vấn đề nào đó. Nên số nhà toán học được trao đổi với A ít hơn 16 . Gọi số nhà toán học cùng trao đổi với nhà toán học A vấn đề (I) nào đó là A1 , A2 , A3 , A4 , A5 , A6 như vậy 6 nhà toán học trao đổi với nhau 3 vấn đề (không kể trao đổi với A) Như vậy 6 nhà toán học phải trao đổi với nhau 3 vấn đề đó là ( I , II , III) có 2 khả năng sảy ra : *Nếu có 2 nhà toán học nào đó cùng trao đổi với nhau về vấn đề I thì có 3 nhà toán (kể cả A) trao đổi với nhau về vấn đề I (bài toán được chứng minh song) *Nếu không có nhà toán học nào trong 6 nhà toán học trên trao đổi về vấn đề I Thì 6 nhà toán học trên trao đổi với nhau về vấn đề II và III .Như vậy theo nguyên tắc Đi ric kllê 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 (bài toán cũng đã được chứng minh) Bài 10 : Chứng minh rằng trong 19 số tự nhiên bât kì ta luôn luôn tìm được một số có tổng các chữ số của nó chia hết cho 10 Bài giải: Thật vậy trong dãy số tự nhiên liên tiếp bao giờ cũng tồn tại một số chia hết cho 100. Với 19 số tự nhiên bất kì luôn tồn tại 10 số liên tiếp có chữ số hàng chục khác nhau còn các chữ số hàng đơn vị từ 0 đến 9. Vì vậy tổng các chữ số của 10 số này cũng làm thành dãy số gồm 10 số tự nhiên liên tiếp. Do đó tồn tại một số chia hết cho 10 (ĐPCM) Bài 11 : Chứng minh rằng trong hệ cơ số 10 ta có thể tìm đựơc bội số của 1995 mà trong đó các chữ số của nó chỉ gồm chữ số 0 và1 Bài giải : Ta thành lập các dãy số sau : A1 = 1 A2 = 11 A3 = 111 A4 = 1111 …………. A1995= 111…1 (1995 chữ số 1) Vì các số trên có tận cùng là 1 nên không có số nào chia hết cho 1995. Chia cả 1995 só trên cho 1995 có 1995 phép chia nên có 1995 số dư nhưng chỉ có 1994 giá trị đó là : 1 , 2 , 3 , 4 … , 1994. Theo nguyên tắc Đi ri klê thì có 2 số chia cho 1995 cùng số dư . gọi 2 số đó là Ai và Aj thì Ai – Aj 1995 Hiệu của 2 số đó chính là số có dạng 111…1000…0 (ĐPCM) Bài 12 : Chứng minh rằng trong 52 số tự nhiên bất kì chí ít cũng có một cặp số gồm hai số sao cho tổng hoặc hiệu của chúng chia hết cho 100. Bài giải: Trong tập hợp các số dư trong phép chia cho 100 ta lấy ra từng cặp số sao cho tổng các cặp đó bằng 100 và thành lập các nhóm như sau : ( 0 , 0) ; ( 1 , 99) ; ( 2 , 98) ; ( 3 , 97) … ( 50 , 50) Như vậy có tất cả 51 cặp . Đem chia 52 số tự nhiên đó cho 100 sẽ có 52 số dư nhưng chỉ có 51 giá trị . Theo nguyên tắc Đi ri klê có 2 số dư cùng rơi vào một nhóm nên cặp số tự nhiên ứng với cặp số dư này chính là hai số tự nhiên có tổng hoặc hiệu chia hết cho 100.(ĐPCM) Bài 13 : Trong 39 số t nhiên liên tiếp . Hỏi rằng ta có thể tìm được một số mà tổn các chữ số của nó chia hết cho 11 không ? (cách làm tương tự) Bài 14 : Chứng minh rằng nếu 3 số a , a+k , a+ 2k đều là các số nguyên tố lớn hơn 3 thì k 6 Bài giải : Vì cả 3 số trên đều là các số nguyên tố lớn hơn 3 nên cả 3 số đều là số lẻ. Vì a lẻ nên k là số chẳn. Mặt khác chúng là các số nguyên tố lớn hơn 3 nên có dạng 6k + 1 hoặc 6k + 5.Theo nguyên tắc Đia ric lê thì có hai số có cùng một dạng .Do đó (a+2k) –(a +k) hoặc (a+ k) –a = k = (6k + 1) – (6q + 1) = 6k – 6q 6 .Vậy k 6 (ĐPCM) Bài 15 : Chứng minh rằng tồn tại số tự nhiên k sao cho 1983k 105 (Tương tự bài 6 xét 100000 số) Bài 16 : Chứng minh rằng tồn tại số có dạng 19931993…1993000..00 1992 Bài giải: Ta thiết lập dãy số sau : A1 =1993 A2 = 19931993 A3 = 199319931993 ……………………. A1992 = 19931993...1993 ( 1992 số 1993) Vì các số lẽ không chia hêt cho các số chẵn nên không có An nào chia hết cho 1992. Ta chia 1992 số trên cho 1992 vì có 1992 phép chia nên có 1992 số dư nhưng chỉ có 1991 giá trị là : 1 , 2 , 3 , … 1991. Theo nguyên tắc Đi ri klê thì có 2 số chia cho 1992 cùng số dư . Gọi 2 số đó là Ai và Aj (i>j) tacó Ai – Aj 1992 hay 19931993…1993 – 19931993 1993 1992 hay 19931993 …1993 000…00 1992 (ĐPCM Câu b : 19961996…1996 1993 Ta thiết lập dãy sau : A1 = 1996 A2 = 19961996 A3 = 199619961996 …………………………. A1993 = 19961996…1996 (1993 số 1996) Nếu một An nào đó chia hết cho 1996 thì đó là (ĐPCM) Nếu không một An nào chia hết cho 1993 thì chia cả 1993 số trên cho 1993 ta có 1993 phép chia nên có 1993 số dư nhưng chỉ có 1992 giá trị là : 1 , 2 , 3 …, 1992. Theo nguyên tắc Đi ri klê thì có 2 số chia cho 1993 cùng số dư . Gọi 2 số dó là Ai và A (i>j) thì Ai–Aj 1993 hay 19961996…1996 – 19961996…1996 1993 Tức là 19961996 …1996000…00 1993 Nên 19961996…1996 . 104j 1993 . Mà ( 104j , 1993) = 1 Nên 19961996…1996 1993 (ĐPCM) Bài 17 : Chứng minh rằng trong 3 số nguyên tố lớn hơn 3 ta luôn tìm được hai số có tổng hoặc hiệu chia hết cho 12 Bài giải : Các số nguyên tố lớn hơn 3 khi chia cho 12 chỉ có số dư là : 1 , 5 , 7 , 11. Chia các số nguyên tố thành 2 tập hợp A là tập hợp các số chia 12 dư 1 hoặc11 B là tập hợp các số chia 12 dư 5 hoặc 7 Do có 3 số nguyên tố mà chỉ có hai tập hợp nên theo nguyên tắc Đia ric klê thì có 2 số nằm trong cùng một tập hợp .Điều đó chứng tỏ rằng có 2 số có tổng hoặc hiệu chia hết cho 12 Bài 18 : Chứng minh rằng tồn tại luỹ thừa của 29 mà chữ số tận cùng của nó là 00001 (Tức là 29m -1 105 , mN) Bài 19 : Chứng minh tồn tại m là số tự nhiên sao cho 3m có tận cùng là 001 Bài 20 : Chứng minh rằng trong hệ cơ số 10 có thể tìm được bội của 1995 mà chỉ được viết bằng chữ số 1 và 0 Bài 21 : a. Chứng minh rằng tồn tại 3232…32 31 (Tương tự bài 16 ) b. Chứng minh rằng tồn tại 124124…124 123 (Tương tự bài 16) c. Chứng minh rằng tồn tại 19961996…1996 1995 (Tương tự bài 16) Bài 22 : a.Trong 10 số tự nhiên bất kì tồn tại hai số có hiệu chia hết cho 9 Bài giải Thật vậy chia cả 10 số trên cho 9 ta có 10 phép chia nên có 10 số dư nhưng chỉ có 9 giá trị đó là : 0 , 1 , 2 , 3 … , 8 .Theo nguyên tắc Đi ri klê thì có 2 số chia cho 9 cùng số dư điều đó chứng tỏ rằng có 2 số có hiệu chia hết cho 9. (ĐPCM) Trong 50 số tự nhiên bất kì tồn tại 2 số có hiệu chi hết cho 49 Bài giải. Thật vậy chia cả 50 số trên cho 49 ta có 50 phép chia nên có 50 số dư nhưng chỉ có 49 giá trị đó là : 0 , 1 , 2 , 3 , …, 48 . Theo nguyên tắc Đi ri klê thì có 2 số chia cho 49 cùng số dư điều đó chứng tỏ rằng có 2 số có hiệu chia hết cho 49 (ĐPCM) Trong 100 số tự nhiên bất kì tồn tại 2 số có hiệu chia hết cho 99 Bài giải Thật vậy chia cả 100 số trên cho 99 ta có 100 phép chia nên có 100 số dư nhưng chỉ có 99 giá trị dư đó là : 0 , 1 , 2 , …, 98. Theo nguyên tắc Đi ri klê thì có 2 số chia cho 99 cùng số dư , điều đó chứng tỏ rằng có 2 số có hiệu chia hết cho 99 (ĐPCM) (Tương tự cho một số bài cùng dạng) Bài 23 : chứng minh rằng n là số tự nhiên ta có : a. 13n – 1 10 4 (n là số tự nhiên) b. 7n có tận cùng là 00001 (n là số tự nhiên) Bài 24 : một lớp học có 50 học sinh cùng tuổi . Chứng tỏ rằng có ít nhất 5 học sinh, sinh trong cùng một tháng . Bài 25 : Chứng minh rằng : 19931993…1993000…00 1994 13571357…1357000…00 2468