Chuyên đề ôn tập Toán 7 - Chuyên đề 19: Nguyên lý dirichlet

Nội dung text: Chuyên đề ôn tập Toán 7 - Chuyên đề 19: Nguyên lý dirichlet

1. Chuyên đề 19. NGUYÊN LÝ DIRICHLET A. Kiến thức cần nhớ 1. Nội dung: Dirichlet (Điriklê) là tên của một nhà toán học người Đức (Pôngutáp Lêgien Điriklê) ông sinh năm 1805 và mất năm 1859. Trong quá trình nghiên cứu và giảng dạy toán ở các trường phổ thông ông đã đưa ra được một nguyên tắc giải toán rất hữu hiệu và được sử dụng nhiều trong lĩnh vực số học, hình học và đại số. Ngày nay người ta thường gọi nguyên tắc này là nguyên tắc Dirichlet hay nguyên lý Dirichlet (hay còn gọi là nguyên tắc “nhốt thỏ vào lồng”) * Cụ thể: Nếu nhốt 7 con thỏ vào 3 cái lồng thì tồn tại ít nhất một lồng có từ 3 con thỏ trở lên. (Hay: Không thể nhốt 7 con thỏ vào 3 cái lồng lại không có cái lồng nào nhốt nhiều hơn 2 con thỏ). * Tổng quát: a. Nếu ta nhốt n chú thỏ vào n 1 cái lồng thì tồn tại một lồng có từ hai chú thỏ trở lên. b. Khi nhốt n con thỏ vào k cái lồng: + Nếu n kp r 0 r k 1 thì tồn tại ít nhất một lồng chứa không ít hơn p 1 con thỏ. + Nếu n kp thì tồn tại ít nhất một lồng chứa không ít hơn p con thỏ và tồn tại ít nhất một lồng chứa không nhiều hơn p con thỏ. 2. Chú ý: + Nguyên lý Dirichlet thường được sử dụng để giải 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 chỉ ra một cách tường minh sự vật, sự việc đó. + Khi giải bài toán vận dụng nguyên lý Dirichlet, điều quan trọng là phải nhận ra (hay tạo ra) các yếu tố “thỏ”; “lồng”; “nhốt thỏ vào lồng”. Khi giải diễn đạt theo ngôn ngữ toán học. + Nhiều bài toán sau một số bước trung gian mới sử dụng được nguyên lý Dirichlet. + Thường kết hợp với phương pháp chứng minh phản chứng. B. Một số ví dụ Ví dụ 1: Chứng minh nguyên lý Dirichlet.  Tìm cách giải: Chứng minh trực tiếp hoặc sử dụng phản chứng. Giải * Chứng minh: Nếu nhốt 7 con thỏ vào 3 cái lồng thì tồn tại ít nhất một lồng có từ 3 con thỏ trở lên. (Hay: Không thể nhốt 7 con thỏ vào 3 cái lồng mà lại không có lồng nào nhốt nhiều hơn 2 con thỏ). Thật vậy, nếu mỗi lồng chứa không quá 2 con thỏ thì 3 lồng chứa không quá 2.3 6 con thỏ, vô lý. Vậy không thể nhốt 7 con thỏ vào 3 cái lồng mà không có lồng nào nhốt nhiều hơn 2 con thỏ. * Chứng minh tổng quát: a. Nếu ta nhốt n con thỏ vào n 1 cái lồng thì tồn tại một lồng có từ hai con thỏ trở lên. Thật vậy giả sử không có lồng nào chứa từ hai con thỏ trở lên thì nhiều nhất mỗi lồng chỉ chứa một con thỏ. n 1 cái lồng chứa nhiều nhất n 1 con thỏ. Vô lý. Vậy nếu ta nhốt n con thỏ vào n 1 cái lồng thì tồn tại một lồng có từ hai con thỏ trở lên. Trang 1
2. b. Khi nhốt n con thỏ vào k cái lồng: + Nếu n kp r 0 r k 1 thì tồn tại ít nhất một lồng chứa không ít hơn p 1 con thỏ. Thật vậy: Giả sử lồng nào cũng có không quá p con thỏ thì k lồng không có kp con thỏ, ít hơn số n con thỏ, vô lý. + Nếu n kp thì tồn tại ít nhất một lồng chứa không ít hơn p con thỏ và tồn tại ít nhất một lồng chứa không nhiều hơn p con thỏ. Thật vậy giả sử lồng nào cũng chứa ít hơn p con thỏ thì k lồng không có quá k p 1 thỏ, vô lý. Giả sử lồng nào cũng chứa nhiều hơn p con thỏ thì k lồng có ít nhất là k p 1 thỏ, vô lý. Ví dụ 2: Thả 257 viên bi nhỏ vào bàn cờ Quốc tế 64 ô vuông. Chứng minh tồn tại một ô chứa ít nhất 5 viên bi (kể cả trường hợp viên bi nằm trên cạnh ô vuông).  Tìm cách giải: Coi 64 ô vuông như 64 cái lồng. 257 viên bi là 257 con thỏ. Ta thấy 257 64.4 1 . Thả 257 con thỏ vào 64 cái lồng, theo nguyên lý Đi-rich-lê tồn tại một lồng chứa ít nhất 5 con thỏ. Giải Giải trực tiếp như trên. Tuy nhiên có thể dùng phản chứng: Giả sử không tồn tại một ô nào chứa ít nhất 5 viên bi, thì nhiều nhất mỗi ô chỉ chứa 4 viên. 64 ô chứa nhiều nhất 64.4 256 viên bi. Vô lý. Ví dụ 3: Một lớp học có 41 học sinh làm bài kiểm tra Toán, không có ai bị điểm dưới 3. Có bốn học sinh đạt đ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).  Tìm cách giải: Trong bài toán này số “thỏ” là 41 4 37 điểm từ 3 đến 9. “Lồng” là 7 loại điểm nói trên. Phép chia 37 cho 7 được 5 còn dư. Tồn tại 5 1 6 học sinh có điểm kiểm tra bằng nhau. Giải Có 41 4 37 học sinh phân chia vào 7 loại điểm từ 3 đến 9. Giả sử không tồn tại một loại điểm nào có ít nhất 6 bạn đạt, thì nhiều nhất mỗi loại điểm chỉ có 5 bạn đạt; 7 loại điểm có nhiều nhất 7.5 3 bạn5 đạt. Lớp học ít hơn 41 học sinh. Vô lý. Vậy tồn tại ít nhất 6 học sinh có điểm kiểm tra bằng nhau. Ví dụ 4: 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.  Tìm cách giải: 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”. Giải Trang 2
3. 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. Ví dụ 5: Chứng minh rằng: Trong n 1 số tự nhiên bất kỳ a1; a2; ; an; an 1luôn tìm được hai số sao cho hiệu của chúng chia hết cho n.  Tìm cách giải: Trong bài toán “thỏ” là các số tự nhiên bất kỳ, “lồng” là số số dư trong phép chia một số cho n . Chia một số bất kỳ cho n có thể nhận được một trong n số dư 0; 1; 2; ; n 2; n .1 Có n 1 con thỏ, có n cái lồng Giải Chia một số bất kỳ cho n có thể nhận được một trong n số dư 0; 1; 2; ; n 2; n 1. Có n 1 số, có n số dư. Do đó theo nguyên lý Dirichlet tồn tại hai số có cùng số dư khi chia cho n . Không mất tổng quát giả sử hai số đó là ap và aq p;q 1;2; ;n;n 1 và ap aq . Ta có: ap n.kp r r N;0 r n 1 aq n.kq r Khi đó ap aq n. kp kq n. Đây chính là hai số có hiệu của chúng chia hết cho n . Bài toán được chứng minh. Ví dụ 6: Trong 2016 số tự nhiên bất kỳ a1; a2; ; a2016 luôn tìm được một số chia hết cho 2016 hoặc hai số có hiệu chia hết cho 2016.  Tìm cách giải: Trong bài toán số “thỏ” là số 2016 số tự nhiên bất kỳ, “Lồng” là số số dư trong phép chia một số cho 2016. Có hai khả năng xảy ra: hoặc có số chia hết cho 2016, hoặc tất cả các số đều không chia hết cho 2016. Giải Nếu một trong n số chia hết cho 2016, bài toán được chứng minh. Nếu tất cả 2016 số không có số nào chia hết cho 2016 thì mỗi số khi chia cho 2016 sẽ nhận một trong 2015 số dư 1; 2; 3; ; 2014; 2015. Có 2016 số mà có 2015 số dư nên tồn tại 2 số có cùng số dư khi chia cho 2016 hiệu của hai số chia hết cho 2016. (đpcm). Trang 3
4. Ví dụ 7: a) Cho một dãy số gồm 100 số tự nhiên bất kỳ a1; a2; ; a100 . Chứng minh rằng tồn tại một số chia hết cho 100 hoặc tổng một số số chia hết cho 100. b) Hãy tổng quát hóa bài toán.  Tìm cách giải: Trong bài toán số “thỏ” là số 100 số tự nhiên bất kỳ, “Lồng” là số số dư trong phép chia một số cho 100. Có hai khả năng xảy ra: hoặc có số bằng 0, hoặc tất cả các số đều khác không. Giải a) Trường hợp có số bằng 0 ta chọn số này thỏa mãn đầu bài. Trường hợp tất cả các số đều khác 0 ta lập 100 tổng sau: S1 a1 S2 a1 a2 S3 a1 a2 a3 S100 a1 a2 a3 a100 Nếu một trong 100 tổng này chia hết cho 100, bài toán được chứng minh. Nếu tất cả 100 tổng này không chia hết cho 100, thì khi chia cho 100 chúng nhận 99 số dư 1; 2; 3; ; 99. Có 100 tổng và có 99 số dư khi chia cho 100, theo nguyên lý Dirichlet tồn tại hai tổng có số dư bằng nhau khi chia cho 100. Giả sử là hai tổng là Sk a1 a2 a3 ak và Sh a1 a2 a3 ah 100 k h 1 Thì Sk Sh a1 a2 a3 ak a1 a2 a3 ah ah 1 ah 2 ah 3 ak 100. b) Tổng quát hóa: Cho một dãy số gồm n số tự nhiên bất kỳ a1; a2; ; an . Chứng minh rằng tồn tại một số chia hết cho n hoặc tổng một số số chia hết cho n. Ví dụ 8: Chứng minh tồn tại lũy thừa của 79 mà các chữ số tận cùng của nó là 00001.  Tìm cách giải: Nhận xét 79n . Nếu n chẵn thì chữ số tận cùng là 1. Nếu n lẻ thì chữ số tận cùng là 9. Do đó ta xét 105 lũy thừa của 79 với các số mũ chẵn khác nhau. Giải  Cách 1. - Xét 105 lũy thừa của 79 với các số mũ chẵn khác nhau. Nếu một trong các lũy thừa đó có tận cùng là 00001 thì bài toán được chứng minh. Trang 4
5. - Nếu không có lũy thừa nào có tận cùng là 00001 thì số các số có 5 chữ số tận cùng khác nhau kể từ số 00002; 00003; ; đến 99998; 99999 nhỏ hơn 105 . Theo nguyên lý Dirichlet tồn tại ít nhất hai lũy thừa nào đó có 5 chữ số tận cùng giống nhau. Nếu n chẵn thì số 792k chữ số tận cùng là 1. Giả sử đó là hai số: 2k1  A1 79 B1.10 abcd1. 2k2 5 A2 79 B2 .10 abcd1 với A1 A2 . 2k 2k 2k 2 k k 5 A A 79 1 79 2 79 2 79 1 2 1 10 B B . 1 2 1 2 2k 5 2 k k Do 79 2 có tận cùng là 1 và 10 B B có tận cùng không ít hơn 5 số 0 nên 79 1 2 1 có tận cùng 1 2 2 k1 k2 không ít hơn 5 số 0 suy ra 79 có tận cùng là 00001. Vậy tìm được số k 2 k1 k2 thỏa mãn yêu cầu của bài.  Cách 2. Ta cần chứng minh tồn tại k N sao cho 79k 1 chia hết cho105. 5 Xét 105 1 số: 79; 792; 793; 794; ; 7910 1 . Tất cả các số này đều không chia hết cho 105 nên nếu lấy 105 1 số này chia cho số 105 thì theo nguyên lý Dirichlet tồn tại hai số có cùng số dư trong phép chia cho 105 . Khi đó hiệu của chúng chia hết cho 105 . Giả sử hai số đó là 79m và 79n m,n N; 1 n m 105 1 . Ta có 79m 79n 105 hay 79n 79m n 1 105. Vì 79n;105 1 nên 79m n 1 105 Ta chọn m n k lúc đó 79k chia cho 105 dư 1 tức là 79k có chữ số tận cùng là 00001 (đpcm). Ví dụ 9: Để chuẩn bị cho buổi sinh hoạt câu lạc bộ toán của khối 7 của một trường THCS, 6 bạn học sinh giỏi toán của 6 lớp 7A, 7B, 7C, 7D, 7E, 7G viết thư trao đổi với nhau về hai nội dung: (I): “Thống kê” và (II): “Biểu thức đại số”. Biết rằng mỗi bạn đều viết thư cho 5 bạn còn lại (trong các bạn nói trên) về một trong hai nội dung trên. Chứng minh rằng có ít nhất 3 bạn cùng trao đổi với nhau về một nội dung.  Tìm cách giải: Ta gọi 6 học sinh giỏi toán (ta coi là 6 “thỏ”) của 6 lớp lần lượt là A, B, C, D, E, G. Giả sử một bạn nào đó A chẳng hạn viết thư cho 5 bạn còn lại về mỗi bạn một trong hai nội dung “Thống kê” và “Biểu thức đại số”. Ta thành lập các “lồng” bằng cách sau đây: - “Lồng I” nhốt những ai trao đổi với A về nội dung (I). - “Lồng II” nhốt những ai trao đổi với A về nội dung (II). Trang 5
6. Như vậy sẽ có 5 thỏ nhốt vào “2 lồng”. Theo nguyên lí Dirichlet phải có một lồng nhốt không ít hơn 3 “thỏ”, nghĩa là phải có ít nhất 3 bạn nào đó trong số 5 bạn (không kể A) cùng trao đổi với A về một trong hai nội dung trên. Không mất tổng quát ta có thể giả sử 3 bạn cùng trao đổi với A về nội dung (I). + Trong ba bạn đó nếu có hai bạn nào đó trao đổi với nhau về nội dung (I) thì hai bạn đó với A tạo thành 3 bạn cùng trao đổi với nhau về một nội dung. + Nếu trong ba bạn đó nếu có không có hai bạn nào trao đổi với nhau về nội dung (I) thì ba bạn đó chỉ có thể trao đổi với nhau về nội dung (II). Bài toán cũng được chứng minh. Ta trình bày lời giải như sau: Giải Ta gọi 6 học sinh giỏi toán của 6 lớp lần lượt là A, B, C, D, E, G. Giả sử một bạn nào đó A chẳng hạn viết thư cho 5 bạn còn lại về hai nội dung (I) và (II). Ta có 5 2.2 1 . Theo nguyên lí Dirichlet A phải viết cho ít nhất 3 bạn về một nội dung, không mất tổng quát ta giả sử 3 bạn đó là B, C, D và nội dung trao đổi là (I). + Trong ba bạn B, C, D nếu có hai bạn nào đó trao đổi với nhau về nội dung (I) chẳng hạn B và C thì hai bạn B và C với A tạo thành 3 bạn cùng trao đổi với nhau về một nội dung. + Nếu trong ba bạn B, C, D đó nếu có không có hai bạn nào trao đổi với nhau về nội dung (I) thì ba bạn đó chỉ có thể trao đổi với nhau về nội dung (II) tạo thành 3 bạn cùng trao đổi với nhau về một nội dung. Bài toán cũng được chứng minh. Tóm lại dù khả năng nào xảy ra ta luôn có ít nhất 3 bạn cùng trao đổi với nhau về một nội dung. C. Bài tập vận dụng 19.1. Một tổ có 12 học sinh, trong một giờ kiểm tra Toán ngoài 2 bạn An và Bình đạt điểm 10 còn lại các bạn khác đạt số điểm thấp hơn nhưng không bạn nào bị điểm 0; 1; 2 (điểm số của các bạn đều là số tự nhiên). Chứng minh ngoài hai bạn đạt điểm 10 còn ít nhất có hai bạn có điểm số như nhau. 19.2. Một lớp học có 37 học sinh cùng tuổi. Chứng minh rằng trong năm có một tháng ít nhất 4 học sinh cùng tổ chức sinh nhật. 19.3. Một vòng chung kết bóng bàn có 8 đấu thủ tham gia thi đấu vòng tròn nghĩa là mỗi đấu thủ đều phải gặp 7 đấu thủ còn lại. Chứng minh trong mọi thời điểm giữa các cuộc đấu bao giờ cũng có hai đấu thủ đã đấu một số trận như nhau. 19.4. Chứng minh rằng trong 5 người bất kỳ ít ra cũng có 2 người có cùng số người quen như nhau trong 5 người đó. Hãy tổng quát hóa bài toán! 19.5. 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. Trang 6
7. 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. 19.6. Chứng minh rằng trong 2016 số tự nhiên bất kỳ tồn tại hai số có hiệu chia hết cho 2015. 19.7. Chứng minh rằng trong n số tự nhiên liên tiếp luôn tìm được một số chia hết cho n. 19.8. Trong n số tự nhiên bất kỳ a1; a2; ; an luôn tìm được một số chia hết cho n hoặc hai số có hiệu chia hết cho n. 19.9. Chứng minh rằng trong ba số lẻ bất kỳ bao giờ cũng tìm được hai số có tổng hoặc hiệu chia hết cho 8. 19.10. Chứng minh rằng luôn tìm được số có dạng 19741974 19740000 0000 chia hết cho 1975. 19.11. Tồn tại hay không một số có dạng 20162016 20162016 chia hết cho 2017. 19.12. Chứng minh rằng trong 20 số tự nhiên liên tiếp bất kỳ ta luôn tìm được một số mà tổng các chữ số của nó chia hết cho 10. 19.13. a) Cho 1001 số nguyên dương khác nhau nhỏ hơn 2000. Chứng minh rằng ta có thể chọn ra 3 số mà một số bằng tổng của hai số còn lại. b) Hãy tổng quát hóa bài toán và chứng minh. 19.14. Chứng minh rằng trong 52 số tự nhiên tùy ý luôn tồn tại hai số sao cho tổng hoặc hiệu của chúng chia hết cho 100. 19.15. Có 17 nhà khoa học viết thư cho nhau trao đổi về ba đề tài: “Biến đổi khí hậu”; “Môi trường”; “Dân số”. Mỗi người viết thư cho một người về một đề tài. Chứng minh rằng ít nhất cũng có 3 nhà khoa học trao đổi với nhau về cùng một đề tài. (Chú ý: Bài toán trên có thể diễn đạt cách khác theo ngôn ngữ hình học như sau: “Cho 17 điểm phân biệt nằm trên một đường tròn Hai điểm bất kì trong 17 điểm này đều được nối bằng một đoạn màu xanh, màu đỏ hoặc màu vàng. Chứng minh luôn tồn tại ít nhất một tam giác có ba cạnh cùng màu”). 19.16. Cho dãy số 101; 102; 103; 104; ; 1020 . Chứng minh rằng có một số trong dãy số ấy chia cho 19 thì dư 1. (Thi chọn học sinh giỏi lớp 9. Quận 10. TP Hồ Chí Minh, năm học 2005 – 2006) 19.17. Cho X là một tập hợp gồm 700 số nguyên dương đôi một khác nhau mỗi số không lớn hơn 2006. Chứng minh rằng trong tập hợp X luôn tìm được hai phần tử x, y sao cho x y thuộc tập hợp E 3;6;9. (Đề thi vào khối THPT Chuyên, Đại học Sư phạm Hà Nội, Trang 7
8. năm học 2006 – 2007) 19.18. Cho lưới ô vuông 5 5 . Người ta điền vào mỗi ô một trong các số 1; 0; 1 . Xét tổng các số được tính theo hàng, theo cột 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. (Thi vào lớp 10 THPT chuyên Toán Thành phố Hà Nội, năm học 2007 – 2008) 19.19. Trên một đường tròn cho 6 điểm phân biệt. Hai điểm bất kỳ trong 6 điểm này đều được nối bằng một đoạn màu xanh hoặc màu đỏ. Chứng minh rằng tồn tại một tam giác có ba cạnh cùng màu. (Đề thi chọn học sinh giỏi lớp 9, Thanh Hóa, năm học 2009 -2010) 19.20. 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. (Đề thi chọn học sinh giỏi lớp 9, Vĩnh Phúc, năm học 2009 – 2010) Trang 8
9. HƯỚNG DẪN GIẢI – ĐÁP SỐ 19.1. Trừ hai bạn đạt điểm 10 còn lại 10 bạn đạt 7 loại điểm 3; 4; 5; 6; 7; 8; 9. Giả sử trong số đó không có ít nhất hai bạn nào có số điểm giống nhau thì mỗi loại điểm chỉ nhiều nhất có một bạn đạt nên tổ còn lại nhiều nhất 7 bạn. Vô lý. 19.2. Một năm có 12 tháng. Giả sử trong năm không có một tháng nào có ít nhất 4 học sinh cùng tổ chức sinh nhật, thì một tháng nhiều nhất có 3 học sinh tổ chức sinh nhật. Số học sinh của lớp nhiều nhất là 21.3 36 37 . Vô lý. 19.3. Số trận đấu của mỗi đấu thủ với các đấu thủ khác gồm 8 loại là 0; 1; 2; 3; 4; 5; 6; 7. Các số 0 và 7 không đồng thời tồn tại vì nếu có 1 ai chưa đấu trận nào thì không ai đấu đủ 7 trận. Nếu đã có một người đấu đủ 7 trận thì không ai chưa đấu trận nào. Có 8 đấu thủ, có 7 loại số trận đấu do đó phải tồn tại ít nhất hai đấu thủ có số trận đấu như nhau ở mọi thời điểm giữa các cuộc đấu. 19.4. Giả sử trong số 5 người có một người không quen với tất cả những người còn lại thì mỗi người còn lại không ai có thể có số người quen quá 3 người. Số người quen chỉ có thể có các loại 0; 1; 2; 3. Có 5 người (5 thỏ) mà chỉ có 4 loại số người quen (4 lồng). Theo nguyên lý Dirichlet tồn tại ít nhất hai người có số người quen như nhau trong 5 người đó. Giả sử trong số 5 người có một người quen với tất cả những người còn lại thì mỗi người còn lại có số người quen chỉ có thể là 1; 2; 3; 4. Có 5 người (5 thỏ) mà chỉ có 4 loại số người quen (4 lồng). Theo nguyên lý Dirichlet tồn tại ít nhất hai người có số người quen như nhau trong 5 người đó. Tổng quát: Một phòng họp có n người, bao giờ cũng có ít nhất 2 người có số người quen như nhau trong số n người đó. 19.5. 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. 19.6. Chia một số cho 2015 ta nhận được một trong 2015 số dư: 0; 1; 2; ; 2013; 2014. Có 2016 số tự nhiên bất kỳ nên theo nguyên lý Dirichlet tồn tại 2 số có cùng số dư khi chia cho 2015 hiệu của hai số chia hết cho 2015. Trang 9
10. 19.7. Giả sử không tìm được số nào trong n số tự nhiên liên tiếp đã cho mà chia hết cho n. Khi đó n số này chia cho n chỉ nhận được nhiều nhất là n 1 số dư khác nhau 1; 2; 3; 4; ; n 1 , theo nguyên lý Dirichlet tồn tại hai số chia cho n có cùng số dư, chẳng hạn là a và b với a b , khi đó số a b chia hết cho n. Điều này mâu thuẫn với 0 a b n . Từ đó suy ra điều phải chứng minh. 19.8. Nếu một trong n số chia hết cho n, bài toán được chứng minh. Nếu tất cả n số không có số nào chia hết cho n thì khi chia cho n chúng nhận n 1 số dư 1; 2; 3; ; n 2; n 1. Có n số, có nsố dư1 nên theo nguyên lý Dirichlet tồn tại 2 số có cùng số dư khi chia cho n hiệu của hai số chia hết cho n. 19.9. Một số lẻ khi chia cho 8 sẽ có số dư là 1; 3; 5 hoặc 7. Ta chia các số dư này thành hai nhóm: Nhóm 1 là (1; 7) nhóm 2 là (3; 5). Có ba số lẻ chia cho 8 mà có hai nhóm số dư, theo nguyên lý Diriclet tồn tại hai số có số dư khi chia cho 8 vào cùng một nhóm. Nếu hai số dư giống nhau thì hiệu của hai số chia hết cho 8. Nếu hai số dư khác nhau thì tổng của chúng chia hết cho 8. Vậy trong ba số lẻ bất kỳ bao giờ cũng tìm được hai số có tổng hoặc hiệu chia hết cho 8. 19.10. Xét 1975 số có dạng sau: A1 1974 A2 19741974 A3 197419741974 A1974 19741974 1974 1974 soá 1974 A1975 19741974 19741974 1975 soá 1974 Tất cả 1975 số này đều không chia hết cho 5 nên không chia hết cho 1975. Do đó mỗi số khi chia cho 1975 nhận một trong 1974 số dư 1; 2; 3; ; 1974. Do đó theo nguyên lý Dirichlet tồn tại hai số có cùng số dư khi chia cho 1975 nghĩa là hiệu của chúng chia hết cho 1975. Giả sử đó là Ai 19741974 19741974 và Ak 19741974 19741974 i soá 1974 k soá 1974 i k; i,k 1;2; ;1975 hiệu của chúng sẽ là: Ai Ak 19741974 19741974 19741974 19741974 i soá 1974 k soá 1974 19741974 19740000 .00001975. (đpcm) i k soá 1974: 4k soá 0 19.11. Xét 2017 số có dạng Trang 10
11. B1 2016 B2 20162016 B3 20162016 B2017 20162016 20162016 2017 soá 2016 Nếu một trong số 2017 số này chia hết cho 2017 ta có số cần tìm. Nếu 2017 số này đều không chia hết cho 2017 thì tương tự bài trên ta có số Bi Bk 20162016 20160000 .0000 i k; i,k 1;2; ;2017 i k soá 2016: 4k soá 0 4k 4k 20162016 2016.10 2017 . Do 10 2017 i k soá 2016 Nên 20162016 20162017. i k soá 2016 Vậy tồn tại một số có dạng 20162016 20162016 chia hết cho 2017. 19.12. Trong 20 số tự nhiên liên tiếp bất kỳ bao giờ cũng tìm được 10 số tự nhiên liên tiếp có chữ số hàng chục giống nhau còn chữ số hàng đơn vị là 0; 1; 2; 3; 4; 5; 6; 7; 8; 9. Viết các số đó dưới dạng: ab c0 ; ab c1; ab c2; ; ab c9 . Gọi tổng các chữ số là S a b c thì các số vừa viết có tổng các chữ số S;S 1;S 2 : : S 9 là 10 số tự nhiên liên tiếp do đó có 1 số chia hết cho 10. 19.13. a) Gọi 1001 số nguyên dương khác nhau đã cho là a1;a2;a3; ;a1001 với a1 a2 a3 a1001 2000. Đặt A a2;a3; ;a1001 gồm 1000 phần tử có dạng am với m 2;3; ;1001 và B a2 a1;a3 a1; ;a1001 a1 gồm 1000 phần tử có dạng an a1 với n 2;3; ;1001. Ta thấy các phần tử của hai tập hợp A và B đều thuộc tập hợp gồm 1999 phần tử 1;2;3; ;1998;1999  trong khi tổng số các phần tử của tập A và B là 1000 1000 2000 phần tử. Theo nguyên lý Dirichlet tồn tại hai số bằng nhau mà chúng không thể thuộc cùng một tập hợp, nên có một số thuộc tập hợp A, một số thuộc tập hợp B tức là am an a1 do đó an am a1 . Ba số am ;an;a 1đôi một khác nhau. Thật vậy am a1;an a1 theo cách đặt các tập hợp A và B, còn am an vì nếu am an thì a1 0 , trái với giả thiết của bài toán. Vậy tồn tại ba số an;am ;a1 trong các số đã cho mà an am a1. b) Tổng quát hóa: Cho n 1 số nguyên dương khác nhau nhỏ hơn 2n. Chứng minh rằng ta có thể chọn ra 3 số mà một số bằng tổng của hai số còn lại. (Chứng minh tương tự như câu a). (Bạn đọc tự chứng minh). Trang 11
12. 19.14. Một số tự nhiên chia cho 100 có 1 trong các số dư 0; 1; 2; ; 98; 99. Tất cả các số dư trong phép chia cho 100 được chia thành 51 nhóm sau: (0); (1;99); (2; 98); (3; 97); ; (49; 51); (50) Đem 52 số tự nhiên chia cho 100 nhận được 52 số dư; 52 số dư này thuộc 51 nhóm trên. Theo nguyên lý Dirichlet tồn tại ít nhất hai số dư thuộc vào một nhóm, tức là tồn tại hai số có tổng số dư trong phép chia cho 100 bằng 100 hoặc hiệu số dư trong phép chia cho 100 bằng 0. Hai số này có tổng hoặc hiệu chia hết cho 100. 19.15. Giả sử A là 1 trong 17 nhà khoa học. A phải trao đổi với 16 nhà khoa học còn lại về 3 đề tại. Theo nguyên lý Dirichlet thì A phải trao đổi với ít nhất 6 nhà khoa học khác về cùng một đề tài chẳng hạn “Dân số”. Gọi 6 nhà khoa học khác cùng một đề tài chẳng hạn “Dân số” với A là B; C; D; E; F; G. + Nếu 2 trong 6 nhà khoa học trao đổi với nhau về đề tài “Dân số” thì bài toán được chứng minh vì khi ấy 2 trong 6 nhà khoa học cùng với A trao đổi với nhau về cùng một đề tài “Dân số”. + Nếu tất cả 6 nhà khoa học B; C; D; E; F; G. không ai trao đổi với nhau về đề tài “Dân số” thì họ chỉ còn trao đổi với nhau về hai đề tài “Biến đổi khí hậu”; “Môi trường”. Xét nhà khoa học B trong 6 nhà khoa học trên. B phải trao đổi với 5 người còn lại về hai đề tài “Biến đổi khí hậu”; “Môi trường”. Theo nguyên lý Dirichlet B phải trao đổi với ít nhất 3 nhà khoa học khác chẳng hạn C; D; E về cùng một đề tài chẳng hạn “Môi trường”. Nếu C; D; E có hai người chẳng hạn D và E trao đổi với nhau về cùng đề tài “Môi trường” thì B; E; D chính là ba người cùng trao đổi với nhau về một đề tài. Nếu C; D; E không có ai trao đổi với nhau về cùng đề tài “Môi trường” thì C; D; E chỉ còn một đề tài duy nhất là “Biến đổi khí hậu”; để trao đổi. Vậy ta có ba người cùng trao đổi với nhau về một đề tài. Vậy trong mọi trường hợp ta luôn có ít nhất 3 nhà khoa học trao đổi với nhau về cùng một đề tài. 19.16. Xét dãy số 101; 102; 103; 104; ;1020 có 20 số nên khi chia mỗi số trong dãy cho 19 ta nhận được 1 trong 19 số dư r 0; 1; 2; 3; ; 17; 18. Theo nguyên lý Dirichlet tồn tại ít nhất hai số có cùng số dư khi chia cho 19. Không mất tổng quát giả sử hai số đó là 10a và 10b (a,b N * và b a 20 ) khi đó 10a 10b 10b. 10a b 1 19 . Mà 10b;19 1 nên 10a b 1 19 hay 10a b 19 dư 1 và 1 a b 19 . Ta có điều phải chứng minh. 19.17. Gọi 700 số nguyên dương đôi một khác nhau đã cho là a1; a2; a3; ;a700 . Như vậy X a1; a2; a3; ; a700 . Xét 700.4 2800 số sau đây: a1; a2; a3; ;a700; a1 3; a2 3; a3 3; ; a700 3; a1 6; a2 6; a3 6; ; a700 6;a1 9; a2 9; a3 9; ; a700 9; Do mỗi số không lớn hơn 2006 nên mỗi số trên đều không lớn hơn: 2006 9 2015 . Có 2800 số mà mỗi số nhận giá trị từ 1 đến không quá 2015. Theo theo nguyên lý Dirichlet phải tồn tại ít nhất hai số bằng nhau. Giả sử đó là 2 số ai 9 ak 3 với (i;k 1;2;3; ;700. Trang 12
13. Khi ấy ak ai x y 9 3 6. (Tương tự nếu có số ai 6 ak 3 ta có x y 3; ai 9 ak ta có x y 9 ). Suy ra tồn tại hai phần tử x, y X sao cho x y thuộc tập hợp E 3;6;9. 19.18. Tổng số có 12 tổng đó là: 5 tổng theo hàng; 5 tổng theo cột và 2 tổng theo đường chéo. Vì mỗi tổng có 5 số hạng chỉ gồm 3 số là 1;0;1 nên mỗi tổng chỉ nhận không quá 11 giá trị 5; 4; 3; 2; 1;0;1;2;3;4;5. Do đó theo nguyên lý Dirichlet tồn tại ít nhất hai tổng có giá trị bằng nhau. 19.19. Giả sử 6 điểm phân biệt trên đường tròn là A, B, C, D, E, G. Từ 1 điểm nối với 5 điểm còn lại được 5 đoạn thẳng với 2 màu xanh hoặc đỏ. Theo nguyên lý Dirichlet tồn tại ít nhất ba đoạn thẳng cùng màu. Không mất tổng quát, giả sử ba đoạn thẳng AB, AC, AD cùng màu đỏ (nếu màu xanh lập luận tương tự). Xét BCD nếu có một cạnh chẳng hạn BC màu đỏ thì ABC có ba cạnh màu đỏ. Trái lại thì BCD sẽ có ba cạnh màu xanh. Vậy luôn tồn tại một tam giác có ba cạnh cùng màu. 19.20. 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 13