Chuyên đề bồi dưỡng học sinh giỏi Toán Lớp 7 - Chuyên đề 16: Ứng dụng nguyên lý Dirichlet

Bạn đang xem tài liệu "Chuyên đề bồi dưỡng học sinh giỏi Toán Lớp 7 - Chuyên đề 16: Ứng dụng nguyên lý Dirichlet", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. CHUYÊN ĐỀ 16 : ỨNG DỤNG NGUYÊN LÝ DIRICHLET I. TÓM TẮT LÍ THUYẾT. - Nguyên lý Dirichlet do nhà toán học người Đức nổi tiếng là Dirichlet đề xuất từ thế kỷ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ một mệnh đề rất đơn giản gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý “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 chắn có ít nhất một ngăn có nhiều hơn một con chim. - Một cách tổng quát, nguyên lý Dirichlet được phát biểu như sau: Nếu xếp nhiều hơn n+1 đối tượng vào n cái hộp thì tồn tại ít nhất một hộp chứa không ít hơn hai đối tượng. - Việc chứng minh nguyên lý này có thể tiến hành bằng lập luận phản chứng rất đơn giản: Giả sử không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiết là số đối tượng lớn hơn n. - Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào m cái chuồng thì tồn tại một chuồng có ít nhất n m 1 con thỏ . m * Một số chú ý: 1. Các bài toán áp dụng nguyên tắc Đirichle 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 đó. 2. Nhiều bài toán, nguyên tắc Đirichle 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. 3. Để giải bài toán áp dụng nguyên tắc Đirichle, nhiều khi ta phải kết hợp với phương pháp chứng minh phản chứng. 4. Khi giải các bài toán mà ta đã biết phải áp dụng nguyên tắc Đirichle hoặc dự đoán sẽ phải dùng nguyên tắc này, chúng ta cần suy nghĩ hoặc biến đổi bài toán để làm xuất hiện khái niệm "thỏ" và "lồng", khái niệm "nhốt thỏ vào lồng" và thỏa mãn các điều kiện: + Số thỏ phải nhiều hơn số lồng. + Thỏ phải được nhốt hết vào các lồng, nhưng không bắt buộc lồng nào cũng phải có thỏ. 5. Cũng có thể có những bài toán phải áp dụng 2, 3 lần nguyên tắc Đirichle. 6. Trong suy nghĩ khi giải toán ta cố gắng làm xuất hiện các khái niệm "thỏ" và "lồng", nhưng trong trình bày phần lời giải ta cố gắng diễn đạt theo ngôn ngữ toán học thông thường. 7. Khi giải xong các bài toán áp dụng nguyên tắc Điriclê, chúng ta cố gắng suy nghĩ để sáng tạo ra được các bài toán tổng quát hơn hoặc cụ thể 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.CÁC DẠNG BÀI TẬP: DẠNG 1. SỰ TƯƠNG HỖ Bài 1. 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. Phân tích: Ta thành lập được các cái lồng đó là các lồng chứa số trận đã đấu của các đấu thủ (có 4 lồng), số đấu thủ ta coi là các con thỏ. Trang 1 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. Lời giải Gọi 5 lồng 0,1,2,3,4 thứ tự chứa các đấu thủ đã đấu 0,1,2,3,4 trận. Cũng chú ý rằng hai lồng 0 và 4 không thể cùng chứa người. Như vậy chỉ có 4 lồng, mà có 5 người, tồn tại 2 người trong cùng một lồng tức là tồn tại hai đấu thủ có số trận đấu bằng nhau. Bài 2. Cho 5 người tùy ý. CMR trong số đó có ít nhất 2 người có số người quen như nhau (hiểu rằng A quen B thì B quen A). Phân tích: Chú trọng đến câu hỏi “ 2 người có số người quen như nhau” Từ đó hiểu rằng 5 người đóng vai trò là số thỏ. Ta có thể tạo ra các lồng như sau: Lồng 1 chứa số người không quen ai, lồng 2 chứa số người có số người quen là 1, Lời giải Gọi lồng 0 chứa những người có số người quen là 0 . Gọi lồng 1 chứa những người có số người quen là 1. Gọi lồng 4 chứa những người có số người quen là 4 . Như vậy ta có 5 lồng. Nếu lồng 0 có chứa ai đó thì lồng 4 phải trống. Ngược lại nếu lồng 4 có chứa ai đó thì lồng 0 phải trống. Vậy thực chất chỉ có 4 lồng nhốt 5 thỏ nên có ít nhất 2 người ở cùng một phòng tức là hai người đó có số người quen như nhau. Bài 3. 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 (kể cả số trận đấu là 0). Phân tích: Hiểu tương tự như bài toán trên. Lời giải Gọi A0 là phòng chứa các đội có số trận đấu là 0 . Gọi A1 là phòng chứa các đội có số trận đấu là 1. Gọi A9 là phòng chứa các đội có số trận đấu là 9. Nếu phòng A0 có ít nhất 1 đội thì phòng A9 không có đội nào và ngược lại phòng A9 có ít nhất 1 đội thì phòng A0 không có đội nào. Vậy thực chất chỉ có 9 phòng được sử dụng mà lại có 9 đội nên có ít nhất 2 đội vào chung một phòng hay có ít nhất 2 đội có cùng số trận đấu như nhau. Bài 4. 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. Phân tích: Coi 6 đội bóng là 6 con thỏ vậy ta tìm cách thành lập các lồng. Vì bài toán yêu cầu tận 3 đội tức 3 con thỏ trong một lồng nên trước tiên ta cần chọn ra 1 con thỏ rồi xét các con thỏ khác cùng tính chất (đã đấu hay chưa đấu) với con thỏ đã chọn. Như vậy, khi đó ta tạo ra các lồng như sau : Lồng 1 chứa các đội chưa đấu với đội chọn ra trận nào, lồng 2 chứa các đội đã đấu với đội đã chọn. Trang 2 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. Lời giải Giả sử 6 đội bóng đó là A, B, C, D, E, F . Xét đội A: Theo nguyên lý Dirichlet 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. Bài 4. Trong 45 học sinh làm bài kiểm tra không có ai bị điểm dưới 2 và 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 từ 0 đến 10). Lời giải Số học sinh có điểm kiểm tra từ 2 đến 9 là : 45 – 2 43 Ta có : 43 8.5 3 Như vậy , khi phân chia 43 học sinh vào 8 loại điểm kiểm tra ( từ 2 đến 9 ) thì theo nguyên lí Dirichlet luôn tồn tại ít nhất 5 1 6học sinh có điểm kiểm tra giống nhau (đpcm ) Bài 5. Có 17 nhà toán học trao đổi với nhau về 3 vấn đề. Mỗi người tra đổi với một người về 1 vấn đề. CMR cũng có ít nhất 3 nhà toán học trao đổi với nhau về cùng một vấn đề (I và II, II và III, III và I). Phân tích: Tương tự như 17 điểm được nối với nhau bằng 3 màu à luôn tồn tại một tam giác với 3 cạnh cùng màu tức là 3 nhà toán học trao đổi với nhau về cùng một vấn đề. Lời giải Một nhà toán học trao đổi với 16 nhà toán học khác về 3 vấn đề nên theo nguyên lý Dirichlet có ít nhất 6 người sẽ được một người trao đổi về cùng một vấn đề, giả sử đó là vấn đề I. 6 người này lại trao đổi với nhau về 3 vấn đề: + TH1: Nếu có 2 người nào đó cùng trao đổi về vấn đề I thì bài toán được chứng minh. + TH2: Nếu không có 2 người nào cùng trao đổi về vấn đề 1 thì 6 người này chỉ trao đổi về 2 vấn đề II và III. Một người trao đổi với 5 người còn lại về 2 vấn đề II và III. Theo nguyên lý Dirichlet có ít nhất 3 người cùng được một người trao đổi về 1 vấn đề, giả sử đó là vấn đề II. Ba người này lại tiếp tục trao đổi với nhau: + TH1: Nếu có 2 người nào đó cùng trao đổi với nhau về vấn đề II thì bài toán được chứng minh. + TH2: Nếu không có 2 người nào cùng trao đổi với nhau về vấn đề II thì cả 3 người này trao đổi với nhau về vấn đề III suy bài toán cũng đã được chứng minh. 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 đề Trang 3 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. DẠNG 2. SỰ SẮP XẾP Bài 1. 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 tồn tại hai ô kề nhau (tức là hai ô có một cạnh chung ) sao cho hiệu các số ở hai ô đó lớn hơn hoặc bằng 3. Phân tích: Vì yêu cầu liên quan đến hiệu hai ô cạnh nhau (hiệu 2 số trong hai ô) nên ta coi số các hiệu có thể của hai ô cạnh nhau là số thỏ, số các cặp ô cạnh nhau từ ô ghi số 1 đến ô ghi số 16 là các lồng. Lời giải Xét hàng có ô ghi số 1 và cột có ô ghi số 16. Hiệu giữa hai số này là 15 (coi như là 15 thỏ). Số cặp ô kề nhau từ ô ghi số 1 đến ô ghi số 16 nhiều nhất là 6 (gồm 3 cặp ô chung cạnh tính theo hàng và 3 cặp ô chung cạnh tính theo cột) (coi như có 6 lồng). Ta có: 15 6.2 3. Vậy theo nguyên lý Dirichlet luôn tồn tại hai ô vuông chung cạnh mà hiệu các số ghi trong chúng không nhỏ hơn 3. Cách khác: 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ất cả các 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 tồn tại hai ô kề nhau có hiệu các số của hai ô đó lớn hơn hoặc bằng 3. Bài 2. 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 tồn tại hai cặp số mà tồng các số trong hai cặp đó bằng nhau. Phân tích: Ta sắp xếp các tổng của các cặp theo thứ tự từ lớn đến bé thì lớn nhất là 8 còn bé nhất là 2 được dãy các tổng 2,3,4,5,6,7,8. Ta coi các tổng này là các lồng, còn các con thỏ là các cặp có thể. Lờ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á trị: 2,3,4,5,6,7,8 . Theo nguyên lý Dirichlet, tồn tại hai tổng bằng nhau, tức là tồn tại hai cặp có tổng bằng nhau. Bài 3. Người ta chia một hình vuông thành 16 hình vuông nhỏ bằng cách chia mỗi cạnh thành 4 phần bằng nhau. Người ta viết vào mỗi ô của bảng một trong các số a; 0; a sau đó tính tổng các số theo từng cột, từng hàng và từng đường chéo. Chứng minh rằng trong tất cả các tổng đó luôn tồn tại 2 tổng có giá trị bằng nhau. Phân tích: Có bao nhiêu tổng theo cột, theo hàng, theo đường chéo đó chính là “số thỏ”. Mỗi tổng có thể có giá trị bao nhiêu. Số giá trị của tổng sẽ là số “lồng”. Lời giải Trang 4 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. Số hàng: 4; Số cột: 4; Số đường chéo: 2. Như vậy sẽ có 10 tổng. Các giá trị có thể có khi cộng các số trong mỗi hàng, cột hoặc đường chéo là 4a; 3a; 2a; a; 0; a; 2a; 3a; 4a. Có 10 tổng, mỗi tổng nhận 1 trong 9 giá trị mà 10 9.1 1. Theo nguyên lý Dirichlet tồn tại hai tổng có giá trị bằng nhau. Bài 4. a) Trên một bảng ô vuông kích thước 6 6 ta viết vào mỗi ô của bảng một trong các số 1; 0; 1 sau đó tính tổng của các số theo từng cột, theo từng dòng và theo từng đường chéo. Chứng minh rằng luôn tồn tại hai tổng có giá trị bằng nhau. b) Trên bảng ô vuông kích thước 6 6 ấy ta viết các số tự nhiên từ 1 đến 36, mỗi số viết vào một ô một cách tùy ý. Chứng minh rằng luôn tồn tại hai ô vuông chung cạnh mà hiệu các số ghi trong chúng không nhỏ hơn 4. Phân tích: a) Bài toán yêu cầu kết quả liên quan đến tổng nên ta coi các tổng là các con thỏ còn các hàng, cột, đường chéo là các lồng. b) Vì yêu cầu liên quan đến hiệu hai ô cạnh nhau (hiệu 2 số trong hai ô) nên ta coi số các hiệu có thể của hai ô cạnh nhau là số thỏ, số các cặp ô cạnh nhau từ ô ghi số 1 đến ô ghi số 36 là các lồng. Lời giải a) Bảng ô vuông kích thước 6 6 có 6 dòng, 6 cột và 2 đường chéo nên sẽ có 14 tổng của các số được tính theo dòng, theo cột và theo đường chéo. Mỗi dòng, mỗi cột và đường chéo đều ghi 6 số thuộc tập 1;0;1 . Vì vậy giá trị mỗi tổng thuộc tập hợp 6; 5; 4; 3; 2; 1;0;1;2;3;4;5;6 có 13 phần tử. Có 14 tổng nhận trong tập 13 giá trị khác nhau nên theo nguyên lý Dirichlet tồn tại ít nhất hai tổng có cùng một giá trị. b) Xét hàng có ô ghi số 1 và cột có ô ghi số 36. Hiệu giữa hai số này là 35 (coi như là 35 thỏ). Số cặp ô kề nhau từ ô ghi số 1 đến ô ghi số 36 nhiều nhất là 10 (gồm 5 cặp ô chung cạnh tính theo hàng và 5 cặp ô chung cạnh tính theo cột) (coi như có 10 lồng). Ta có: 35 10.3 5. Vậy theo nguyên lý Dirichlet luôn tồn tại hai ô vuông chung cạnh mà hiệu các số ghi trong chúng không nhỏ hơn 4. Bài 5. Mỗi ô vuông của bảng kích thước 10 10 (10 dòng, 10 cột) được ghi một số nguyên dương không vượt quá 10 sao cho bất kỳ hai số nào ghi trong hai ô chung một cạnh hoặc hai ô chung một đỉnh của bảng là hai số nguyên tố cùng nhau. Chứng minh rằng có số được ghi ít nhất 17 lần. Lời giải Phân tích đề bài ta tạo ra các con thỏ và các cái lồng như sau: Số các con thỏ chính là các số cách c Trên mỗi hình vuông con kích thước 2 2 có không quá 1 số chia hết cho 2, không quá 1 số chia hết cho 3. Lát kín bảng bởi 25 hình vuông, kích thước 2 2, có nhiều nhất 25 số chia hết cho 2, có nhiều nhất 25 số chia hết cho 3. Do đó, có ít nhất 50 số còn lại không chia hết cho 2 và cũng không chia hết cho 3. Vì vậy chúng phải là một trong ba số 1;5;7 . Ta có 50 3.16 2 . Từ đó theo nguyên lý Dirichlet có một số xuất hiện ít nhất 17 lần. Trang 5 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. Bài 6. Có 20 người quyết định đi bơi thuyền bằng 10 chiếc thuyền đôi. Biết rằng nếu hai người A và B mà không quen nhau thì tổng số những người quen của A và những người quen của B không nhỏ hơn 19. Chứng minh rằng có thể phân công vào các thuyền đôi sao cho mỗi thuyền đều là hai người quen nhau. Lời giải Nếu trong 20 người không có hai người nào quen nhau thì tổng số người quen của hai người bất kì là 0. Điều này mâu thuẫn với giả thiết là tổng số người quen của hai người không nhỏ hơn 19. Vậy tồn tại một số cặp quen nhau. Ta xếp mỗi cặp quen nhau đó vào một thuyền đôi. Gọi k là số lượng thuyền lớn nhất mà trong đó ta có thể xếp được những cặp quen nhau vào một thuyền và kí hiệu thuyền thứ i xếp hai người Ai và Bi quen nhau (1 i k) . Giả sử k 9 , kí hiệu tập hợp M gồm những người chưa được xếp vào thuyền nào, tức là gồm những người đôi một không quen nhau. Chọn hai người A và B trong tập hợp M. Theo bài ra thì tổng số người quen của A và số người quen của B không nhỏ hơn 19 và những người quen A hoặc quen B đã được xếp vào thuyền rồi. Như vậy có 19 người quen A hoặc B được xếp vào nhiều nhất là 9 thuyền đôi (trừ 1 thuyền vì A, B chưa được xếp), nên theo nguyên lí Dirichlet tồn tại ít nhất một thuyền chở 2 người quen cả A và B (thuyền thứ i nào đó). Nhưng khi đó ta có thể xếp lại như sau: giữ nguyên k 1 thuyền, còn thuyền thứ i xếp Ai và B, còn thuyền thứ k 1 xếp A và Bi . Điều này mâu thuẫn với giả sử k 9 . Theo cách xếp này ta tiếp tục xếp đến hết 10 thuyền sao cho mỗi thuyền hai người đều quen nhau. Bài 7. Cho tập A 1;2;3;...;16 . Hãy tìm số nguyên dương k nhỏ nhất sao cho trong mỗi tập con gồm k phần tử của A đều tồn tại hai số phân biệt a, b mà a2 b2 là một số nguyên tố. Lời giải Nếu a,b chẵn thì a2 b2 là hợp số. Do đó nếu tập con X của A có hai phần tử phân biệt a,b mà a2 b2 là một số nguyên tố thì X không thể chỉ chứa các số chẵn. Suy ra k 9 . Ta chứng tỏ k 9 là giá trị nhỏ nhất cần tìm. Điều đó có ý nghĩa là với mọi tập con X gồm 9 phần tử bất kỳ của A luôn tồn tại hai phần tử phân biệt a,b mà a2 b2 là một số nguyên tố. Để chứng minh khẳng định trên ta chia tập A thành các cặp hai phần tử phân biệt a,b mà a2 b2 là một số nguyên tố, ta có tất cả 8 cặp 1;4 , 2;3 , 5;8 , 6;11 , 7;10 , 9;16 , 12;13 , 14;15 . Theo nguyên lý Dirichlet thì 9 phần tử của X có hai phần tử cùng thuộc một cặp và ta có điều phải chứng minh. DẠNG 3. ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE VÀO 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 Trang 6 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. có hai phép chia có cùng số dư.Giả sử hai số bị chia trong hai phép chia đó là ai và a j (với 1 j i m 1 ).Ta có ( ai a j )m . Bài 1. Chứng minh rằng trong số 39 số tự nhiên liên tiếp bất kì luôn tồn tại ít nhất một số có tổng các chữ số chia hết cho 11. Lời giải Xét tập hợp 39 số tự nhiên liên tiếp S a1;a2 ;...;a39, ai 1 ai 1,1 i 38 Trong tập a1;a2 ;...;a20luôn tồn tại hai số có tận cùng là 0 và hơn kém nhau 10. Do đó trong hai số này tồn tại ít nhất một số có chữ số hàng chục nhỏ hơn 9, kí hiệu số đó là: A Bc0 0 c 8,c ¥ , B ¥ Xét 11 số: Nhận xét rằng: A; A 1; A 2;...; A 9; A 10 + 11 số trên thuộc tập S + 11 số đó có tổng các chữ số là 11 số tự nhiên liên tiếp vì tổng đó là: s A ;s A 1;s A 2;...;s A 9;s A 10 , với s A là tổng các chữ số của A. Trong 11 số tự nhiên liên tiếp luôn tồn tại một số chia hết cho 11. Do vậy, ta có điều phải chứng minh. Bài 2. Cho 2021 số tự nhiên bất kì. Chứng minh rằng trong các số đó có một số chia hết cho 2021 hoặc một tổng các số trong các số đã cho chia hết cho 2021. Lời giải Gọi 2014 số tự nhiên đã cho là a1;a2 ;...;a2021 Xét dãy S1 a1;S2 a1 a2 ;...;S2021 a1 a2 ... a2021 Chia tất cả các số hạng của dãy cho 2021 ta có các trường hợp sau: • Trường hợp 1: Nếu có một số hạng nào của dãy chia hết cho 2021 thì bài toán được chứng minh. • Trường hợp 2: Nếu không có số hạng nào của dãy chia hết cho 2021 thì vì có tất cả 2021 phép chia mà số dư chỉ gồm 1, 2, ..., 2020 do đó theo nguyên lý Dirichle có ít nhất hai số hạng của dãy có cùng số dư khi chia cho 2021. Gọi hai số hạng đó là: Si ; S j Không mất tính tổng quát, giả sử 1 i j 2021 Với Si a1 a2 ... ai ;S j a1 a2 ... ai ... a j Si S j 2021 ai 1 ... a j 2021 Từ đó ta có điều phải chứng minh. Bài 3. Cho 12 số tự nhiên khác nhau có hai chữ số. Chứng minh rằng tồn tại hai số có hiệu là một số có hai chữ số như nhau. Trang 7 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. Lời giải Có 12số 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 4. 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 cho10. 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ó 10khả 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 10có cùng số dư do đó hiệu của chúng chia hết cho 10 (đpcm). Bài 5. 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 Xét dãy số có dạng: 1994 ; 19941994 ; ... ; . +) Các số ở dãy 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ó1994khả 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). k Bài 6. Chứng minh rằng tồn tại số tự nhiên k sao cho (1999 1) chia hết cho 104. Lời giải Xét dãy số có dạng: 19991;19992 ;...;1999104 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à 1999a và 1999b (với a > b) Ta có: 1999a 1999b 104 1999b[1999(a b) 1]104 Mà ƯCLN(1999b , 104) là 1 (vì là hai số nguyên tố cùng nhau) nên 1999(a b) 1104 . Đặt k a – b , ta có 1999k 1104 (đpcm) Bài 7. Chứng minh rằng tồn tại một số chỉ viết bởi hai chữ số chia hết cho 2003. Lời giải Xét dãy 2003 số có dạng 1;11;111;...; +) Nếu có một số chia hết cho 2003 thì 11...1100..002003(đpcm). +) Nếu không có một số nào chia hêt cho 2003 thì sẽ có 2002 khả năng dư là 1;2;3;...;2002. Trang 8 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. Mà dãy số trên có 2003 số hạng nên sẽ có ít nhất hai số khi chia cho 2003 có cùng số dư Gọi hai số có cùng số dư khi chia cho 2003 là 11...11 và 111...111 (với n m ) m chu so 1 n chu so 1 Khi đó 111...111-11...11 =11...110...00000 2003 (đpcm). n chu so 1 m chu so 1 n m chu so 0 Bài 8. Chứng minh rằng tồn tại một số tự nhiên chỉ được viết bởi chữ số 2 và chữ số 0 mà số đó chia hết cho 2018 . Lời giải Khi chia lần lượt các số trong dãy cho 2018 thì số dư của các phép chia nằm trong khoảng từ 1 đến 2017 ( 2017 số dư) Theo nguyên lý dirichlet có ít nhất 2 số khi chia cho 2018 có cùng số dư Giả sử có 2 số khi chia cho 2018 có cùng số dư là là An 222.......22 ( n chữ số 2 ). Am 22222...22222 ( m chữ số 2 ); n m . Khi đó hiệu của hai số mà khi chia cho 1 số có cùng số dư thì hiệu đó chia hết cho số chia Am An 22222..22 2222...2 222222...0000 (n chữ số 0 và m n chữ số 2) chia hết cho 2018 (đpcm). Bài 9. Chứng minh rằng trong 19 số tự nhiên liên tiếp bất kì ta luôn tìm được một số có tổng các chữ số chia hết cho 10. Lời giải Trong 19 số tự nhiên liên tiếp luôn tồn tại 10 số tự nhiên liên tiếp có chữ số hàng chục giống nhau , kí hiệu chữ số hàng chục đó là a ( các chữ số hàng trăm , hàng nghìn , .(nếu có ) cũng giống nhau) , còn các chữ số hàng đơn vị là dãy 0;1;2;3; ;9.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 10. 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ố trong dãy 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: S = a 1 1 S = a + a 2 1 2 S = a + a + a 3 1 2 3 S = a + a + a + a 4 1 2 3 4 S = a + a + a + a + a 5 1 2 3 4 5 - Nếu một trong các số Si i 1, ... 5 chia hết cho 5 thì bài toán đã được chứng minh. Trang 9 ỨNG DỤNG NGUYÊN LÍ ĐIRRICHLE. - 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 11. 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. 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 các chữ số của chúng là x . Mà S; S 1; S 2; ... ;S 9;S 10; là 11 số tự nhiên liên tiếp, ắt phải có một số chia hết cho 11. Bài 12. 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. Lời giải Để làm xuất hiện số "thỏ" và số "lồng ta làm như sau: 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 thành các 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ó 51cặp (51lồ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 Đirichle ít nhất 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 cho100 (đpcm). Bài 13. Cho dãy m số tự nhiên bất kì a1,a2 ,....,am .Chứng minh rằng tồn tại một số hạng chia hết cho m hoặc tổng của một số số trong dãy chia hết cho m(m ¥ *) . Lời giải Xét dãy số b1 = a1,b2 = a1 + a2,.......,bm = a1 + a2 + .... + am Khi chia các số hạng của dãy này cho m thì xảy ra một trong hai trường hợp sau : • Có một phép chia hết , chẳng hạn : bk m , thì ta có điều phải chứng minh : (a1 + a2 + .... + ak )Mm • Không có phép chia hết nào .Khi đó tồn tại hai phép chia có cùng số dư , chẳng hạn là bi ,bj chia cho m ( vơi 1 j i m ). Trang 10
Tài liệu đính kèm:
chuyen_de_boi_duong_hoc_sinh_gioi_toan_lop_7_chuyen_de_16_un.docx