Tài liệu “nguyên lý dirichlet và các bài toán suy luận”

PHÒNG GIÁO DỤC - ĐÀO TẠO GIAO THUỶ TRƯỜNG THCS GIAO THỦY ---------------------------------- BÁO CÁO SÁNG KIẾN NGUYÊN LÝ DIRICHLET VÀ CÁC BÀI TOÁN SUY LUẬN Tác giả: Tô Thị Bình Trình độ chuyên môn: Đại học sư phạm Toán Chức vụ: Giáo viên Nơi công tác: Trường THCS Giao Thủy Nam Định, ngày 30 tháng 06 năm 2015 trang 1 1. Tên sáng kiến “NGUYÊN LÝ DIRICHLET VÀ CÁC BÀI TOÁN SUY LUẬN” 2. Lĩnh vực áp dụng sáng kiến : Giáo dục. 3. Thời gian áp dụng sáng kiến : Từ năm học 2012 - 2013 đến nay. 4. Tác giả : Họ và tên : Tô Thị Bình Năm sinh : 1983 Nơi thường trú : Xóm 1 - Bình Hòa - Giao Thủy - Nam Định. Trình độ chuyên môn : Đại học sư phạm Toán. Chức vụ : Giáo viên Nơi làm việc : Trường THCS Giao Thủy - Giao Thủy - Nam Định Địa chỉ : Trường THCS Giao Thủy - Giao Thủy - Nam Định Điện thoại : 03503 508 486 5. Đơn vị áp dụng sáng kiến : Tên đơn vị : Trường THCS Giao Thủy - Giao Thủy - Nam Định . Địa chỉ : Khu 4A TT Ngô Đồng - Giao Thủy - Nam Định. Điện thoại : 03503 737 456. BÁO CÁO SÁNG KIẾN trang 2 “NGUYÊN LÝ DIRICHLET VÀ CÁC BÀI TOÁN SUY LUẬN” A- ĐIỀU KIỆN HOÀN CẢNH TẠO RA SÁNG KIẾN: Qua những năm giảng dạy tôi nhận thấy, bên cạnh việc cung cấp hệ thống kiến thức và các kĩ năng cơ bản cho học sinh, người thầy cần tìm tòi, khai thác hệ thống kiến thức nâng cao nhằm bồi dưỡng phát triển tư duy suy luận Toán học cho học sinh năng khiếu với mong muốn các em sẽ trở thành chủ nhân tương lai có khả năng tư duy nhạy bén, linh hoạt, sáng tạo, có độ tin cậy cao nhằm đáp ứng được yêu cầu ngày càng cao của nền kinh tế trong thời đại công nghiệp hiện đại. Với mong muốn được góp một phần công sức nhỏ nhoi của mình trong việc bồi dưỡng học sinh giỏi và cũng nhằm rèn luyện khả năng sáng tạo trong học toán cho học sinh để các em có thể tự phát huy năng lực độc lập sáng tạo của mình, nhằm góp phần vào công tác chăm lo bồi dưỡng đội ngũ HSG toán của ngành giáo dục huyện nhà. Tôi xin được chia sẻ và trao đổi cùng đồng nghiệp kinh nghiệm: “Nguyên lý Dirichlet và các bài toán suy luận”. Như chúng ta đã biết nguyên lý Dirichlet có nội dung khá đơn giản song nó lại là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của Toán học. Nguyên lí này trong nhiều trường hợp người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm vật cụ thể, nhưng trong thực tế nhiều bài toán ta chỉ cần chỉ ra sự tồn tại là đủ rồi. Nó có nhiều ứng dụng trong nhiều lĩnh vực lại có thể áp dụng rộng rãi trong việc chứng minh các bài toán số học, hình học, đại số,…Đặc biệt đối với các bài toán khó dành cho học sinh giỏi và thi vào 10 chuyên Toán, hay các kì thi IMO cũng như các kì thi toán học trên thế giới. Đề tài này ta có thể bồi dưỡng năng lực học toán cho học sinh và cũng có thể dùng nó trong việc dạy ôn thi vào các trường THPT chuyên. Mong quý đồng nghiệp cùng đóng góp ý kiến để sáng kiến kinh nghiệm được hoàn thiện hơn. B. MÔ TẢ GIẢI PHÁP: I. Mô tả giải pháp trước khi tạo ra sáng kiến: Năm học 2011 – 2012, tôi được phân công dạy đội tuyển học sinh giỏi môn Toán cấp Tỉnh. Là một giáo viên tuổi nghề còn ít do đó tôi đã gặp không ít những khó khăn trong công tác bồi dưỡng học sinh giỏi, phần nào cũng ảnh hưởng tới chất lượng đội tuyển (có 1 học sinh đạt giải nhì, 3 học sinh đạt khuyến khích – xếp chung đội tuyển: 10/10). Sau một năm dạy đội tuyển, cũng phần nào “vỡ vạc” công việc của mình, luôn trăn trở và tôi nhận thấy rằng: học sinh mình trang 3 không đạt nhiều giải cao, phải chăng học sinh mình chỉ là những con ong chăm chỉ, quen với tư duy lối mòn: giải các bài toán dạng cơ bản và chuẩn mực, khả năng khải quát, tư duy ở cấp độ cao còn hạn chế? Năm học 2012 – 2013, tôi đã thay đổi nội dung và phương pháp dạy đội tuyển. Khi học sinh đã quen với những dạng toán chuẩn mực, cơ bản tôi đã đưa cho học sinh những bài toán phức tạp hơn mà sau khi đọc xong nội dung, học sinh không có một định hướng nào cả. Sau đó tôi còn cho cả lời giải, học sinh xem xong cũng không hiểu tại sao lại có những suy luận như vậy mà trong sách giáo khoa chưa đề cập đến (kể cả trong một số bài, lời giải có sử dụng một vài khẳng định tuy rất hiển nhiên nhưng học sinh lại chưa hề biết đến). Những bài toán như thế thường được coi là dạng Toán không mẫu mực. Đó những dạng toán khó thường xuất hiện ở kì thi chọn học sinh giỏi hay thi vào 10 chuyên Toán. Từ năm học 2012 – 2013 trở đi, trong công tác bồi dưỡng học sinh giỏi tôi đã giành nhiều thời gian và chú trọng ở dạng toán suy luận. Trong khuôn khổ bài viết này, tôi xin được trình bày phần nhỏ của dạng Toán này, đó là “Nguyên lý Dirichlet và các bài toán suy luận” II. Mô tả giải pháp sau khi có sáng kiến: Các bài toán suy luận lôgic sử dụng nguyên lý Dirichlet thường không đòi hỏi nhiều về kĩ năng tính toán. Để giải chúng, điều cần thiết hơn cả là phải có phương pháp suy luận đúng đắn, chặt chẽ, hợp lí và sáng tạo. Trong khuôn khổ thời gian có hạn, tôi xin được trình bày một số vấn đề thường gặp trong thi học sinh giỏi và thi vào THPT chuyên. Phần thứ nhất: Giới thiệu về nhà Toán học Dirichlet 1. Vài nét về tiểu sử nhà toán học Dirichlet. Nhà toán học người Đức Dirichlet là học trò của Gauss là người rất hâm mộ Gauss. Nhờ giỏi tiếng Pháp, ông đóng vai trò quan trọng trong việc giao lưu tư tưởng giửa hai phía của sông Rhin. Trong thời gian học ở Pari, giữa 1822 và 1825, ông làm gia sư trong gia đình của tướng và nhà chính trị Maximilien Foy. Trong thời gian này, ông tham gia nhà bác học trẻ, quây quần xung quanh Fourier. Vì vậy ông gắn bó với Fourier và… với các chuỗi lượng giác. Từ 1826 đến 1828, Dirichlet là giảng viên trường Đại Học Breslau. Từ 1829 ông làm việc ở trường Đại họcBerlin. Từ 1931 đến 1855 ông là giáo sư trường Đại họcBerlin. Từ 1855, sau khi Gauss qua đời, ông kế tục Gauss ở trường Đại học Gôttinggen. trang 4 Dirichlet là một người khiêm tốn trung thực và nhân ái. Nhưng, khác với vợ ông là Jacobi, Dirichlet không xuất sắc về mặt sư phạm. Mặc dù vậy, các bài giảng của ông có ảnh hưởng lớn đến các nhà toán học thuộc thế hệ sau như:Riemann, Eisenstein, Kronecker, Dedekin… Sau khi Dirichlet qua đời, bộ óc của ông được bảo quả tại khoa sinh lý học Trường Đại Học Gôttingen. Dirichlet có những phát minh lớn trong lí thuyết số. Ông thiết lập các công thức cho cho số các lớp dạng toàn phương hai ngôi với định thức cho trước. Ông chứng minh định lý về tập hợp vô hạn các số nguyên tố trong một cấp số cộng gồm những số nguyên mà số hạng đầu và công sai là nguyên tố cùng nhau. Để giải các bài toán trên, ông sử dụng những hàm giải tích, gọi là hàm (chuỗi) Dirichlet. Ông sáng lập ra lý thuyết tổng quát về các đơn vị đại số trong một trường số đại số. Về giải tích, Dirichlet là một trong những người đầu tiên quan niệm hàm là sự cho ứng với mọi x một phần tử y, mà không cần phải có biểu thức của y theo x bằng các phép tính số học. Dirichlet cũng là người đầu tiên đề xuất và nghiên cứu khái niệm hội tụ có điều kiện của chuỗi. Ông phát biểu và chứng minh những điều kiện đủ, thường gọi là điều kiện Dirichlet, để chuỗi Fourier của một hàm số hội tụ tới hàm số đó. Dirichlet cũng có những công trình đáng kể về cơ học và vật lý toán, đặc biệt về lý thuyết thế. 2. Các công trình toán học của Dirichlet. Những đóng góp của Dirichlet đến toán học. Đóng góp của ông vào Định lý Fermat được thực hiện cuối năm 1825. Khoảng thời gian này, ông cũng xuất bản một bản giấy lấy cảm hứng từ Gauss 's làm việc trên quy luật trùng phương. Năm 1837, ông đã chứng minh được với một cấp số cộng có dạng an + b, Cho n = 1, 2, ..., chứa vô hạn các số nguyên tố , a và b là nguyên tố cùng nhau , tức là (a,b) = 1. Kết quả này đã được phỏng đoán bởi Gauss (Derbyshire năm 2004, p. 96), nhưng lần đầu tiên được chứng minh bởi Dirichlet (1837). Phân tích lý thuyết số có thể cho biết để bắt đầu với công việc của Dirichlet, và đặc biệt với cuốn hồi ký của 1.837 Dirichlet về sự tồn tại của số nguyên tố trong một cấp số cộng nhất định. Ngay sau khi tác phẩm này được xuất bản giấy, Dirichlet đã thêm về lý thuyết số phân tích, một trong năm 1838 với sự tiếp theo trong năm sau. Những trang 5 giấy tờ giới thiệu loạt Dirichlet và xác định, trong số những thứ khác, công thức cho số lớp học cho các hình thức bậc hai. Tác phẩm của ông về các đơn vị trong số đại số lý thuyết über Vorlesungen Zahlentheorie (xuất bản 1863) có công việc quan trọng về lý tưởng. Ông cũng đề nghị năm 1837 định nghĩa hiện đại của một hàm: Nếu một y biến như vậy là liên quan đến một biến x rằng bất cứ khi nào một số giá trị được gán cho x, có một quy tắc theo đó một giá trị duy nhất của y được xác định, sau đó y được gọi là một chức năng của x. biến độc lập Trong cơ khí, ông điều tra các trạng thái cân bằng của hệ thống và lý thuyết tiềm năng. Những điều tra đã bắt đầu vào năm 1839 với giấy tờ mà đã cho phương pháp để đánh giá tích phân nhiều và ông này áp dụng cho vấn đề của việc thu hút hấp dẫn của một ellipsoid trên điểm cả hai bên trong và bên ngoài. Ông quay sang Laplace 's vấn đề chứng minh sự ổn định của hệ thống năng lượng mặt trời và sản xuất phân tích mà tránh được vấn đề của việc sử dụng mở rộng loạt với các thuật ngữ bậc hai và cao hơn disregarded. Công việc này đã dẫn ông đến các vấn đề liên quan đến chức năng Dirichlet hài hòa với điều kiện biên nhất định. Một số hoạt động trên cơ học sau này trong sự nghiệp của mình là có tầm quan trọng khá nổi bật. Năm 1852, ông nghiên cứu các vấn đề của một mặt cầu đặt trong một chất lỏng incompressible, trong quá trình điều tra này trở thành người đầu tiên tích hợp các phương trình Thủy động lực học chính xác. Dirichlet cũng nổi tiếng với những tác phẩm của ông về điều kiện cho sự hội tụ của chuỗi lượng giác. Những chuỗi đã được sử dụng trước đây của Fourier trong giải phương trình vi phân. Tác phẩm của Dirichlet được xuất bản trong Tạp chí Crelle của năm 1828. Bởi vì điều này làm việc Dirichlet được coi là người sáng lập ra học thuyết của Fourier series. Riemann, một sinh viên của Dirichlet , đã viết trong phần giới thiệu cho luận án của mình trên Habilitation Chuỗi Fourier rằng nó đã được Dirichlet: “ ... người học giả đầu tiên sâu sắc về chủ đề này”. Nhân vật Dirichlet và chất lượng giảng dạy được tóm tắt như sau: “Ông là một giáo viên giỏi, luôn luôn thể hiện mình với độ rõ nét tuyệt vời. Lần theo cách của ông đã được khiêm tốn; trong những năm sau đó ông đã được nhút nhát và lúc reserved. Ông ít khi phát biểu tại cuộc họp và đã miễn cưỡng để làm xuất hiện công khai”. Ở tuổi 45 Dirichlet được Thomas Hirst miêu tả như sau: trang 6 “Ông là khá cao, lanky-tim người đàn ông, với bộ râu ria và về để biến màu xám với một giọng nói hơi thô và thay điếc. Ông đã không có tắm rửa, với ly cà phê của mình và xì gà. Một trong những thiếu sót của mình là quên thời gian, ông đã kéo mình ra xem, thấy ba vừa qua, và chạy ra mà không hề kết thúc câu”. Koch viết về sự đóng góp của Dirichlet như sau: “... phần quan trọng của toán học bị ảnh hưởng bởi Dirichlet. Chứng minh của ông characteristically bắt đầu với các quan sát đáng ngạc nhiên đơn giản, tiếp theo là phân tích cực kỳ sắc nét của vấn đề còn lại…”. Phần thứ hai: Nguyên lý Dirichlet 1.Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle)-hoặc nguyên ý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật vào ngăn kéo (The Drawer Principle) - đưa ra một nguyên tắc về phân chia phần tử các lớp. Nguyên lí này được Dirichlet phát biểu đầu tiên năm 1834. Nguyên lý Dirichlet là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của toán học. Nó đặc biệt có nhiều áp dụng trong lĩnh vực khác nhau của toán học. Nguyên lý này trong nhiều trường hợp người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm được vật cụ thể, nhưng trong thực tế nhiều bài toán ta chỉ cần chỉ ra sự tồn tại là đủ rồi. Nội dung của nguyên lí này hết sức đơn giản và dễ hiểu nhưng lại có tác dụng rất lớn, có nhiều hiệu quả bất ngờ trong giải toán. Sử dụng nó, chúng ta có thể chứng minh được nhiều kết quả sâu sắc của Toán học. Đôi khi có những bài toán người ta đã dùng rất nhiều phương pháp khác nhau để giải mà vẫn chưa đi đến được kết quả, nhưng nhờ nguyên lí Dirichlet mà bài toán trở nên dễ dàng giải quyết.  Nguyên lý Dirichlet cơ bản:. Nếu nhốt n + 1con thỏ vào n cái chuồng thì bao giờ cũng có một chuồng chứa ít nhất hai con thỏ.  Nguyên lý Dirichlet tổng quát: Mệnh đề: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp N  chứa ít nhất   đồ vật. k  trang 7 ( với [x] – phần nguyên của x – là số nguyên lớn nhất có giá trị nhỏ hơn hoặc bằng x.) Chứng minh: N  Giả sử mọi hộp đều chứa ít hơn   vật. Khi đó tổng số đồ vật là; k  N  N  k (   - 1) < k   = N. k  k  Điều này mâu thuẩn với giả thiết là có N đồ vật cần xếp.  Nguyên lí Dirichlet mở rộng. Nếu nhốt n con thỏ vào m ≥ 2 cái chuồng thì tồn tại một chuồng có ít nhất  n  m  1  m  con thỏ, ở đây kí hiệu [α] để chỉ phần nguyên của số α. Ta chứng minh nguyên lí Dirichlet mở rộng như sau : Giả sử trái lại mọi chuồngthỏ không có đến  n  m  1   n  1   n  1  m    m  1   m   1  n  1 con, thì số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng  con.  m   n  1  n  1 con  m  Từ đó suy ra tổng số con thỏ không vượt quá m.  Điều này vô lí vì có n con thỏ. Vậy giả thiết phản chứng là sai. Nguyên lí Dirichlet mở rộng được chứng minh.Nguyên lí Dirichlet tưởng chừng đơn giản như vậy, nhưng nó là một công cụ rất hiệu quả dùng để chứng minh nhiều kết quả sâu sắc của toán học. Nó đặc biệt có nhiều áp dụng trong lĩnh vực khác nhau của toán học. Nguyên lí này trong nhiềutrường hợp người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra đượcphương pháp tìm được vật cụ thể, nhưng trong thực tế nhiều bài toán ta chỉ cầnchỉ ra sự tồn tại là đủ rồi.Nguyên lí Dirichlet thực chất là một định lí về tập hữu hạn. Người ta có thểphát biểu chính xác nguyên lí này dưới dạng sau đây. 2. Chú ý: Đề giải bài toán suy luận sử dụng nguyên lý Dirichlet ta cần thực hiện những bước sau: trang 8 Bước 1: Tìm hiểu đề bài, xác định đối tượng của bài toán. Số lượng mỗi đối tượng trong giả thiết của bài toán. Bước 2: Xây dựng thuật giải: - Tiến hành phân chia các đối tượng trong giả thiết của bài toán thành hai tập các đối tượng: A và B. Đây là bước quan trọng nhất của tiến trình giải toán. Việc phân chia như vậy thường dựa trên tính chất của từng loại yếu tố. - Xác định và so sánh số phần tử của mỗi tập hợp, tập hợp nào có số phần tử lớn hơn được chọn làm “thỏ”, tập hợp kia chọn làm “lồng”. Nếu trong bài toán đang xét đó ta chỉ ra được hai tập hợp các đối tượng tương ứng với “thỏ” và “lồng” thì bài toán được giải xong. Để giải các bài toán áp dụng nguyên lý Dirichlet chúng ta cần lưu ý một số điểm sau đây: 1. Khi gặp bài toán về chứng minh sự tồn tại của một hay nhiều đối tượng nào đó, người ta thường dùng một phương pháp thuận lợi là sử dụng nguyên lí Đi-richlê .Các bài toán áp dụng nguyên lý Dirichlet 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 lý Dirichlet 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 lý Dirichlet , nhiều khi ta phải kết hợp với phương pháp chứng minh phản chứng (Phương pháp chứng minh phản chứng: Chứng minh phản chứng là phương pháp chứng minh dựa trên kết quả của mệnh đề logic : A  B  B  A . Nội dung phương pháp này được trình bày như sau: + Chấp nhận giả thiết B (nghĩa là coi B đúng). + Từ giả thiết A và B ta suy ra hai kết quả mâu thuẫn nhau C và C (hoặc một kết quả nào đó mâu thuẫn với một kết quả đã biết). Từ đó suy ra B là sai nên đúng). 4. Khi giải các bài toán mà ta đã biết phải áp dụng nguyên lý Dirichlet hoặc dự đoán sẽ phải dùng nguyên lý 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à thoả mãn các điều kiện : + Số ‘thỏ” phải hiều hơn số chuồng trang 9 + “Thỏ” phải được nhốt hết vào các “chuồng”, nhưng không bắt buộc chuồ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 lý Dirichlet . 6. Khi giải xong các bài toán áp dụng nguyên lý Dirichlet , 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. 3. Ví dụ: Ví dụ 1: Chứng minh rằng trong 11 số tự nhiên bất kỳ luôn tồn tại hai số có hiệu chia hết cho 10 * Phân tích: Xác định được + Thỏ : số tự nhiên (gồm 11 số). + Chuồng : tượng trưng cho tính chất chung : chia hết, cùng số dư cùng chuồng, khác số dư khác chuồng. Số chuồng tính như thế nào? Bằng số thỏ trừ đi 1, tức là 11 – 1 = 10 Một số khi chia cho 10 sẽ có số dư là “ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9”: có 10 số dư. Vậy có 11 số khi chia cho 10 sẽ có ít nhất hai số có cùng số dư khi chia cho 10. * Giải: Một số tự nhiên khi chia cho 10 sẽ có 10 số dư, các số dư lần lượt là: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Vậy có 11 số tự nhiên bất kì khi chia cho 10 sẽ có ít nhất hai số có cùng số dư (theo nguyên lý Dirichlet). Khi đó luôn tồn tại hai số có hiệu chia hết cho 10. Tổng quát: 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ư Ví dụ 2: Cho tứ giác ABCD, dùng ba màu xanh, đỏ, vàng để tô màu các đỉnh của tứ giác. Chứng tỏ rằng có hai đỉnh được tô cùng màu. Phân tích: - Xác định được: + “thỏ” : đỉnh, với số lượng là 4. + “chuồng” : màu, số lượng : 3 . + Dựa vào nguyên lý Dirichlet suy ra điều phải chứng minh. Giải trang 10 Với 4 đỉnh của tứ giác A, B, C, D và 3 màu dùng để tô các đỉnh (xanh, đỏ, vàng) nên theo nguyên lý Dirichlet sẽ có ít nhất hai đỉnh được tô cùng màu. Khai thác: Bài toán trên quả là khá đơn giản nếu chỉ dừng lại ở đó! Ta tiếp tục khai thác bài toán trên như sau: + Nếu chỉ dùng hai màu để tô thì số điểm được tô màu ít nhất là bao nhiêu để chắc chắn có hai điểm được tô cùng màu? + Tổng quát: Nếu số điểm được tô màu là a, số màu dùng để tô là b(a, b là các số tự nhiên khác 0) thì a và b có quan hệ với nhau như thế nào để luôn có ít nhất là bao nhiêu đề chắc chắn có hai điểm được tô cùng màu? + Nếu chỉ dùng hai màu để tô thì số điểm được tô màu ít nhất là bao nhiêu để chắc chắn có ba điểm được tô cùng màu? Tìm mối quan hệ giữa a và b trong trường hợp này? Trên đây là hai ví dụ đơn giản nhất, giúp hình thành rõ các bước suy luận. Ta tiếp tục đặt ra các tình huống khó hơn như biết trước “thỏ”, ta phải xác định “lồng” và số “lồng” phù hợp. Ví dụ sau đây trình bày một cách tạo ra “lồng”. Ví dụ 3: 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. Nhận xét: Để làm xuất hiện 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). 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 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): 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 nhất cũng phải có 2 số dư cùng rơi vào một nhóm. trang 11 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) Ví dụ 4: Trong hình vuông cạnh bằng 1, đặt 51 điểm bất kì, phân biệt. Chứng minh rằng có ít nhất 3 trong số 51 điểm đó nằm trong một hình tròn bán kính 1 . 7 * Nhận xét: Ta phải biết cách chia đối tượng lớn thành nhiều đối tượng nhỏ (đối tượng này như là các chuồng). Số thỏ: 51. Số chuồng ở đây là bao nhiêu? Có phải bằng 51 - 1 không? Giải: Chia hình vuông đã cho thành 25 hình vuông con bằng nhau có cạnh bằng 1 .Theo nguyên lý Dirichlet, tồn tại ít nhất một hình vuông con a chứa ít nhất ba 5 điểm trong số 51 điểm đó. Đường tròn ngoại tiếp (a) có bán kính 1 5 2  1 . 7 Vậy ba điểm nói trên nằm trong hình tròn đồng tâm với đường tròn (a) có bán kính 1 . 7 Tổng quát hóa bài toán: Dựa vào bài giải bài toán trên ta có thể tổng quát hóa bài toán trên với a là kích thước của cạnh hình vuông, m là số điểm đặt bất kì, phân biệt. Chứng minh rằng có ít nhất n trong số m điểm đó nằm trong một hình trong bán kính a2  m  . ( trong đó kí hiệu [a] là phần nguyên của a). 2.   n  1  Giải: Chia hình vuông đã cho thành [ m ] hình vuông con bằng nhau có cạnh n 1 a2 bằng  m  . Theo nguyên lí Dirichlet , tồn tại ít nhất một hình vuông con có  n  1  trang 12 chứa ít nhất n điểm trong số m điểm đó. a2 Đường tròn ngoại tiếp (c) có bán kính  m   2.   n  1  a2  m  . 2.   n  1  Vậy n điểm trên nằm trong hình tròn đồng tâm với đường tròn (c) có bán kính a2  m . 2.   n  1  điểm chính giữa của chúng có tọa độ nguyên. Ví dụ 5: Trên mặt phẳng cho 25 điểm. Biết rằng trong ba điểm bất kì trong số đó luôn luôn tồn tại hia điểm cách nhau nhỏ hơn 1. Chứng minh rằng tồn tại hình tròn bán kính 1 chứa không ít hơn 13 điểm đã cho. Giải: Lấy A là một trong số 25 điểm đã cho. Xét hình tròn O1 ( A,1) tâm A bán kính 1. Chỉ có hai khả năng sau có thể xảy ra: 1) Nếu tất cả các điểm đã cho nằm trong O1 ( A,1) thì kết luận của bài toán hiển nhiên đúng. 2) Tồn tại điểm B  A ( B thuộc trong số 25 điểm đã cho), sao cho B  O1 ( A,1) , vì B O1 ( A,1) , nên AB>1. Xét hình tròn O2 ( B,1) tâm B, bán kính 1. Lấy C là điểm bất kì trong số 25 điểm đã cho sao cho C  A, C  B . Theo giả thiết( và dựa vào AB>1), ta có Min{CA, CB}<1. Vì thế C O1 ( A,1) , hoặc C O2 ( B,1) . Điều này chứng tỏ rằng các hình tròn O1 ( A,1) , O2 ( B,1) chứa tất cả 25 điểm đã cho. Vì thế theo nguyên lí Dirichlet, ít nhất 1 trong hai hình tròn trên chứa 13 điểm đã cho. Đó là đpcm. Tổng quát bài tóan : Cho 2n+1 điểm trên mặt phẳng ( với n  3 ) . Biết rằng trong ba điểm bất kì trong số đó luôn luôn tồn tại hai điểm cách nhau nhỏ hơn 1. Khi đó tồn tại hình tròn bán kính 1 chứa không ít hơn n+1 điểm đã cho. Ví dụ 6: 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. trang 13 * Gợi ý: Ở bài này phải biết cách tạo ra “thỏ”, bằng cách lập dãy số : 5 thỏ và tạo ra 4 “lồng” S1 = a1 S2 = a1 + a2 S3 = a1 + a2 + a3 S4 = a1 + a2 + a3 + a4 S5 = a1 + a2 + a3 + a4 + a5 Giải: Ta sẽ thành lập dãy số mới gồm 5 số sau đây: S1 = a1 S2 = a1 + a2 S3 = a1 + a2 + a3 S4 = a1 + a2 + a3 + a4 S5 = 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 minh. - Nếu không có số nào chia hết cho 5 thì khi đem chia các số S i 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 đó. Ví dụ 7: (Bài toán áp dụng 2 lần nguyên tắc Điriclê) 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 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 đề. 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 vấn đề. Như vậy nhà toán học A phải trao đổi ít nhất với 6 nhà toán học về một vấn đề nào đó. Vì nếu chỉ trao đổi với số ít hơn 6 nhà toán học về một vấn đề thì số nhà toán học được trao đổi với A ít hơn 16. (Các bạn có thể diễn tả theo khái niệm "thỏ" và "lồng" để thấy ở trang 14 đây đã áp dụng nguyên tắc Điriclê lần thứ nhất.) - Gọi các nhà toán học trao đổi với nhà toán học A về một vấn đề nào đó (giả sử vấn đề 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 vấn đề (không kể trao đổi với A). Như vậy có 6 nhà toán học A 1, A2, A3, A4, A5, A6 trao đổi với nhau về 3 vấn đề, I, II, III. Có hai khả năng xảy ra: a. Nếu có 2 nhà toán học nào đó cùng trao đổi với nhau về vấn đề I thế thì có 3 nhà toán học (kể cả A) trao đổi với nhau về vấn đề I. Bài toán được chứng minh. 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 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. Ví dụ 8: (Đề thi học sinh giỏi Tỉnh Nam Định năm học 2013 – 2014) Trong một lớp học gồm 35 học sinh có tổ chức một số câu lạc bộ môn học. Biết rằng mỗi học sinh tham gia đúng hai câu lạc bộ và hai học sinh bất kì đều tham gia cùng nhau ít nhất một câu lạc bộ nào đó. Chứng minh tồn tại một câu lạc bộ có không ít hơn 24 học sinh. Giải + Nếu có 1 câu lạc bộ có tất cả 35 học sinh tham gia thì câu lạc bộ đó thỏa mãn bài toán. + Ngược lại, với một câu lạc bộ bất kì luôn tồn tại học sinh không tham gia. Ta kí hiệu học sinh tham gia câu lạc bộ A và B là (A; B). Tồn tại học sinh không tham gia B, học sinh này phải tham gia A, giả sử là (A; C). Vì tồn tại học sinh không tham gia A nên có học sinh khác (A; B) và khác (A; C), học sinh này phải tham gia cả B và C. Vậy ngoài những học sinh (A; B) và (A; C) là học sinh (B; C), hay chỉ tồn tại 3 câu lạc bộ A, B và C. + Có 35 học sinh và mỗi học sinh tham gia đúng 2 câu lạc bộ nên có 70 lượt học sinh tham gia câu lạc bộ. Theo nguyên lí Dirichle tồn tại một câu lạc bộ có  70   3   1  24 không ít hơn học sinh tham gia Ví dụ 9: (ĐHSP Hà Nội 1993) Cho 40 số nguyên dương a1, a2, ...., a19 và b1, b2, ..., b21 sao cho : trang 15 1 ≤ a1 < a2 <....< a19 ≤ 200 và 1 ≤ b1 < b2 <....< b21 ≤ 200 . Chứng minh rằng tồn tại 4 số ai, aj, bk, bp (1 ≤ i, j ≤ 19, 1 ≤ k, p ≤ 21) sao cho a i < aj, bk < bp và aj – ai = bp - bk * Phân tích: Từ điều đề bài yêu cầu, mấu chốt xuất hiện aj – ai = bp - bk, ta sẽ đưa về aj + bk = bp + ai , xét “thỏ”: tổng am + bn, trong đó 1 ≤ m ≤ 19, 1 ≤ n ≤ 21 nên có 399 con thỏ. Chuồng ở đâu? Chuồng nằm ngay ở 399 giá trị nằm từ [2; 400], ta loại trừ 1 giá trị hiển nhiên đúng, còn 399 con thỏ nhốt vào 398 chuồng. * Giải: Xét tổng am + bn, trong đó 1 ≤ m ≤ 19, 1 ≤ n ≤ 21 , sẽ có 19.21 = 399 tổng. Vì 2 ≤ am + bn ≤ 400. + Nếu am + bn đồng thời nhận 2 giá trị là 2 và 400, túc là tồn tại a i , bp sao cho ai + bp = 2 và aj + bk = 400. Suy ra ai = bp = 1 và aj = bk = 200. + Nếu tổng am + bn trong đó 1 ≤ m ≤ 19, 1 ≤ n ≤ 21 không đồng thời nhận hai giá trị là 2 và 400. Vậy suy ra có 399 tổng nhận nhiều nhất là 398 giá trị, theo nguyên lý Dirichlet tồn tại ít nhất hai tổng có cùng giá trị. Gọi hai tổng đó là a j + bk = bp + ai với i < j và p < k, suy ra aj – ai = bp - bk (điều phải chứng minh). Ví dụ 10 : 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 chia 40 học sinh vào 12 tháng đó. Nếu mỗi tháng có không quá 3 học sinh được sinh ra thì số học sinh không quá: 3.12 = 36 mà 36 < 40: vô lý. Vậy tồn tại một tháng có ít nhất 4 học sinh trùng tháng sinh ( trong bài này 40 thỏ là 40 học sinh, 12 lồng là 12 tên tháng). Ví dụ 11: Cho 2002 số tự nhiên khác 0 sau cho 4 số khác nhau bất kỳ trong chúng đều lập thành một tỷ lệ thức. Chứng minh rằng trong các số đã cho luôn luôn tồn tại ít nhất 501 số bằng nhau. Ta chứng minh trong 2002 số tự nhiên đã cho chỉ nhận nhiều nhất 4 giá trị khác nhau. Thực vậy, giả sử trong các số đã cho có nhiều hơn 4 số khác nhau, giả sử a1, a2, a3, a4, a5 là 5 số khác nhau. trang 16 Không mất tính tổng quát giả sử a1n) 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ó 1983 m-n-1 chia hết cho 105. Như vậy có số k’=m-n sao cho 1983k –1 chia hết cho 105. Ví dụ 13: 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 . 4. Các dạng bài tập. trang 17 a) Dạng 1: Phân chia tập hợp để tạo ra các n – tập (các chuồng) * Nhận xét: Nội dung cơ bản của phương pháp là chia một đối tượng lớn thành nhiều đối tượng nhỏ (các đối tượng này như các “chuồng”). Sau đó áp dụng nguyên lý Dirichlet cho các đối tượng nhỏ Bài toán1: Cho một hình vuông và 13 đường thẳng, mỗi đường thẳng đều chia hình vuông thành hai tứ giác có tỉ số diện tích 2 : 3.Chứng minh rằng trong số 13 đường thẳng đã cho, có ít nhất 4 đường thẳng cùng đi qua một điểm. Giải: Gọi d là đường thẳng chia hình vuông ABCD thành hai tứ giác có tỉ số diện tích là 2 : 3. Đường thẳng d không thể cắt hai cạnh kề nhau của hình vuông Giả sử d cắt hai cạnh AB và CD tại M và N, khi đó nó cắt đường trung bình EF tại I Giả sử S AMND  2 2 S BMNC thì EI  IF 3 3 Như vậy mỗi đường thẳng đã cho chia các đường trung bình của hình vuông theo tỉ số 2 : 3 Có 4 điểm chia các đường trung bình của hình vuông ABCD theo tỉ số 2 : 3 Có 13 đường thẳng, mỗi đường thẳng đi qua một trong 4 điểm trang 18 Vậy theo nguyên lý Dirichlet có ít nhất 4 đường thẳng cùng đi qua 1 điểm. Bài toán 2: Trong hình chữ nhật 3x4 đặt 6 điểm. Chứng minh rằng trong số đó luôn tìm được hai điểm có khoảng cách giữa chúng không lớn hơn 5 . Giải: Chia hình chữ nhật đã cho thành năm hình ABCD, DCKEF, KFNM, NFEQR, QEDAS. Vì có 6 điểm nên theo nguyên lí Dirichlet tồn tại một trong năm hình trên, mà hình này chứa ít nhất hai trong 6 điểm đã cho. Ta đưa vào khái niệm sau: Giả sử P là một hình . {MN} , và đại lượng d(P) gọi là đường kính của hình P. Dễ thấy Đặt d(P)= Mm, Nax P cả năm hình trên đều có đường kính bằng 5 . ( Thí dụ: d(ABCD) = AC = 5 , d(DCKFE) = CE = KE = CF =DK = 5 ) Từ đó suy ra luôn tìm được 2 điểm trong số 6 điểm đã cho có khoảng cách không lớn hơn 5 . Đó là điều phải chứng minh. Từ đó ta có các bài toán tương tự như sau: Bài toán 3: Bên trong tam giác đều ABC cạnh 1 đặt 5 điểm.Chứng minh rằng tồn tại 2 điểm có khoảng cách nhỏ hơn 0,5 Giải: trang 19 Các đường trung bình của tam giác đều cạnh 1 sẽ chia nó ra làm 4 tam giác đều cạnh 0,5. Do đó trong một tam giác nhỏ đó có ít nhất 2 điểm đã cho, và các điểm đó không thể rơi vào các đỉnh của tam giác ABC.Vậy khoảng cách giữa hai điểm đó nhỏ hơn 0,5. Bài toán 4 : Trong hình tròn đường kính bằng 5 có 10 điểm. Chứng minh rằng tồn tại ít nhất hai điểm mà khoảng cách giữa chúng bé hơn hoặc bằng 2. Giải: Thật vậy, trong đường tròn tâm O đường kính 5 , vẽ đường tròn đồng tâm và đường kính 2. Chia hình tròn đã cho thành 9 phần ( xem hình 7.2) đường tròn đường kính 2 và 8 phần bằng nhau II, III, …, IX mà mỗi phần là vành khăn. Rõ ràng I có đường kình bằng 2. trang 20 1 hình 8