Tài liệu Một số bài toán hình học tổ hợp

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM ***** ĐẶNG THỊ THÚY NGÂN MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢP KHÓA LUẬN TỐT NGHIỆP Đà Nẵng – Năm 2021 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM ***** ĐẶNG THỊ THÚY NGÂN MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢP KHÓA LUẬN TỐT NGHIỆP NGƯỜI HƯỚNG DẪN KHÓA LUẬN: TS. LÊ VĂN DŨNG Đà Nẵng – Năm 2021 LỜI CẢM ƠN Đề tài khóa luận tốt nghiệp được hoàn thành tại trường Đại học Sư phạm – Đại học Đà Nẵng, dưới sự hướng dẫn của TS. Lê Văn Dũng. Trước hết, tôi xin được gửi lời cảm ơn sâu sắc đến người thầy của mình là TS. Lê Văn Dũng, người đã đặt bài toán và định hướng nghiên cứu cho tôi. Thầy đã tận tình chỉ bảo và tạo mọi điều kiện để tôi học tập và hoàn thành đề tài. Cảm ơn thầy đã luôn chia sẻ, động viên tôi trong quá trình học tập và nghiên cứu. Tôi cũng xin chân thành cảm ơn khoa Toán học của trường Đại học Sư phạm – Đại học Đà Nẵng đã tạo điều kiện để tôi hoàn thành đề tài khóa luận tốt nghiệp này. Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đến gia đình và những người bạn thân thiết đã luôn chia sẻ, giúp đỡ, động viên tôi trong quá trình thực hiện đề tài. Đặng Thị Thúy Ngân MỤC LỤC PHẦN MỞ ĐẦU .................................................................................................................. 1 CHƯƠNG 1: KIẾN THỨC CƠ SỞ ..................................................................................... 3 1.1. Một số kiến thức hình học cơ bản ............................................................................... 3 1.1.1. Các định nghĩa ....................................................................................................... 3 1.1.2. Định lý Pytago........................................................................................................ 4 1.1.3. Đường trung trực ................................................................................................... 4 1.1.4. Bất đẳng thức tam giác .......................................................................................... 4 1.1.5. Đường tròn bàng tiếp của tam giác ....................................................................... 5 1.2. Phương pháp phản chứng và nguyên lý Dirichlet ...................................................... 5 1.2.1. Phương pháp phản chứng ...................................................................................... 5 1.2.2. Nguyên lý Dirichlet ................................................................................................ 7 1.3. Phương pháp quy nạp toán học ................................................................................. 10 1.3.1. Giới thiệu.............................................................................................................. 13 1.3.2. Phương pháp chứng minh quy nạp toán học ....................................................... 13 1.3.3. Quy nạp mạnh ...................................................................................................... 13 1.3.4. Quy nạp bước nhảy .............................................................................................. 13 1.3.5. Quy nạp lùi ........................................................................................................... 14 CHƯƠNG 2: MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢP ............................................... 15 2.1. Sử dụng phương pháp phản chứng – Nguyên lý Dirichlet ....................................... 15 2.2. Sử dụng phương pháp quy nạp toán học................................................................... 21 KẾT LUẬN ........................................................................................................................ 27 TÀI LIỆU THAM KHẢO .................................................................................................. 28 1 PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Bài toán hình học tổ hợp là một bài toán mà trong đó có nhiều thành phần (ví dụ như nhiều điểm, nhiều góc, nhiều hình), và để giải quyết bài toán chúng ta cần dùng các phương pháp tổ hợp, tức là các phương pháp phân chia và kết hợp các thành phần với nhau. Hình học tổ hợp là một nhánh không thể thiếu được của các bài toán tổ hợp nói chung, các bài toán Hình học tổ hợp thường không đòi hỏi nhiều về kiến thức và kỹ năng tính toán. Chúng chủ yếu đòi hỏi sự chặt chẽ trong việc xét các khả năng, sự sáng tạo trong việc đưa ra những mô hình cụ thể, sự linh hoạt trong việc vận dụng các phương pháp. Nhiều bài toán có nội dung tương tự như nhau, chỉ khác nhau về các con số, nhưng lại cần đến những cách giải quyết khác nhau, đòi hỏi người giải toán không thể rập khuôn, máy móc. Chỗ khó và cũng là thế mạnh của Hình học tổ hợp là ở chỗ đó chính vì vậy nó thường xuyên xuất hiện trong các đề thi học sinh giỏi ở mọi cấp. Khác với các bài toán trong lĩnh vực Giải tích, Đại số, Lượng giác, các bài toán của hình học tổ hợp thường liên quan nhiều đến các đối tượng là các tập hợp hữu hạn. Vì lẽ đó các bài toán này mang đặc trưng rõ nét của toán học rời rạc. (Ít sử dụng đến tính liên tục - một tính chất đặc trưng của bộ môn giải tích). 2. Mục đích nghiên cứu Trong khóa luận này, tôi nghiên cứu về một số phương pháp để giải các bài toán hình học tổ hợp, từ đó làm tiền đề để nghiên cứu giải quyết các bài toán. Chứng minh chi tiết một số kết quả liên quan đến các bài toán hình học tổ hợp của các tác giả đi trước. 3. Đối tượng nghiên cứu - Phương pháp phản chứng. - Nguyên lý Dirichlet. - Phương pháp quy nạp toán học. 4. Phạm vi nghiên cứu Nghiên cứu các khái niệm và tính chất của phương pháp phản chứng, nguyên lý Dirichlet và phương pháp quy nạp toán học. 5. Phương pháp nghiên cứu - Tham khảo tài liệu, hệ thống lại một số kiến thức về hình học. 2 - Thu thập các bài báo khoa học của các tác giả đi trước liên quan hình học tổ hợp. - Bằng cách tương tự hóa, khái quát hóa nhằm đưa ra các kết quả mới cũng như mở rộng một số kết quả của các tác giả đi trước. - Phân tích, đánh giá, tổng hợp và trao đổi với thầy hướng dẫn kết quả đang nghiên cứu để hoàn chỉnh đề tài của mình. 6. Ý nghĩa khoa học và thực tiễn Đề tài có ý nghĩa về mặt lý thuyết, là tài liệu tham khảo cho những ai quan tâm đến ứng dụng của phương pháp phản chứng – Nguyên lý Dirichlet và phương pháp quy nạp để giải một số bài toán hình học tổ hợp. 7. Cấu trúc của đề tài Nội dung khóa luận được tôi trình bày trong hai chương. Ngoài ra, khóa luận có Lời cảm ơn, Mục lục, phần Mở đầu, phần Kết luận và Tài liệu tham khảo. Chương 1 trình bày một số định nghĩa, định lý và tính chất về một số kiến thức hình học cơ bản, phương pháp phản chứng – Nguyên lý Dirichlet và phương pháp quy nạp toán học làm bổ trợ cho chương sau. Chương này bao gồm 3 mục: mục 1.1 gồm một số kiến thức hình học cơ bản được sử dụng trong khóa luận; mục 1.2 giới thiệu khái niệm, tính chất của phương pháp phản chứng – Nguyên lý Dirichlet và phương pháp sử dụng chúng; mục 1.3 giới thiệu khái niệm, tính chất của phương pháp quy nạp toán học. Chương 2 trình bày về một số bài toán hình học tổ hợp. Chương này bao gồm 2 mục: mục 2.1 trình bày các bài toán hình học tổ hợp được chứng minh bằng phương pháp phản chứng - Nguyên lý Dirichlet; mục 2.2 trình bày các bài toán hình học tổ hợp được chứng minh bằng phương pháp quy nạp toán học. 3 CHƯƠNG 1: KIẾN THỨC CƠ SỞ Trong chương này, tôi trình bày một số định nghĩa, định lý và tính chất về một số kiến thức hình học cơ bản, phương pháp phản chứng – Nguyên lý Dirichlet và phương pháp quy nạp toán học làm bổ trợ cho các chương sau. Tất cả các số đo trong cùng một bài toán, nếu không chú thích đơn vị, được hiểu là đo theo cùng một đơn vị đo. 1.1. Một số kiến thức hình học cơ bản 1.1.1. Các định nghĩa 1.1.1.1. Định nghĩa Mệnh đề là câu khẳng định có thể xác định được tính đúng hay sai của nó. Một mệnh đề không thể vừa đúng, vừa sai. 1.1.1.2. Định nghĩa Mệnh đề chứa biến là câu khẳng định mà sự đúng đắn, hay sai của nó còn tùy thuộc vào một hay nhiều yếu tố biến đổi. 1.1.1.3. Định nghĩa Theo mệnh đề kéo theo có dạng: "Nếu A thì B", trong đó A và B là hai mệnh đề. Mệnh đề "Nếu A thì B" kí hiệu là A =>B. Tính đúng, sai của mệnh đề kéo theo như sau: Mệnh đề A => B chỉ sai khi A đúng và B sai. 1.1.1.4. Định nghĩa Mệnh đề "B=>A" là mệnh đề đảo của mệnh đề A => B. 1.1.1.5. Định nghĩa - Nếu A => B là một mệnh đề đúng và mệnh đề B => A cũng là một mệnh đề đúng thì ta nói A tương đương với B, kí hiệu: A ⇔ B. - Khi A ⇔ B, ta cũng nói A là điều kiện cần và đủ để có B hoặc A khi và chỉ khi B hay A nếu và chỉ nếu B. 4 1.1.2. Định lý Pytago 1.1.2.1. Định lý pitago thuận Trong 1 tam giác vuông (hình 1) bình phương cạnh huyền (cạnh đối diện với góc vuông) bằng tổng bình phương của hai cạnh góc vuông. 1.1.2.2. Định lý pitago đảo Nếu một tam giác có bình phương của một cạnh bằng tổng các bình phương của hai cạnh còn lại thì tam giác đó là tam giác vuông. 1.1.3. Đường trung trực 1.1.3.1. Định nghĩa Đường thẳng đi qua trung điểm của đoạn thẳng và vuông góc với đoạn thẳng gọi là đường trung trực của đoạn thẳng ấy (Hình 2). Hình 2 1.1.3.2. Định lý Điểm nằm trên đường trung trực của một đoạn thẳng thì cách đều hai mút của đoạn thẳng đó. 1.1.3.3. Định lý Điểm cách đều hai đầu mút của một đoạn thẳng thì nằm trên đường trung trực của đoạn thẳng đó.  Nhận xét Hình 3 Tập hợp các điểm cách đều hai mút của một đoạn thẳng là đường trung trực của đoạn thẳng đó. 1.1.4. Bất đẳng thức tam giác 1.1.4.1. Định lý Trong một tam giác, tổng độ dài hai cạnh bất kỳ bao giờ cũng lớn hơn độ dài cạnh còn lại. 1.1.4.2. Hệ quả 5 Trong một tam giác, hiệu độ dài hai cạnh bất kỳ bao giờ cũng nhỏ hơn độ dài cạnh còn lại 1.1.5. Đường tròn bàng tiếp của tam giác 1.1.5.1. Định nghĩa Một đường tròn bàng tiếp của tam giác là một đường tròn nằm ngoài tam giác, tiếp xúc với một cạnh của tam giác và với phần kéo dài của hai cạnh còn lại. 1.1.5.2. Định nghĩa Tâm của một đường tròn bàng tiếp là giao điểm của đường phân giác trong của một góc với các đường phân giác ngoài của hai góc còn lại. 1.2. Phương pháp phản chứng và Nguyên lý Dirichlet 1.2.1. Phương pháp phản chứng 1.2.1.1. Định nghĩa Phương pháp phản chứng hay phép phản chứng (còn được goi là reductio ad absurdum, tiếng La tinh có nghĩa là "thu giảm đến sự vô lý") là một trong các phương pháp chứng minh gián tiếp. Phương pháp này chứng minh một phát biểu bằng cách cho thấy rằng kịch bản ngược lại sẽ dẫn đến một điều vô lý hoặc một sự mâu thuẫn 1.2.1.2. Mục tiêu Mục tiêu của phương pháp phản chứng là bác bỏ mệnh đề phủ định của mệnh đề cần chứng minh. 1.2.1.3. Phương pháp giải Phép phản chứng trong toán học thường được biết đến dưới dạng chứng minh bằng mâu thuẫn hay chứng minh bằng phản chứng. Nếu ta muốn chứng minh kết luận của bài toán là đúng thì phải chúng minh cái ngược lại với nó là sai, vậy ta giả thiết cái ngược lại với nó, và tìm một kết luận mâu thuẫn. Chứng minh một bài toán bằng phương pháp phản chứng gồm ba bước: - Bước 1 (phủ định kết luận): Ta giả sử rằng kết luận bài toán là không đúng. 6 - Bước 2 (đưa đến mâu thuẫn): Từ điều giả sử trên và từ giả thiết của bài toán, ta suy ra một điều mâu thuẫn với giả thiết hoặc mâu thuẫn với kiến thức đã học. - Bước 3 (khẳng định kết luận): Vậy kết luận của bài toán là đúng. 1.2.1.4. Ưu điểm của phương pháp phản chứng Ưu điểm của phương pháp phản chứnglà tạo thêm được một giả thiết mới (giả thiết phản chứng) vào các giả thiết của bài toán. Chẳng hạn để chứng minh A  B bằng phương pháp phản chứng, ta được sử dụng giả thiết phản chứng A  B để chỉ ra điều vô lý. Ví dụ 1.1. Cho hai điểm A, B nằm bên trong một đa giác (có thể không lồi). Chứng minh rằng có ít nhất một đỉnh của đa giác mà khoảng cách từ đỉnh đó đến A lớn hơn khoảng cách từ nó đến B. Giải. (Hình 5). Gọi X1 X 2 ...X n là đa giác đã cho. Giả sử: X1B  X1 A, X 2 N  X 2 B,..., X n B  X n A. Gọi đường trung trực của đoạn thẳng AB là d. Gọi A  ( P1 ), B  ( P2 ) sao cho ( P1 ) và ( P2 ) là hai nửa mặt phẳng của đa giác được cắt bởi đường thẳng d. Hình 5 Để khoảng cách từ X n đến A nhỏ hơn khoảng cách từ X n đến B thì X n phải thuộc mặt phẳng ( P1 ) . Do X1B  X1 A nên X 1   P1  , do X 2 B  X 2 A nên X 2   P1  , tương tự, X 3 , X 4 ,..., X 5 cũng thuộc ( P1 ) . Từ đó suy ra mọi đỉnh của đa giác thuộc nửa mặt phẳng ( P1 ) , còn B thuộc nửa mặt phẳng ( P2 ) nên B nằm bên ngoài đa giác, trái với giả thiết. Vậy tồn tại một đỉnh X của đa giác sao cho khoảng cách từ X đến A lớn hơn khoảng cách từ X đến B. 7 Ví dụ 1.2. Cho hình vuông cạnh 10 và hai điểm bất kỳ M, N. Chứng minh rằng có ít nhất một điểm thuộc biên của hình vuông sao cho 14 nhỏ hơn tổng các khoảng cách từ điểm đó đến M và N. Giải. (Hình 6). Giả sử có không tồn tại một điểm thuộc biên của hình vuông sao cho 14 nhỏ hơn tổng các khoảng cách từ điểm đó đến M và N. Gọi PQ là đường chéo của hình vuông cạnh 10 đã cho. Áp dụng định lý Pytago ta có: PQ  102  102  10 2 . Áp dụng bất đẳng thức tam giác ta có: PM  QM  PQ  10 2 và Hình 6 PN  QN  PQ  10 2 . Suy ra: ( PM  QM )  ( PN  QN )  ( PM  PN )  (QM  QN )  20 2 (1) Trong hai tổng PM + PN và QM + QN, tồn tại một tổng lớn hơn hoặc bằng 10 2 , vì nếu cả hai tổng nhỏ hơn 10 2 thì tổng của chúng nhỏ hơn 20 2 , mâu thuẫn với (1). Chẳng hạn PM  PN  10 2 , thế thì PM + PN > 14 và P là điểm phải tìm. Vậy có ít nhất một điểm thuộc biên của hình vuông sao cho 14 nhỏ hơn tổng các khoảng cách từ điểm đó đến M và N. Nhận xét. Khi chứng minh a bé hơn một độ dài nào đó, ta có thể xét tổng của hai độ dài rồi chứng minh tổng đó lớn hơn 2a, khi đó tồn tại một độ dài lớn hơn a. 1.2.2. Nguyên lý Dirichlet Nguyên lí những cái lồng nhốt các chú thỏ đã được biết đến từ lâu. Nguyên lí này được phát biểu đầu tiên bởi nhà toán học người Đức Pete Gustava Lejeune Dirichlet (1805-1859). Nguyên lý ngăn kéo Dirichlet được ứng dụng trực tiếp nhất cho các tập hợp hữu hạn (hộp, ngăn kéo, chuồng bồ câu), nhưng nó cũng có thể được áp dụng đối với các tập hợp vô hạn không thể được đặt vào song ánh. Cụ thể trong trường hợp này nguyên lý ngăn kéo có nội dung là: "không tồn tại một đơn ánh trên những tập hợp hữu hạn mà codomain của nó nhỏ 8 hơn tập xác định của nó". Một số định lý của toán học như bổ đề Siegel được xây dựng trên nguyên lý này. 1.2.2.1. Nguyên lý Dirichlet cơ bản Dạng đơn giản nhất của nguyên lý Dirichlet, hay còn được gọi là nguyên lý nhốt thỏ vào lồng, như sau: “Nếu nhốt n + 1 thỏ vào lồng thì tồn tại một lồng có ít nhất hai con thỏ.” Tổng quát: Nếu n > km (n, k, m là các số tự nhiên) thì khi nhốt n con thỏ vào m lồng sẽ tồn tại một lồng chứa ít nhất k + 1 thỏ. Thật vậy, lồng nào cũng có không quá k thỏ thì m lồng có không quá mk thỏ, ít hơn n thỏ, vô lý. 1.2.2.2. Nguyên lý Dirichlet mở rộng Nguyên lý Dirichlet mở rộng được phát biểu như sau: n  m  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  con thỏ, ở đây ký hiệu   để ký hiệu phần nguyên của số  . Ta có thể dễ dàng chứng minh nguyên lý Dirichlet mở rộng như sau: n  m  1   n  1   n  1 Giả sử trái lại một chuồng thỏ không có đến   1      1 con, thì  m   m n  1 số thỏ trong mỗi chuồng đều nhỏ hơn hoặc bằng   con.  m  n 1  Từ đó suy ra tổng số con không vượt quá m    n  1 con. m  Đó là điều vô lí (vì có n chuồng thỏ). Vậy giả thiết phản chứng là sai. Nguyên lý mở rộng được chứng minh. 1.2.2.3. Nguyên lý Dirichlet cho diện tích Nguyên lý Dirichlet được phát biểu cho diện tích như sau:   m  9 Nếu K là một hình phẳng, còn K1 , K2 ,...Kn là các hình phẳng sao cho Ki  K với i  1, n , và K  K1  K2  ...  Kn , ở đây K là ký hiệu diện tích của hình phẳng K, còn K i là diện tích của hình phẳng K i , i  1, n ; thì tồn tại ít nhất hai hình phẳng H i , H j (1  i  j  n) sao cho H i , H j có điểm chung. (Ở đây ta nói rằng P là điểm tromg tập hợp A trên mặt phẳng nếu như tồn tại hình tròn tâm P bán kính đủ bé sao cho hình tròn này nằm trọn trong A.) Tương tự như nguyên lý Dirichlet cho diện tích, ta có các nguyên lý cho độ dài đoạn thẳng, thể tích các vật thể,… 1.2.2.4. Nguyên lý Dirichlet vô hạn Nguyên lý Dirichlet còn được phát biểu trong trường hợp vô hạn như sau: Nếu chia một tập vô hạn các quả táo và 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 quả táo. Nguyên lý Dirichlet mở rộng cho trường hợp vô hạn này đóng vai trò cũng hết sức quan trọng trong lý thuyết tập hợp điểm trù mật trên đường thẳng. Nó có vai trò quan trọng trong lý thuyết số nói riêng và trong toán học rời rạc nói chung (cho tất cả hình học tổ hợp). Nguyên lí Dirichlet tưởng chừng đơn giản như vậy, nhưng có là một công cụ hết sức có hiệu quả dùng để chứng minh nhiều kết quả hết sức sâu sắc của toán học. Nó đặc biệt có nhiều áp dụng trong các lĩnh vực khác nhau của toán học. Dùng 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 của một đối tượng với tính chất xác định. Tuy rằng với nguyên lí này ta chỉ 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 thực tế nhiều bài toán chỉ cần chỉ ra được sự tồn tại là đủ. Trong các vấn đề hình học tổ hợp, nguyên tắc Dirichlet cho phép chúng ta chứng minh sự tồn tại của một hình có những tính chất mong muốn mà không cần chỉ ra cụ thể hình đó. Ứng dụng to lớn của nguyên lý Dirichlet để giải quyết các bài toán hình học tổ hợp được trình bày qua các ví dụ sau đây: Ví dụ 1.3. Trong mặt phẳng cho 9 điểm có tọa độ nguyên, trong đó không có 3 điểm nào thẳng hàng. Hỏi trong số các tam giác được tạo thành từ 3 trong 9 điểm đó có ít nhất bao nhiêu tam giác có diện tích nguyên? 10 Giải. Cho tam giác MNP có tọa độ đỉnh M ( xM ; yM ) , N ( xN ; yN ) , P( xP ; yP ) . Ta có: Diện tích tam giác MNP là: SMNP  1 ( xP  xM )( yN  yM )  ( xN  xM )( yP  yM ) (*) 2 Xét 9 điểm M, N, P, Q, R, S, T, V, O có tọa độ nguyên thì tọa độ của mỗi điểm sẽ thuộc một trong các dạng sau: (chẵn, chẵn), (lẻ, lẻ), (lẻ, chẵn), (chẵn, lẻ). Do đó theo nguyên lí 9 Dirichlets tồn tại ít nhất    1  3 điểm thuộc cùng một dạng, tức là tọa độ cùng tính chẵn 4 lẻ, giả sử đó là M, N, P. Với hai điểm M, N có tọa độ cùng tính chẵn lẻ thì yN  yM , xN  xM đều là số chẵn nên diện tích tam giác có cạnh MN đều nguyên (do(*)). Tương tự diện tích các tam giác có cạnh NP, PM đều nguyên. Với mỗi 2 trong 3 điểm M, N, P kết hợp với 6 điểm còn lại thì được 6 tam giác có diện tích nguyên. Vậy có ít nhất 3.6 + 1 = 19 tam giác có diện tích nguyên. Ví dụ 1.4. Chứng minh rằng trong mọi khối đa diện lồi tồn tại ít nhất hai mặt có cùng số cạnh. Giải: Gọi X là mặt có số cạnh lớn nhất của khối đa diện. Giả sử mặt X có n cạnh. Khi đó vì có n mặt có cạnh chung với X, nên đa diện có ít nhất n  1 mặt. Vì X là mặt có số cạnh lớn nhất bằng n, nên mọi mặt của đa diện có số cạnh nhận một trong các giá trị {3,4,..., n}. Đa diện có ít nhất n + 1 mặt số cạnh của nó nhận một trong n – 2 giá trị (vì mặt lớn nhất có n cạnh. Vì thế theo nguyên lí Dirichlet suy ra có ít nhất hai mặt của đa diện cố cùng số cạnh. 1.3. Phương pháp quy nạp toán học 1.3.1. Giới thiệu Quy nạp toán học là một phương pháp chứng minh toán học dùng để chứng minh một mệnh đề về bất kỳ tập hợp nào được xếp theo thứ tự. Quy nạp toán học là một hình thức 11 chứng minh trực tiếp, thường được thực hiện theo hai bước. Khi cố gắng để chứng minh một mệnh đề là đúng cho tập hợp các số tự nhiên, bước đầu tiên, được gọi là bước cơ sở, là chứng minh mệnh đề đưa ra là đúng với số tự nhiên đầu tiên. Bước thứ hai, được gọi là bước quy nạp, là chứng minh rằng, nếu mệnh đề được giả định là đúng cho bất kỳ số tự nhiên nào đó, thế thì nó cũng đúng cho số tự nhiên tiếp theo. Sau khi chứng minh hai bước này, các quy tắc suy luận khẳng định mệnh đề là đúng cho tất cả các số tự nhiên. Trong thuật ngữ phổ biến, sử dụng phương pháp nói trên được gọi là sử dụng nguyên lý quy nạp toán học. Phương pháp này có thể được mở rộng để chứng minh các mệnh đề về các cấu trúc được thiết lập tổng quát hơn, chẳng hạn như cây; quá trình tổng quát này, được gọi là quy nạp cấu trúc, được sử dụng trong logic toán và khoa học máy tính. Quy nạp toán học theo nghĩa mở rộng này có quan hệ chặt chẽ với đệ quy. Quy nạp toán học, trong một số hình thức, là nền tảng của tất cả các phép chứng minh tính đúng đắn của các chương trình máy tính. Mỗi bài toán là một mệnh đề đúng hoặc sai. Mỗi mệnh đề như vậy lại phụ thuộc vào một biến số tự nhiên n. Một cách tổng quát ta ký hiệu P(n) là mệnh đề toán học phụ thuộc vào n, với n là số tự nhiên. Như vậy, thực chất phương pháp quy nạp toán học là chứng minh dãy mệnh đề đúng hoặc sai. Ví dụ 1.5. Trong mặt phẳng vẽ n đường tròn, bất kì hai đường tròn nào cũng cắt nhau tại hai điểm, và tại một điểm không có ba đường tròn nào cùng đi qua. Quan sát số miền N của mặt phẳng bị n đường tròn chia ra với n bằng 1, 2, 3, ta được N theo thứ tự là 2, 4, 8 (Hình 7). Bạn A cho rằng với mọi số tự nhiên n(n  1) thì N  2n , còn bạn B cho rằng N  2  n  n  1 . Kết luận của hai bạn là đúng hay sai ? Giải. Với n bằng 1, 2, 3 thì áp dụng công thức của bạn A ta có: 12 n  1  2n  21  2 n  2  2n  22  4 n  3  2 n  23  8 Với n bằng 1, 2, 3 thì áp dụng công thức của bạn B ta có: n  1  2  n  n  1  2  11  1  2 n  2  2  n  n  1  2  2  2  1  4 n  3  2  n  n  1  2  3  3  1  8 Với n = 4, thì áp dụng công thức của bạn A ta có: n  4  2n  24  16 Với n = 4, thì áp dụng công thức của bạn B ta có: n  4  2  n  n  1  2  4  4  1  14 Bằng cách vẽ bốn đường tròn có tính chất như đề bài, ta được N = 14 (Hình 8). Như vậy, kết luận của bạn A là sai. Kết luận của bạn B là đúng thêm trong một trường hợp nữa là n = 4. Theo phương pháp quy nạp, ta chứng minh được kết luận của bạn B là đúng. Nhận xét. Hai phép suy luận của bạn A và bạn B đều từ quan sát một số trường hợp riêng mà rút ra kết luận tổng quát, đó là phép quy nạp không hoàn toàn, chúng cho ta dự đoán về kết quả của bài toán. Ta đã bác bỏ dự đoán N  2n , còn để khẳng định dự đoán N  2  n  n  1 là đúng, ta phải chứng 13 tỏ rằng nó không chỉ đúng trong các trường hợp n bằng 1, 2, 3, 4 mà phải đúng với mọi số tự nhiên n > 1. Một trong các phương pháp thường dùng để giải quyết yêu cầu trên là phương pháp quy nạp toán học. Thông thường nội dung của phương pháp này như sau: 1.3.2. Phương pháp chứng minh quy nạp toán học Để chứng minh một mệnh đề P(n) là đúng với mọi n  N * , ta thường dùng phương pháp quy nạp toán học, được tiến hành theo hai bước như sau: Bước 1: Chứng minh P(n) đúng với n  1 . Bước 2: Với k là một số nguyên dương tùy ý, giả sử P(n) đúng với n  k  1 . Cần chứng minh P(n) cũng đúng khi n  k  1 . Chú ý: Đối với bài toán chứng minh P(n) đúng với mọi n  p với p là số tự nhiên cho trước thì: Bước 1: Chứng minh P(n) đúng với n  p . Bước 2: Với k  p là một số nguyên dương tùy ý, giả sử P(n) đúng với n  k . Cần chứng minh P(n) cũng đúng khi n  k  1 . 1.3.3. Quy nạp mạnh Quy nạp mạnh được thực hiện như sau: Để chứng minh mệnh đề P(n) đúng với mọi số tự nhiên n, ta thực hiện theo hai bước sau: Bước 1: Chứng minh P(n) đúng với n = 1. Bước 2: Giả sử P(n) đúng với 1,2,⋯,n. Chứng minh P(n+1) đúng. 1.3.4. Quy nạp bước nhảy Quy nạp bước nhảy được thực hiện như sau: Chứng minh mệnh đề P(n) đúng với mọi n, ta làm như sau: Bước 1: Chứng minh P(1),P(2),⋯,P(k) đúng. 14 Bước 2: Giả sử P(n) đúng. Ta chứng minh P(n+k) đúng. 1.3.5. Quy nạp lùi Quy nạp lùi được thực hiện như sau: Bước 1: Chứng minh P  ai  đúng với dãy  ai  là dãy con tăng thực sự của tập các số tự nhiên. Bước 2: Giả sử P(n) đúng, chứng minh P(n−1) đúng. Ta dùng phương pháp quy nạp toán học để chứng minh công thức mà bạn B đưa ra ở Ví dụ 1.5 là đúng trong ví dụ ở sau. Ví dụ 1.6. Cho n đường tròn trong mặt phẳng, hai đường tròn nào cũng cắt nhau tại hai điểm, không có ba đường tròn nào đi qua một điểm. Chứng minh rằng n đường tròn đó chia mặt phẳng thành 2  n  n  1 miền. Giải. Khẳng định trên đúng với n = 1, tức là n  1  2  n  n  1  2  11  1  2 , một đường tròn chia mặt phẳng thành hai miền. Giả sử khẳng định đó đúng với n = k tức là M k  2  k  k  1 , nói cách khác: k đường tròn chia mặt phẳng thành 2  k  k  1 miền. Ta sẽ chứng minh khẳng định đó đúng với n = k + 1, tức là: M k 1  2  (k  1)  k  1  1  2  k (k  1) . Thật vậy, đường tròn thứ k + 1 cắt mỗi một trong k đường tròn đã vẽ tại hai điểm nên đường tròn thứ k + 1 bị k đường tròn trên cắt tại 2k điểm và bị chia thành 2k cung. Mỗi cung này chia một miền chứa nó thành hai miền, như vậy số miền tăng thêm là 2k miền. Do đó: M k 1  M k  2k  2  (k  1)k  2k  2  k (k  1  2)  2  k (k  1) , tức là khẳng định trên đúng với n = k + 1. Kết luận: M = 2 + n (n – 1), với mọi số tự nhiên n  1. 15 CHƯƠNG 2: MỘT SỐ BÀI TOÁN HÌNH HỌC TỔ HỢP 2.1. Sử dụng phương pháp phản chứng – nguyên lý dirichlet Bài toán 2.1.1. Cho hình vuông ABCD có cạnh bằng a; M là trung điểm của cạnh AD, điểm a 2 E nằm trên BC thỏa mãn điều kiện 0  CE  . Qua M kẻ đường thẳng song song với AE, cắt cạnh CD tại F. Chứng minh rằng hình thang AMFE không thể là hình thang cân. Giải. (Hình 9) Giả sử AMFE là hình thang cân thì AM = FE (*) và MAE  FEA , mà MAE  BEA => FEA  BEA => EA là phân giác của (góc ngoài của ∆ EFC). Mặt khác CA là phân giác của BCD (tính chất đường chéo của hình vuông), suy ra A là tâm đường tròn bàng tiếp trong ECF của ∆ EFC (đường tròn này tiếp xúc với CE và CF lầ lượt tại B và D). Lại có a a a  BE  ; EF  BE  DF  BE  2 2 2  EF  AM 0  CE  Hình 9 Mâu thuẫn với (*). Vậy AMFE không thể là hình thang cân. ̂ , 𝐴̂ > 𝐷 ̂ Bài toán 2.1.2. Chứng minh rằng trong tứ giác ABCD, nếu 𝐴̂ = 𝐵̂, 𝐶̂ = 𝐷 thì AD < BC. Giải. (Hình 10) Ta sẽ chứng minh AD  BC là sai. Thật vậy, gọi giao điểm của AD và BC là E ta có: ̂ = 𝐴𝐵𝐶 ̂ (giả thiết). 𝐷𝐴𝐵 ̂ = 𝐸𝐵𝐴 ̂ => ∆ EAB cân tại E => EA = EB. Suy ra 𝐸𝐴𝐵 Giả sử AD = BC => AD + EA = BC + EB => ED = EC Hình 10 => ∆ EDC cân tại E => trái với giả thiết. ̂ , cũng trái với giả Giả sử: AD > BC => AD + EA > BC + EB => ED > EC => 𝐶̂ > 𝐷 thiết. 16 Vậy chỉ có thể là AD < BC. Bài toán 2.1.3. Cho đường tròn có đường kính 8 và ba điểm M , N , P tùy ý. Chứng minh rằng tồn tại một điểm Q nằm trên đường tròn sao cho QM  QN  QP  12 . Giải. (Hình 11) Gọi QR là một đường kính của đường tròn . Ta có: MQ  MR  QR  8 NQ  NR  QR  8 PQ  PR  QR  8 Suy ra: ( MQ  NQ  PQ)  ( MR  NR  PR)  24. Trong hai tổng ( MQ  NQ  PQ) và ( MR  NR  PR) , tồn tại một tổng lớn hơn hoặc bằng 12. Do đó trong hai điểm Q và R tồn tại một điểm, chẳng hạn Q thỏa mãn: ( MQ  NQ  PQ)  12 Suy ra điều phải chứng minh. Bài toán 2.1.4. Cho đường tròn đường kính 6, trên đường tròn ta lấy 50 điểm. Chứng minh rằng tồn tại một điểm trên đường tròn mà tổng các khoảng cách từ điểm đó đến tất cả 50 điểm được đánh dấu lớn hơn 150. Giải. (Hình 12) Gọi MN là đường kính của đường tròn. Trên đường tròn ta lấy các điểm P1 , P2 ,..., P50 ( P1 , P2 ,..., P50 không trùng với M, N). Ta có: PM  P1 N  MN  6 1 P2 M  P2 N  MN  6 ... P50 M  P50 N  MN  6 Suy ra: ( PM  P2 M  ...  Pn M )  ( PN  P2 N  ...  Pn N )  50MN  300 1 1 Hình 12