Tài liệu ứng dụng nguyên lí dirichlet vào giải bài toán tô màu hình (2017)

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA GIÁO DỤC TIỂU HỌC ------------------------------ NGUYỄN THỊ NGỌC ỨNG DỤNG NGUYÊN LÍ DIRICHLET VÀO GIẢI BÀI TOÁN TÔ MÀU HÌNH KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán tiểu học Người hướng dẫn khoa học ThS. PHẠM THANH TÂM HÀ NỘI, 2017 LỜI CẢM ƠN Trước khi trình bày nội dung của đề tài, tôi xin gửi lời cảm ơn và sự tri ân sâu sắc đến thầy giáo Th.S. Phạm Thanh Tâm – người đã chỉ bảo và hướng dẫn tận tình cho tôi, giúp tôi hoàn thành đề tài khóa luận tốt nghiệp.. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo của trường Đại học Sư phạm Hà Nội 2, tôi cũng đặc biệt cảm ơn các thầy cô giáo khoa Giáo dục Tiểu học đã tận tình chỉ bảo tôi trong suốt quá trình học tập tại trường. Lời cảm ơn chân thành và sâu sắc, tôi xin gửi tới gia đình, bạn bè – những người đã luôn động viên và giúp đỡ tôi trong suốt quá trình học tập tại trường. Tôi xin chân thành cảm ơn! Hà Nội, tháng 5 năm 2017 Sinh viên thực hiện Nguyễn Thị Ngọc LỜI CAM ĐOAN Sau một thời gian nghiên cứu với sự cố gắng, nỗ lực của bản thân cùng sự hướng dẫn, chỉ bảo tận tình của thầy giáo Th.S. Phạm Thanh Tâm tôi đã hoàn thành bài khóa luận của mình. Tôi xin cam đoan bài khóa luận là do bản thân hoàn thành cùng với sự hướng dẫn của thầy giáo Th.S. Phạm Thanh Tâm. Hà Nội, tháng 5 năm 2017 Sinh viên thực hiện Nguyễn Thị Ngọc MỤC LỤC MỞ ĐẦU ........................................................................................................... 1 1. Lí do chọn đề tài ......................................................................................... 1 2. Mục đích nghiên cứu ................................................................................. 2 3. Đối tượng và phạm vi nghiên cứu đề tài .................................................. 3 4. Nhiệm vụ nghiên cứu ................................................................................. 3 5. Phương pháp nguyên cứu ......................................................................... 3 6. Giả thuyết khoa học ................................................................................... 3 7. Cấu trúc đề tài ............................................................................................ 3 CHƯƠNG 1: KIẾN THỨC CƠ BẢN ............................................................. 5 1.1 Các kiến thức cơ bản về bài toán tô màu ............................................. 5 1.1.1 Các kiến thức cơ bản về hình .......................................................... 5 1.1.2 Các kiến thức cơ bản về bài toán tô màu ..................................... 11 1.2 Nguyên lí Dirichlet ................................................................................ 12 1.2.1 Nguyên lí Dirichlet cơ bản ............................................................. 13 1.2.2 Nguyên lí Dirichlet mở rộng .......................................................... 13 1.2.3 Nguyên lí Dirichlet dạng tập hợp.................................................. 14 1.2.4 Nguyên lí Dirichlet dạng tập hợp mở rộng .................................. 14 1.2.5 Nguyên lí Dirichlet vô hạn ............................................................. 15 CHƯƠNG 2: ỨNG DỤNG NGUYÊN LÍ DIRICHLET VÀO GIẢI BÀI TOÁN TÔ MÀU HÌNH .................................................................................. 16 2.1 Bài toán tô màu trên tam giác................................................................. 16 2.2 Bài toán tô màu trên tứ giác ................................................................ 32 2.3 Bài toán tô màu trên đa giác ................................................................... 40 2.4 Một số bài toán đề nghị ........................................................................... 50 KẾT LUẬN ...................................................................................................... 51 TÀI LIỆU THAM KHẢO .............................................................................. 52 MỞ ĐẦU 1. Lí do chọn đề tài Trong hệ thống giáo dục của mỗi quốc gia thì hệ thống Giáo dục Tiểu học giữ một vị trí quan trọng. Việc đào tạo, bồi dưỡng nhân tài phải bắt đầu được quan tâm ngay từ bậc Tiểu học, vì đây là "cái nôi" tri thức đầu tiên và là bậc học đặt nền móng quan trọng cho sự hình thành nhân cách của mỗi học sinh. Trong quá khứ lãnh đạo của Bộ Giáo dục và Đào tạo đã chỉ rõ: "Tiểu học là nền tảng, đặt cơ sở ban đầu cho việc hình thành và phát triển toàn diện nhân cách của con người, đặt nền tảng vững chắc cho giáo dục phổ thông và cho toàn bộ hệ thống giáo dục Quốc dân". Trong các môn học ở trường Tiểu học thì môn toán có vị trí đặc biệt quan trọng. Với tư cách là một môn học trong nhà trường thì môn toán giúp trang bị cho học sinh một hệ thống tri thức, phương pháp riêng để nhận thức thế giới, làm công cụ cần thiết để học tập các môn học khác và phục vụ cho cấp học trên. Các kiến thức toán học được đưa vào dạy cho học sinh Tiểu học gồm 4 tuyến chính là số học, đại lượng và phép đo đại lượng, các yếu tố hình học và giải toán có lời văn. Các tuyến kiến thức này có mối liên hệ mật thiết, hỗ trợ và bổ sung cho nhau ghóp phần phát triển toàn diện năng lực toán học của học sinh Tiểu học. Trong đó, các bài toán hình học tổ hợp nói chung, bài toán tô màu hình nói riêng chiếm một số lượng tương đối lớn trong mảng toán hình học. Các bài toán này không những được trình bày trong sách giáo khoa mà còn được trình bày trong nhiều tài liệu tham khảo khác và có trong các kì thi học sinh giỏi bậc Tiểu học. Sử dụng nguyên lý Dirichlet để giải các bài toán này là phương pháp phổ biến, giúp học sinh dễ nắm bắt kiến thức. Nhờ có ứng dụng của nguyên lí này mà nhiều bài toán khó trong lĩnh vực hình học tổ hợp đặc biệt là các bài toán tô màu hình trong sách giáo khoa và các bài 1 trong kì thi học sinh khá giỏi bậc Tiểu học được giải quyết một cách dễ dàng, thuận tiện và trọn vẹn. Nguyên lí Dirichlet do nhà toán học Peter Guster Lijeune Dirichlet (1805- 1859) người Đức đưa ra lần đầu tiên vào năm 1834. Nguyên lí này là một công cụ hiệu quả và sắc bén để chứng minh nhiều kết quả sâu sắc của toán học. Ở mỗi cấp học nguyên lí Dirichlet lại được phát biểu bằng một ngôn ngữ khác nhau sao cho phù hợp với tư duy và lứa tuổi của các em mà vẫn giữ nguyên được bản chất của kiến thức trong nguyên lí. Nó có nhiều ứng dụng trong các lĩnh vực khác nhau của toán học như hình học, đại số, tổ hợp,... Nguyên lí Dirichlet có nội dung khá đơn giản song nó lại là một công cụ vô cùng hiệu quả trong việc chứng minh nhiều bài toán từ cụ thể đến trừu tượng mà khó có thể có một công cụ nào thay thế. Trong rất nhiều trường hợp nó giúp học sinh thấy được một sự vật, một sự việc chắc chắn tồn tại song không thể chỉ ra được một cách tường minh. Chính điều đó đã kích thích tư duy, óc tưởng tượng phong phú của học sinh, làm cho học sinh thấy yêu thích hơn với bộ môn toán. Vì vậy mà các kì thi học sinh giỏi các cấp thường xuyên có mặt các bài toán sử dụng nguyên lí này. Dùng nguyên lí Dirichlet trong nhiều trường hợp người ta dễ chứng minh được sự tồn tại của một đối tượng với tính chất xác định. Sử dụng nguyên lí Dirichlet không đòi hỏi nhiều kiến thức về hình học và tổ hợp cùng với khả năng tính toán mà chủ yếu đòi hỏi sự sáng tạo trong việc đưa ra một số mô hình cụ thể và linh hoạt trong cách tư duy. Đó là điểm mạnh cũng như cái khó của việc ứng dụng nguyên lí Dirichlet vào giải các bài toán tô màu. 2. Mục đích nghiên cứu Nghiên cứu các cơ sở lý luận và dựa vào thực tiễn trong quá trình học tập, giảng dạy kiến thức hình học để tổng hợp và đưa ra các ứng dụng của nguyên lí Dirichlet vào giải các bài toán tô màu. 2 3. Đối tượng và phạm vi nghiên cứu đề tài  Đối tượng: nguyên lí Dirichlet và những bài toán tô màu có ứng dụng nguyên lí Dirichlet để giải.  Phạm vi nghiên cứu: một số bài toán tô màu giải được bằng nguyên lí Dirichlet. 4. Nhiệm vụ nghiên cứu  Nêu nội dung cơ bản của nguyên lí Dirichlet.  Nêu ứng dụng của nguyên lí Dirichlet vào việc giải các bài toán tô màu.  Hệ thống lại một số dạng bài tập tô màu có ứng dụng nguyên lí Dirichlet để giải. 5. Phương pháp nguyên cứu  Phương pháp nghiên cứu lí luận.  Phương pháp phân tích tổng hợp và hệ thống. 6. Giả thuyết khoa học Nếu xác định được ứng dụng của nguyên lí Dirichlet và hệ thống lại được các dạng bài tập thì sẽ góp phần nâng cao chất lượng dạy học môn Toán, đặc biệt là các kiến thức Hình học và bồi dưỡng học sinh giỏi. 7. Cấu trúc đề tài Ngoài phần mở đầu, kết luận và tài liệu tham khảo, khóa luận gồm 2 chương: Chương 1: Kiến thức cơ bản về bài toán tô màu hình và nguyên lí Dirichlet. Chương này nhằm mục đích chuẩn bị các kiến thức cần thiết làm nền tảng cho chương tiếp theo. Chương 2: Trong chương này, tôi đưa ra các ứng dụng nguyên lí Dirichlet vào giải bài toán tô màu hình: - Trên tam giác 3 - Trên tứ giác - Trên đa giác - Một số bài tập đề nghị 4 NỘI DUNG CHƯƠNG 1: KIẾN THỨC CƠ BẢN 1.1 Các kiến thức cơ bản về bài toán tô màu 1.1.1 Các kiến thức cơ bản về hình Dưới đây là mô tả cho một vài khái niệm nhằm mục đích sử dụng cho khóa luận. 1.1.1.1 Các định nghĩa Điểm trong mặt phẳng: Điểm là một khái niệm cơ bản trong toán học, được hình dung như là cái gì đó rất nhỏ bé, không có kích thước hay kích thước bằng không. Đoạn thẳng trong mặt phẳng: là một phần của đường thẳng mà bị giới hạn bởi hai đầu mút, và là quỹ tích của tất cả những điểm nằm giữa hai đầu mút này trong quan hệ thẳng hàng. Các ví dụ về đoạn thẳng là: các cạnh của một tam giác hay một hình vuông. Tổng quát hơn, nếu cả hai đầu mút là hai đỉnh kề nhau của một đa giác, đoạn thẳng đó là một cạnh (của đa giác đang xét), nếu hai đầu mút không phải là hai đỉnh kề nhau thì đoạn thẳng đó là đường chéo của đa giác. Khi các đầu mút nằm trên cùng một đường như là đường tròn, thì đoạn thẳng đó được gọi là một dây cung (của đường đang xét). Đỉnh trong một hình: là điểm chung của hai hay nhiều cạnh. 1.1.1.2 Các hình cơ bản và hình đặc biệt ở Tiểu học  Các hình cơ bản:  Hình tam giác (hình tam giác cân, hình tam giác đều). Định nghĩa: Hình tam giác là hình có ba cạnh, ba đỉnh và ba góc. Nếu một tam giác không có cạnh nào bằng nhau thì đó là tam giác thường. Nếu một tam giác có ít nhất hai cạnh có chiều dài bằng nhau thì đó là tam giác cân. Tam giác có ba cạnh với chiều dài bằng nhau thì đó là tam giác đều. 5 Tính chất: - Tổng các góc trong của một tam giác bằng 1800 - Độ dài mỗi cạnh lớn hơn hiệu độ dài hai cạnh kia và nhỏ hơn tổng độ dài của chúng. - Ba đường cao của tam giác cắt nhau tại mỗi điểm được gọi là trực tâm của tam giác. - Ba đường trung tuyến của tam giác cắt nhau tại một điểm được gọi là trọng tâm của tam giác. Đường trung tuyến của tam giác chia tam giác thành hai phần có diện tích bằng nhau. - Ba đường trung trực của tam giác cắt nhau tại một điểm là tâm đường tròn ngoại tiếp của tam giác. - Ba đường phân giác trong tam giác cắt nhau tại một điểm là tâm đường tròn nội tiếp của tam giác. - Trong hai cạnh của cùng một tam giác cạnh đối diện với góc lớn hơn có chiều dài lớn hơn. Góc đối diện với cạnh lớn hơn là góc lớn hơn - Định lí hàm cosin: Trong một tam giác, bình phương độ dài một cạnh bằng tổng bình phương độ dài hai cạnh còn lại trừ đi hai lần tích của độ dài hai cạnh ấy với cosin của góc xen giữa hai cạnh đó. - Định lí hàm số sin: Trong một tam giác tỉ lệ giữa độ dài của mỗi cạnh với sin của góc đối diện là như nhau cho cả ba cạnh.  Hình chữ nhật Định nghĩa: Hình chữ nhật là hình có bốn cạnh, bốn đỉnh và bốn góc vuông. Tính chất: - Trong hình chữ nhật, hai đường chéo bằng nhau và cắt nhau tại trung điểm của mỗi đường. - Có tất cả các tính chất của hình thang cân và hình bình hành. 6 - Các đường chéo cắt nhau tạo thành bốn tam giác cân. Dấu hiệu nhận biết: - Tứ giác có ba góc vuông là hình chữ nhật. - Hình thang cân có một góc vuông là hình chữ nhật. - Hình bình hành có một góc vuông là hình chữ nhật. - Hình bình hành có hai đường chéo bằng nhau là hình chữ nhật.  Hình vuông Định nghĩa: Hình vuông là tứ giác có 4 góc vuông và 4 cạnh bằng nhau. Tính chất: - Hai đường chéo bằng nhau, vuông góc và giao nhau tại trung điểm của mỗi đường. - Có một đường tròn nội tiếp và ngoại tiếp đồng thời tâm của cả hai đường tròn trùng nhau và là giao điểm của hai đường chéo của hình vuông. - Một đường chéo sẽ chia hình vuông thành hai phần có diện tích bằng nhau. - Giao điểm của các đường phân giác, trung tuyến, trung trực đều trùng tại một điểm. - Có tất cả tính chất của hình chữ nhật và hình bình hành. Dấu hiệu nhận biết: - Hình chữ nhật có hai cạnh kề bằng nhau là hình vuông. - Hình chữ nhật có hai đường chéo vuông góc với nhau là hình vuông. - Hình chữ nhật có một đường chéo là đường phân giác của một góc là hình vuông. - Hình thoi có một góc vuông là hình vuông. - Hình thoi có hai đường chéo bằng nhau là hình vuông. 7  Hình tứ giác Định nghĩa: Tứ giác là đa giác có bốn cạnh và bốn đỉnh. Tính chất: Tổng các góc của tứ giác đơn bằng .  Hình tròn Định nghĩa: Hình tròn là tập hợp tất cả các điểm nằm trong và nằm trên đường tròn hay tập hợp các điểm cách tâm một khoảng nhỏ hơn hoặc bằng bán kính. Đường tròn là quỹ tích của tất cả những điểm trên một mặt phẳng, cách đều một điểm cho trước bằng một khoảng cách cho trước. Điểm cho trước gọi là tâm của đường tròn, còn khoảng cho trước gọi là bán kính của đường tròn. Tính chất: - Tập hợp các điểm cách đều điểm O cho trước một khoảng không đổi R gọi là đường tròn tâm O bán kính R, kí hiệu là (O,R). - Một đường tròn hoàn toàn xác định bởi một điều kiện của nó. Nếu AB là đoạn cho trước thì đường tròn đường kính AB là tập hợp những điểm M sao cho góc AMB bằng . Khi đó tâm O sẽ là trung điểm của AB còn bán kính thì bằng R = AB/2. - Qua 3 điểm A, B, C không thẳng hàng, luôn vẽ được một đường tròn và chỉ một mà thôi. Đường tròn đó được gọi là đường tròn ngoại tiếp tam giác ABC. - Trong một đường tròn, đường kính vuông góc với một dây thì đi qua trung điểm dây đó. Ngược lại đường kính đi qua trung điểm của một dây không đi qua tâm thì vuông góc với dây đó. - Trong đường tròn, hai dây cung bằng nhau khi và chỉ khi chúng cách đều tâm. - Trong một đường tròn, hai dây cung không bằng nhau, dây lớn hơn khi và chỉ khi dây đó gần tâm hơn. 8  Hình lập phương Hình hộp đứng là hình hộp có cạnh bên vuông góc với mặt đáy. Tính chất: Hình hộp đứng có hai đáy là hình bình hành, bốn mặt xung quanh là bốn hình chữ nhật. Hình hộp chữ nhật là hình hộp đứng có đáy là hình chữ nhật. Tính chất: Hình hộp chữ nhật có sáu mặt là sáu hình chữ nhật. Hình lập phương là hình hộp chữ nhật có hai đáy và bốn mặt bên đều là hình vuông. Tính chất: Hình lập phương có sáu mặt đều là hình vuông.  Các hình đặc biệt:  Hình đa giác đều có n cạnh Trong hình học phẳng, đa giác là một đường gấp khúc phẳng khép kín, nghĩa là gồm những đoạn thẳng nối tiếp nhau (mỗi điểm nối là đầu mút của vừa đúng hai đoạn thẳng) cùng nằm trên một mặt phẳng và khép kín (điểm nối đầu trùng với điểm nối cuối). Phần mặt phẳng giới hạn bởi đường đa giác được gọi là hình đa giác. Những đoạn thẳng trên đường gấp khúc này được gọi là cạnh của đa giác, còn điểm nối tiếp giữa hai cạnh được gọi là đỉnh của đa giác. Hai cạnh có chung đỉnh cũng được gọi là hai cạnh kề nhau. Nếu đa giác là đa giác đơn thì các cạnh và các đỉnh tạo thành ranh giới của miền đa giác. Đôi khi cũng xét tới các đường gấp khúc, khép kín, không cùng nằm trong một mặt phẳng, đó được gọi là đa giác ghềnh. Tuy nhiên thuật ngữ đa giác thường dùng cho các đa giác phẳng. Đa giác đều là đa giác có tất cả các cạnh bằng nhau và các góc ở đỉnh bằng nhau. Đa giác đều được chia làm hai loại là đa giác lồi đều (đa giác đều một đỉnh, nhị giác đều, tam giác đều, hình vuông, ngũ giác đều, lục giác đều, thất giác đều, bát giác đều, cửu giác đều, thập giác đều, …) và đa giác sao đều 9 (sao 5 cánh đều, sao 7 cánh đều, sao 8 cánh đều, sao 9 cánh đều, sao 10 cánh đều, sao 11 cánh đều, …)  Hình chóp đáy là đa giác n cạnh Trong hình học, hình chóp là khối đa diện có một đỉnh và một đáy là đa giác lồi, các mặt bên là các hình tam giác. Chiều cao của hình chóp là khoảng cách từ đỉnh đến mặt đáy của hình chóp. Các loại hình chóp thường gặp:  Hình chóp đa giác đều: là hình chóp có đáy là đa giác đều và hình chiếu của đỉnh xuống đáy trùng với tâm của đáy. Cần phân biệt nó với hình chóp có đáy là đa giác đều, vốn chỉ có đáy là đa giác đều chứ hình chiếu của đỉnh xuống đáy chưa chắc trùng với tâm của đáy.  Hình chóp đều là hình chóp có đáy là đa giác đều. Các cạnh bên của nó bằng nhau. Hình chóp có mặt đáy là tứ giác Hình chóp có mặt đáy là hình thang Hình chóp có mặt đáy là hình bình hành  Hình lăng trụ có hai đáy là các đa giác đều Hình lăng trụ là một đa diện có hai mặt đáy là các đa giác tương đẳng và những mặt còn lại là các hình bình hành. Mọi tiết diện song song với hai đáy đều là các đa giác tương đẳng với hai đáy. Hình lăng trụ đứng là hình lăng trụ có cạnh bên vuông góc với mặt đáy. Trong hình lăng trụ đứng thì tất cả các mặt bên đều là hình chữ nhật. Hình lăng trụ đều là hình lăng trụ đứng có đáy là đa giác đều. Ta hay gặp hình lăng trụ đều có đáy là tam giác hoặc hình vuông trong giải toán. Người ta thường gọi tắt các trường hợp đó với các thuật ngữ là hình lăng trụ tam giác đều, hình lăng trụ tứ giác đều. Hình lăng trụ tứ giác đều là một hình hộp đứng đặc biệt có đáy là hình vuông còn hình hộp đứng thì chỉ cần đáy là hình bình hành. 10 1.1.2 Các kiến thức cơ bản về bài toán tô màu 1.1.2.1 Các công đoạn trong tô màu hình  Xác định vị trí các điểm, đoạn thẳng, đỉnh, cạnh cần tô màu  Quyết định màu để tô vào các vị trí trên. Công đoạn này sẽ trở nên phức tạp khi ta cần tô theo một mẫu tô nào đó chứ không phải tô thuần một màu. 1.1.2.2 Các cách tiếp cận chính để tô màu Có 3 cách tiếp cận chính để tô màu:  Tô màu theo từng điểm (tô đơn giản) Thuật toán này bắt đầu từ việc xác định một điểm có thuộc vùng cần tô hay không. Nếu đúng là điểm thuộc vùng cần tô thì sẽ tô với màu muốn tô. Thường sử dụng trong tô đường tròn, tô đa giác,… Nhận xét: Thuật toán tô đơn giản có ưu điểm là tô rất mịn và có thể sử dụng được cho đa giác lồi hay đa giác lõm, hoặc đa giác tự cắt, đường tròn, elip… Tuy nhiên, giải thuật này sẽ trở nên chậm khi ta phải gọi hàm PointInpoly nhiều lần. Để khắc phục nhược điểm này người ta đưa ra thuật toán tô màu theo dòng quét.  Tô màu theo dòng quét Tô màu theo dòng quét (scan - line) Phương pháp này sẽ xác định phần giao của các dòng quét kế tiếp nhau với đường biên của vùng tô. Sau đó, sẽ tiến hành tô màu các điểm thuộc phần giao này. Phương pháp này thường được dùng để tô màu đa giác lồi , lõm hay đa giác tự cắt, đường tròn, ellipse, và một số đường cong đơn giản khác. Các vấn đề cần lưu ý: - Hạn chế được số cạnh cần tìm giao điểm ứng với mỗi dòng quét vì ứng với mỗi dòng quét không phải lúc nào cũng giao điểm với các cạnh của đa giác. 11 - Xác định nhanh hoành độ giao điểm vì nếu lặp lại thao tác tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ tốn rất nhiều thời gian. - Giải quyết trường hợp số giao điểm đi qua đỉnh đơn điệu thì tính số giao điểm là 1 hay đi qua đỉnh cực trị thì tính số giao điểm là 0 (hoặc 2).  Tô màu dựa theo đường biên Bài toán đặt ra : Cần tô màu một vùng nếu biết được màu của đường biên vùng tô và một điểm nằm bên trong vùng tô. Ý tưởng : Bắt đầu từ một điểm nằm bên trong vùng tô, kiểm tra các điểm lân cận của nó đã được tô với màu muốn tô, hay điểm lân cận có màu trùng với màu biên không ? Nếu cả hai trường hợp đều không phải thì ta sẽ tô điểm đó với màu muốn tô. Quá trình này được lặp lại cho đến khi không còn tô được nữa thì dừng. Nhận xét : - Thuật toán có thể không chính xác khi có một số điểm nằm trong vùng tô có màu là màu cần tô của vùng. - Việc thực hiện gọi đệ qui làm thuật toán không thể sử dụng cho vùng tô lớn (tràn stack). - Có thể khắc phục việc tràn stack bằng cách giảm số lần gọi đệ qui. Khởi đầu điểm (x,y) là điểm có vị trí đặc biệt trong vùng tô, sau đó, gọi đệ qui các điểm lân cận của (x,y). 1.2 Nguyên lí Dirichlet Nguyên lí Dirichlet còn gọi là “Nguyên tắc nhốt thỏ vào lồng” hoặc “nguyên tắc xếp đồ vật vào ngăn kéo” hoặc “nguyên tắc lồng chim bồ câu” đã được biết đến từ rất lâu. Nguyên lí Dirichlet này được nhà toán học người Đức Peter Guster Lijeune Dirichlet (1805-1859) phát biểu lần đầu tiên vào năm 1834. 12 1.2.1 Nguyên lí Dirichlet cơ bản Nếu nhốt n+1 con 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ỏ. Ta có thể phát biểu nguyên lí Dirichlet tổng quát như sau: Mệnh đề 1.2.1.1 Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại [ ] đồ vật. (Ở đây, ⌊x⌋ là số nguyên nhỏ nhất có giá trị N một hộp chứa ít nhất k lớn hơn hoặc bằng x). Chứng minh. Giả sử mọi hộp đều chứa ít hơn [N ] đồ vật. Khi đó tổng số k đồ vật là: [ ] - 1) < k[N ] = N. 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. 1.2.2 Nguyên lí Dirichlet mở rộng Mệnh đề 1.2.2.1 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 m [n + m - 1 ] con thỏ, ở đây kí hiệu [α] để chỉ phần nguyên của số α. Chứng minh. Giả sử trái lại, mọi chuồng thỏ không có đến m [ n + m - 1 ] = [ n m 1 + 1] = [ n m 1 ] + 1 13 con, thì số thỏ mỗi chuồng đều nhỏ hơn hoặc bằng tổng số con thỏ không vượt quá m. chứng tỏ có ít nhất một chuồng có [nm1 ] con. Từ đó suy ra [nm1 ] ≤ n – 1 con (vô lí). Điều vô lí này m [n + m - 1 ] con thỏ. 1.2.3 Nguyên lí Dirichlet dạng tập hợp Mệnh đề 1.2.3.1. Cho A và B là hai tập hợp khác rỗng. Kí hiệu S(A), S(B) lần lượt là số lượng phần tử của A và B, với S(B) < S(A) < +∞. Khi đó, xét ánh xạ f, với: f:A B f(a) = b ∈ B a thì tồn tại aʹ ∈ A, aʹ ≠ a sao cho: f(aʹ ) = f(a) = b. 1.2.4 Nguyên lí Dirichlet dạng tập hợp mở rộng Giả sử A, B là hai tập hợp hữu hạn và S(A), S(B) tương ứng kí hiệu là các số lượng phần tử của A và B. a1 b1 a2 b2 a3 b3 a4 H 1.1 Mệnh đề 1.2.4.1. Giả sử có một số tự nhiên k nào đó mà S(A) > k.S(B) và ta có quy tắc cho tương ứng với mỗi phần tử của A với một phần tử của B. Khi 14 đó tồn tại ít nhất k + 1 phần tử của A mà chúng tương ứng với cùng một phần tử của B. Chứng minh. Với mọi tập hợp con C gồm một phần tử của B (C ⊂ B) thì S(C) = 1. Ta có: S(C) = 1 ≤ S(B) suy ra S(A) > k.S(C) = k. Hay S(A) ≥ k +1. Suy ra tồn tại ít nhất k + 1 phần tử của A tương ứng với một phần tử của B. Vì C là tập bất kì nên nguyên lí được chứng minh. Chú ý: khi k = 1, ta có ngay lại nguyên lí Dirichlet. 1.2.5 Nguyên lí Dirichlet vô hạn Mệnh đề 1.2.5.1. Nếu chia một tập hợp vô hạn các quả táo vào hữu hạn ngăn kéo, thì phải có ít nhất một ngăn kéo chứa vô hạn các quả táo. Chứng minh. Nguyên lí Dirichlet mở rộng cho trường hợp vô hạn này cũng đóng vai trò hết sức quan trọng trong lí thuyết số nói riêng và toán học rời rạc nói chung. 15 CHƯƠNG 2: ỨNG DỤNG NGUYÊN LÍ DIRICHLET VÀO GIẢI BÀI TOÁN TÔ MÀU HÌNH 2.1 Bài toán tô màu trên tam giác Bài toán 2.11 Trong mặt phẳng cho 6 điểm sao cho không có ba điểm nào thẳng hàng. Mỗi đoạn thẳng nối từng cặp điểm được bôi màu đỏ hoặc xanh. Chứng minh rằng tồn tại ba điểm trong số sáu điểm đã cho, sao cho chúng là các đỉnh của một tam giác mà các cạnh của nó được bôi cùng một màu. Chứng minh. Xét A là một trong số sáu điểm đã cho. Khi đó xét năm đoạn thẳng (mỗi đoạn thẳng nối điểm A với năm điểm còn lại). Vì mỗi đoạn thẳng được bôi chỉ màu đỏ hoặc màu xanh, nên theo nguyên lí Dirichlet có ít nhất ba trong năm đoạn nói trên cùng màu. Giả sử đó là các đoạn AB, ABʹ và ABʹʹ và có thể cho rằng chúng cùng màu xanh. Chỉ có hai khả năng xảy ra: Bʹ B Bʹʹ A H. 2.11 16