Bài viết về một chủ đề nâng cao trong chương trình toán 6 đó là Nguyên lý Diricle và ứng dụng liên quan là bài toán chi hết. Bài viết có cả lý thuyết và bài tập kèm giải, giúp bồi dưỡng các em học sinh phần kiến thức khá giỏi này
Xem thêm : Tính chất chia hết của một tổng
NGUYÊN LÝ DIRICLE VÀ BÀI TOÁN CHIA HẾT
I/ LÝ THUYẾT:
– Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet yêu cầu từ thế kỷ XX đã được vận dụng để chứng tỏ sự sống sót nghiệm trong nhiều bài toán tổng hợp. Nguyên lý này được tăng trưởng từ một mệnh đề rất đơn thuần gọi là nguyên tắc “ nguyên tắc quả cam ” hay là nguyên tắc “ chuồng chim bồ câu ” : Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc như đinh có tối thiểu một ngăn có nhiều hơn một con chim .- Một cách tổng quát, nguyên tắc Dirichlet được phát biểu như sau :Nếu xếp nhiều hơn n + 1 đối tượng người tiêu dùng vào n cái hộp thì sống sót tối thiểu một hộp chứa không ít hơn hai đối tượng người dùng .- Việc chứng tỏ nguyên tắc này hoàn toàn có thể triển khai bằng lập luận phản chứng rất đơn thuần : Giả sử không hộp nào chứa nhiều hơn một đối tượng người dùng thì chỉ có nhiều nhất là n đối tượng người dùng được xếp trong những hộp, trái với giả thiết là số đối tượng người tiêu dùng lớn hơn n .
Ví dụ 1:
Một năm có nhiều nhất là 365 ngày. Do vậy trong số 366 người bất kể khi nào cũng có tối thiểu 2 người có cùng ngày sinh nhật ( không xét năm nhuận ) .
Ví dụ 2:
Thang điểm bài kiểm tra là từ 0 đến 10, tức là có 11 thang điểm khác nhau. Do vậy trong số 12 sinh viên bất kể của một lớp sẽ có tối thiểu 2 người có tác dụng bài kiểm tra giống nhau .
Ví dụ 3:
Cấp bậc quân hàm của sĩ quan có 8 cấp bậc từ thiếu úy đến đại tá. Do vậy trong một đơn vị chức năng có 9 sĩ quan thì sẽ có tối thiểu 2 người cùng cấp bậc .
· Nguyên lý Dirichlet cơ bản:
Nếu nhốt n thỏ vào m lồng, với n > m, nghĩa là số thỏ nhiều hơn số lồng, thì tối thiểu cũng có một lồng nhốt không ít hơn 2 thỏ. ·ĐỂ GIẢI CÁC BÀI TOÁN ÁP DỤNG NGUYÊN TẮC ĐIRICLÊ CHÚNG TA CẦN LƯU Ý MỘT SỐ ĐIỂM SAU ĐÂY :
1. Các bài toán vận dụng nguyên tắc Điriclê thường là những bài toán chứng tỏ sự sống sót của sự vật, vấn đề mà không cần phải chỉ ra một cách tường minh sự vật, vấn đề đó .2. Nhiều bài toán, nguyên tắc Điriclê chỉ Open sau khi biến hóa qua một bước trung gian, hoặc xây dựng những dãy số mới .3. Để giải bài toán vận dụng nguyên tắc Điriclê, nhiều khi ta phải phối hợp với chiêu thức chứng tỏ phản chứng .4. Khi giải những bài toán mà ta đã biết phải vận dụng nguyên tắc Điriclê hoặc Dự kiến sẽ phải dùng nguyên tắc này, tất cả chúng ta cần tâm lý hoặc đổi khác bài toán để làm Open khái niệm ” thỏ ” và ” lồng “, khái niệm ” nhốt thỏ vào lồng ” .5. Cũng hoàn toàn có thể có những bài toán phải vận dụng 2, 3 lần nguyên tắc Điriclê .6. Trong tâm lý khi giải toán ta nỗ lực làm Open những khái niệm ” thỏ ” và ” lồng “, nhưng trong trình diễn phần lời giải ta nỗ lực diễn đạt theo ngôn từ toán học thường thì7. Khi giải xong những bài toán vận dụng nguyên tắc Điriclê, tất cả chúng ta cố gắng nỗ lực tâm lý để phát minh sáng tạo ra được những bài toán tổng quát hơn hoặc đơn cử hơn. Vì chỉ có như thế ta mới thật nắm chắc bài toán mà mình đã làm .
II / BÀI TẬP:
Bài tập 1:
Người ta viết 5 số tự nhiên vào một hàng duy nhất a1, a2, a3, a4, a5. Chứng minh rằng hoặc một trong những số đó chia hết cho 5, hoặc tổng 1 số ít số tự nhiên kề nhau chia hết cho 5 .Bài giải :Xét 5 tổng : S1 = a1S2 = a1 + a2S3 = a1 + a2 + a3S4 = a1 + a2 + a3 + a4S5 = a1 + a2 + a3 + a4 + a5Nếu một trong những số đó chia hết cho 5 thì bài toán đã giải xong. Trong trường hợp trái lại, khi chia cho 5 thì mỗi số sẽ có một số ít dư nào đó trong 4 số : 1, 2, 3, 4. Theo lý Dirichlet tối thiểu 2 trong 5 số đó có cùng số dư. Vậy hiệu của hai tổng đó chia hết cho 20. Chẳng hạn hai tổng đó là Sm và Sn thì :Sm – Sn ( a1 + a2 + … + an + … + am ) – ( a1 + a2 + … + an )= an + 1 + an + 2 + … + amMà ( Sm – Sn ) 5 ( chứng tỏ trên )Và an + 1 + an + 2 + … + am là tổng một số ít số tự nhiên kề nhau .
Vậy tổng một số ít số tự nhiên kề nhau chia hết cho 5 .
Bài tập 2:
Chứng minh rằng trong số 12 số tự nhiên bất kể hoàn toàn có thể chọn hai số có hiệu chia hết cho 11 .Bài giải :Khi chia 12 số bất kể cho 11 ta sẽ có mỗi số có một số ít dư trong 11 số dư : 0, 1, 2, …, 10. Do đó theo nguyên tắc Dirichlet phải sống sót tối thiểu hai số có cùng số dư. Hiệu của hai số đó sẽ chia hết cho 11 .
Bài tập 3: 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. Chứng minh rẳng í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).
Bài giải :Có 45 – 2 = 43 hoc sinh phân loại 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 viên thì lớp học có không quá : 5.8 = 40 học viên, ít hơn 43 học viên. Vậy sống sót 6 học viên có điểm kiểm tra bằng nhau .Trong bài toán này “ thỏ ” là 43 điểm kiểm tra từ 2 đến 9, “ lồng ” là 8 loại điểm nói trên. Tồn tại học viên có điểm kiểm tra bằng nhau .
Bài tập 4:
Cho 12 số tự nhiên khác nhau có hai chữ số. Chứng minh rằng không sống sót hai số có hiệu là 1 số ít có hai chữ số như nhau .Bà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 đó sống sót hai số có cùng số dư trong phép chia cho 11. Hiệu của chúng là một số ít chia hết cho 11, đó là số có hai chữ số như nhau .
Bài tập 5: Có 5 đấu thủ thi đấu cờ, mỗi người đấu một trận với mỗi đấu thủ khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ có số trận đã đấu bằng nhau.
Bài giải :Gọi 5 lồng 0, 1, 2, 3, 4 thứ tự chứa những đấu thủ đã đấu 0, 1, 2, 3, 4 trận. Cũng chú ý quan tâm rằng hai lông 0 và 4 không hề cùng chứa người. Như vậy chỉ có 4 lồng, mà có 5 người, sống sót 2 người trong cùng một lồng tức là sống sót hai đấu thủ có số trận đấu bằng nhau .
Bài tập 6:
Cho một bảng vuông 4 x 4. Trên 16 ô của bảng, ta đặt 16 số tự nhiên từ 1 đến 16. Chứng minh rằng sống sót hai ô kề nhau ( tức là hai ô có một cạnh chung ) sao cho hiệu những số ở hai ô đó lớn hơn hoặc bằng 3 .
Bài giải :
Chuyển từ một ô bất kỳ sang ô kề nó gọi là một bước. Xét hai ô ghi số 1 và số 16 chuyển từ ô ghi số 1 đến ô ghi số 16 chỉ cần không quá 6 bước chuyển ( nhiều nhất là 3 bước theo hàng ngang, 3 bước theo hàng dọc ). Tồn tại một bước chuyển có hiệu lớn hơn hoặc bằng 3. Thật vậy giả sử tổng thể những bước chuyển đều nhỏ hơn hoặc bằng 2 thì từ số 1, qua không quá 6 bước chuyển tăng thêm không quá 12, không đạt được đến số 16 .Vậy sống sót hai ô kề nhau có hiệu những số của hai ô đó lớn hơn hoặc bằng 3 .
Bài tập 7:
Viết 16 số, mỗi số có giá trị bất kể là 1, 2, 3, 4. Ghép thành từng cặp 2 số được 8 cặp số. Chứng minh rằng sống sót hai cặp số mà tồng những số trong hai cặp đó bằng nhau .Bài giải :Tổng hai số của mỗi cặp trong 8 cặp số có giá trị nhỏ nhất là : 1 + 1 = 2, có giá trị lớn nhất là : 4 + 4 = 8. Như vậy 8 tổng đó nhận 7 giá tri : ( 2, 3, 4, 5, 6, 7, 8 ). Theo nguyên tắc Dirichlet, sống sót hai tổng bằng nhau, tức là sống sót hai cặp có tổng bằng nhau .
Bài tập 8: Một học sinh 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.
Giải:
Một năm có 12 tháng. Ta phân loại 40 học viên vào 12 tháng ấy. Nếu mỗi tháng có không quá 3 học viên được sinh ra thì số hoc sinh không quá 3.12 = 36 mà 36 Bài tập 9: Chứng minh rằng tồn tại số tự nhiên k sao ({3^k}) tận cùng bằng 001.
Giải:
Trước hết ta chứng tỏ rằng sống sót hai lũy thừa của 3 có cùng số dư khi chia cho 1000. Trong phép chia cho 1000, có 1000 số dư là 0, 1, 2, …, 999 .Ta xét 1001 số là ( { 3,3 ^ 2 } {, 3 ^ 3 } {, …, 3 ^ { 1001 } } ) thì sống sót hai số có cùng số dư trong phép chia cho 1000. Gọi hai số đó là ( { 3 ^ m } ) và ( { 3 ^ n } ) ( ( 1 le n { 3 ^ { m – n } } – 1 vdots 1000 ), tức là số ( { 3 ^ { m – n } } ) tận cùng bằng 001 .
Bài tập 10. Một đồi thông có 800 000 cây thông. Trên mỗi cây thông có không quá 500 000 chiếc lá. Chứng minh rằng ít nhất cũng có 2 cây thông có cùng số lá như nhau ở trên cây.
Bài giải :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ối thiểu có 1 lồng nhốt không ít hơn 2 thỏ nghĩa là có tối thiểu 2 cây thông có cùng số lá .
Bài tập 11. 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.
Bài giải : Một năm có 12 tháng. Ta phân loại 40 học viên vào 12 tháng đó. Nếu mỗi tháng có không quá 3 học viên được sinh ra thì số học viên không quá : 3.12 = 36 mà 36 Bài tập 12. 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.
Ta sẽ xây dựng dãy số mới gồm 5 số sau đây :S1 = a1
S2 = a1 + a2S3 = a1 + a2 + a3S4 = a1 + a2 + a3 + a4S5 = 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 tỏ .- Nếu không có số nào chia hết cho 5 thì khi đem chia những 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ối thiểu 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 những ai liên tục nhau hoặc là ai nào đó
Bài tập 13.
Với 39 số tự nhiên liên tục, hỏi rằng ta hoàn toàn có thể tìm được một số ít mà tổng những chữ số của nó chia hết cho 11 hay không ?Bài giải :Từ 20 số tiên phong của dãy khi nào ta cũng hoàn toàn có thể tìm được 2 số mà chữ số hàng đơn vị chức năng là 0, và trong hai số đó tối thiểu phải có một số ít có chữ số hàng chục khác 9. Giả sử N là số đó, và ta gọi S là tổng những chữ số của N .Ta có dãy số mới N, N + 1, N + 2, … N + 9, N + 19 là 11 số vẫn nằm trong 39 số cho trước mà tổng những chữ số của chúng là S, S + 1, S + 2, … S + 9, S + 10. Đó là 11 số tự nhiên liên tục, ắt phải có một số ít chia hết cho 11 .
Bài tập 14. Chứng minh rằng trong 52 số tự nhiên tùy ý, chí ít cũng có một cặp gồm hai số sao cho hoặc tổng hoặc hiệu của chúng chia hết cho 100.
Bài giải : Để làm Open số ” thỏ ” và số ” lồng ta làm như sau :Trong tập hợp những số dư trong phép chia cho 100 ta lấy ra từng cặp số sao cho tổng những cặp đó bằng 100 và xây dựng thành những nhóm sau : ( 0 ; 0 ), ( 1 ; 99 ), ( 2 ; 98 ), ( 3 ; 97 ), ( 4 ; 96 ), ( 5 ; 95 ), ( 6 ; 94 ) … ( 49 ; 51 ), ( 50 ; 50 ) .Chú ý rằng sẽ có 50 cặp như vậy, ta thêm vào cặp ( 0, 0 ) sẽ có 51 cặp ( 51 lồng ) .- Đem chia 52 số tự nhiên cho 100 sẽ có 52 số dư ( 52 thỏ ) .- Có 52 số dư mà chỉ có 51 nhóm, theo nguyên tắc Điriclê tối thiểu cũng phải có 2 số dư cùng rơi vào một nhóm .Rõ ràng là 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 tập 15. 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ố mà tổng các chữ số của nó chia hết cho 10.
Bài giải :Trước hết ta chứng tỏ rằng trong n số tự nhiên liên tục khi nào cũng sống sót một số ít chia hết cho n. ( Các bạn tự chứng minh điều này ) .
Với 19 số tự nhiên liên tục bất kỳ luôn luôn sống sót 10 số liên tục có chữ số hàng chục như nhau, còn những chữ số hàng đơn vị chức năng có giá trị từ 0 đến 9 .Vì thế tổng những chữ số của mỗi số trong 10 số này cũng làm thành dãy số gồm có 10 số tự nhiên liên tục, do đó sống sót 1 số ít chia hết cho 10 ( đpcm ) .
Bài 16:
Có 17 nhà toán học viết thư cho nhau trao đổi về 3 yếu tố khoa học, mỗi người viết thư cho một người về một yếu tố. Chứng minh rằng tối thiểu cũng có 3 nhà toán học trao đổi với nhau về cùng một yếu tố .Bài giải : Gọi A là nhà toán học nào đó trong số 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 yếu tố .Như vậy nhà toán học A phải trao đổi tối thiểu với 6 nhà toán học về một yếu tố nào đó. Vì nếu chỉ trao đổi với số ít hơn 6 nhà toán học về một yếu tố thì số nhà toán học được trao đổi với A ít hơn 16. ( Các bạn hoàn toàn có thể miêu tả theo khái niệm ” thỏ ” và ” lồng ” để thấy ở đây đã vận dụng nguyên tắc Điriclê lần thứ nhất. )- Gọi những nhà toán học trao đổi với nhà toán học A về một yếu tố nào đó ( giả sử yếu tố I ) là A1, A2, A3, A4, A5, A6. Như vậy có 6 nhà toán học trao đổi với nhau về 3 yếu tố ( không kể trao đổi với A ). Như vậy có 6 nhà toán học A1, A2, A3, A4, A5, A6 trao đổi với nhau về 3 yếu tố, I, II, III .
Có hai năng lực xảy ra :a. Nếu có 2 nhà toán học nào đó cùng trao đổi với nhau về yếu tố I thế thì có 3 nhà toán học ( kể cả A ) trao đổi với nhau về yếu tố I. Bài toán được chứng tỏ .
b. Nếu không có nhà toán học nào trong 6 nhà toán học A1, A2 … A6 trao đổi về vấn đề I thì ta có 6 nhà toán học chỉ trao đổi với nhau về 2 vấn đề II và III.
Theo nguyên tắc Điriclê có tối thiểu 3 nhà toán học cùng trao đổi với nhau về một yếu tố II hoặc III. Bài toán cũng được chứng tỏ
Tất cả nội dung bài viết. Các em hãy xem thêm và tải file chi tiết dưới đây:
