Luận văn Hình học tổ hợp với các phương pháp chứng minh

Nội dung tài liệu: Luận văn Hình học tổ hợp với các phương pháp chứng minh

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN ĐỨC ĐẮC HÌNH HỌC TỔ HỢP VỚI CÁC PHƯƠNG PHÁP CHỨNG MINH LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - Năm 2018
2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN ĐỨC ĐẮC HÌNH HỌC TỔ HỢP VỚI CÁC PHƯƠNG PHÁP CHỨNG MINH Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8460101.13 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. Nguyễn Hữu Điển Hà Nội - Năm 2018
3. Mục lục Lời nói đầu 1 Chương 1. Tổng quan về các phương pháp chứng minh 3 1.1 Phương pháp quy nạp . . . . . . . . . . . . . . . . . . . . 3 1.2 Phương pháp phản chứng . . . . . . . . . . . . . . . . . . 6 1.3 Nguyên lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Nguyên lý cực hạn . . . . . . . . . . . . . . . . . . . . . . 10 Chương 2. Các phương pháp chứng minh cho các bài toán hình học tổ hợp 13 2.1 Tổng quan về hình học tổ hợp . . . . . . . . . . . . . . . . 13 2.2 Vận dụng phương pháp quy nạp . . . . . . . . . . . . . . 15 2.3 Vận dụng phương pháp phản chứng . . . . . . . . . . . . 18 2.4 Vận dụng nguyên lý Dirichlet . . . . . . . . . . . . . . . . 20 2.5 Vận dụng nguyên lý cực hạn . . . . . . . . . . . . . . . . . 24 Chương 3. Ứng dụng phương pháp theo chủ đề hình học. Các bài toán thi Olympic trong và ngoài nước 28 3.1 Hệ các điểm và đường cong . . . . . . . . . . . . . . . . . 28 3.1.1 Nhận xét về vật thể lồi . . . . . . . . . . . . . . . . 28 3.1.2 Đếm giao điểm . . . . . . . . . . . . . . . . . . . . 32 3.1.3 Đếm số tam giác . . . . . . . . . . . . . . . . . . . 35 3.1.4 Đếm số đa giác . . . . . . . . . . . . . . . . . . . . 37 3.1.5 Các bài toán với hệ điểm và đường thẳng . . . . . 39 3.1.6 Các bài toán với hệ đoạn thẳng . . . . . . . . . . . 41 3.1.7 Các bài toán với đa giác không lồi . . . . . . . . . 43 3.2 Hệ các đường cong và miền . . . . . . . . . . . . . . . . . 48 i
4. 3.2.1 Chia mặt phẳng bằng hệ các đường . . . . . . . . 49 3.2.2 Chia mặt phẳng bằng đường cong kín . . . . . . . 53 3.2.3 Chia một đa giác lồi . . . . . . . . . . . . . . . . . 55 3.2.4 Chia không gian . . . . . . . . . . . . . . . . . . . 58 3.3 Phép phủ và đóng gói . . . . . . . . . . . . . . . . . . . . 59 3.3.1 Các đối tượng phủ nhau . . . . . . . . . . . . . . . 59 3.3.2 Phép phủ với hệ các hình tròn bằng nhau . . . . . 62 3.3.3 Bài toán về đóng gói . . . . . . . . . . . . . . . . . 65 3.4 Phép tô màu . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.4.1 Màu của các điểm . . . . . . . . . . . . . . . . . . . 67 3.4.2 Tô màu miền . . . . . . . . . . . . . . . . . . . . . 70 3.4.3 Tô màu bàn cờ . . . . . . . . . . . . . . . . . . . . . 72 3.5 Các bài toán thi Olympic trong và ngoài nước . . . . . . . 74 Kết luận 85 Tài liệu tham khảo 86 ii
5. Lời nói đầu Hình học tổ hợp là một bộ phận của hình học nói chung và là một nhánh của tổ hợp. Những 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ì thế các bài toán mang đặc trưng rõ nét của toán học rời rạc. Các bài toán trong hình học tổ hợp rất đa dạng về nội dung và phương pháp giải. Nhiều bài toán phát biểu đơn giản, có thể thấy đúng ngay nhưng để giải được thì cần trang bị những kiến thức riêng về hình học tổ hợp và hình học. Khi đó bài toán sẽ trở nên rất dễ dàng. Tuy nhiên cũng có những bài đòi hỏi kiến thức chuyên sâu, và thậm chí có nhiều bài toán hình học tổ hợp tổng quát cho không gian vẫn chưa có lời giải. Hình học tổ hợp ở nước ta được coi như nội dung dành cho học sinh khá, giỏi bậc Trung học cơ sở và thường xuyên xuất hiện trong các đề thi học sinh giỏi, đề thi tuyển sinh THPT chuyên, đề thi Olympic truyền thống 30/4, . . . và trong các đề thi Olympic Toán quốc tế. Vì vậy trong luận văn này em xin trình bày đề tài: “Hình học tổ hợp với các phương pháp chứng minh”. Trong luận văn này em đưa ra một số phương pháp chứng minh thường sử dụng cho các bài toán hình học tổ hợp và ứng dụng của các phương pháp đó vào chứng minh các bài toán theo chủ đề, có trong các đề thi tuyển sinh vào lớp 10 chuyên, thi học sinh giỏi trong và ngoài nước thời gian qua. Bố cục của luận văn này gồm ba chương: Chương 1. Tổng quan về các phương pháp chứng minh. Chương này trình bày các phương pháp cơ bản được vận dụng để giải các bài toán nói chung như: phương pháp quy nạp, nguyên lý Dirichlet, nguyên 1
6. lý cực hạn. Ngoài ra phương pháp phản chứng cũng được sử dụng nhiều nhưng đan xen cùng các phương pháp khác. Chương 2. Các phương pháp chứng minh cho các bài toán Hình học tổ hợp. Chương này đưa ra tổng quan về Hình học tổ hợp và ví dụ minh họa cách áp dụng các phương pháp chứng minh cho các bài toán Hình học tổ hợp. Chương 3. Ứng dụng phương pháp theo chủ đề hình học; các bài toán thi học sinh giỏi, thi Olympic trong và ngoài nước. Chương này đưa ra một số bài toán Hình học tổ hợp theo chủ đề như: Bài toán về hệ điểm và đường cong; bài toán đường cong và miền; bài toán phủ hình và bao hình; bài toán tô màu; các bài toán có trong các đề thi học sinh giỏi lớp 9 các tỉnh, các đề thi tuyển sinh THPT chuyên, các đề thi Olympic Toán. Để hoàn thành được luận văn này, em xin được gửi lời cảm ơn sâu sắc tới PGS. TS Nguyễn Hữu Điển đã dành thời gian hướng dẫn, chỉ bảo, tận tình giúp đỡ em trong quá trình xây dựng đề tài cũng như hoàn thiện luận văn. Em cũng xin được gửi lời cảm ơn chân thành tới Ban giám hiệu, phòng sau Đại học, khoa Toán - Cơ - Tin học trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi cho em trong suốt quá trình học tập tại trường. Em xin cảm ơn gia đình, bạn bè và tất cả mọi người đã quan tâm, tạo điều kiện, giúp đỡ em hoàn thành luận văn này. Mặc dù đã có nhiều cố gắng nhưng do thời gian và khả năng có hạn nên các vấn đề trong luận văn vẫn chưa được trình bày sâu sắc và không thể tránh khỏi có những sai sót trong cách trình bày. Rất mong được sự góp ý xây dựng của các thầy cô và các bạn. Em xin chân thành cảm ơn! Hà Nội, ngày 28 tháng 9 năm 2018 Học viên Nguyễn Đức Đắc 2
7. Chương 1 Tổng quan về các phương pháp chứng minh Chương này liệt kê các phương pháp điển hình được vận dụng để giải các bài toán trung học phổ thông như: phương pháp quy nạp, phương pháp phản chứng, nguyên lý Dirichlet, nguyên lý cực hạn. Mỗi phương pháp được trình bày độc lập nhưng khi sử dụng chúng đan xen cùng các phương pháp khác ta giải được nhiều bài tập hay và thú vị. 1.1 Phương pháp quy nạp Phương pháp quy nạp có vai trò vô cùng quan trọng trong toán học, khoa học và cuộc sống. Đối với nhiều bài toán trong chương trình toán phổ thông là những bài toán logic, tức những bài toán không mẫu mực, phương pháp quy nạp cho ta nhiều cách giải hữu hiệu. Suy diễn là quá trình từ “tính chất” của tập thể suy ra tính chất của cá thể, nên luôn luôn đúng, còn quá trình ngược lại, tức quá trình quy nạp: đi từ “tính chất” của một số các thể suy ra “tính chất” của tập thể thì không phải lúc nào cũng đúng, mà quá trình này chỉ đúng khi nó thỏa mãn một số điều kiện nào đó, tức thỏa mãn nguyên lý quy nạp: Nếu khẳng định S(n) thỏa mãn hai điều kiện sau: (a) Đúng với n = k0 (số tự nhiên nhỏ nhất mà S(n) xác định). (b) Từ tính đúng đắn của S(n) đối với n = t (hoặc đối với mọi giá trị của n (k0 ≤ n ≤ t)) (t ≥ k0), ta cần chứng minh tính đúng đắn của 3
8. S(n) đối với n = t + 1. Khi S(n) đúng với mọi n ≥ k0. Giả sử khẳng định S(n) xác định với mọi n ≥ t0. Để chứng minh S(n) đúng 8n ≥ t0 bằng quy nạp ta cần thực hiện theo hai bước sau: 1. Cơ sở quy nạp: chứng minh rằng S(n) đúng với số tự nhiên n = t0. 2. Quy nạp: giả sử khẳng định S(n) đã đúng đến n = t (hoặc đối với mọi n (t0 ≤ n ≤ t)) (t ≥ t0). Trên cơ sở giả thiết này ta chứng minh tính đúng đắn của S(n) đối với n = t + 1, tức S(t + 1) đúng. Nếu cả hai bước trên thỏa mãn, thì theo nguyên lý quy nạp S(n) đúng với 8n ≥ t0. Giả thiết ở bước quy nạp rằng mệnh đề đúng với n = t được gọi là giả thiết quy nạp. Ví dụ 1.1.1. Chứng minh rằng mệnh đề S(n) sau đúng với tất cả số tự nhiên n n(n + 1) 0 + 1 + 2 + ··· + n = . 2 Giải. 1. Cơ sở quy nạp: Ta có S(0) bằng 0 · (0 + 1) 0 = . 2 Hai vế bằng nhau nên mệnh đề đúng với n = 0. Vì vậy S(0) đúng. 2. Quy nạp: Giả sử S(k) đúng, ta phải chứng minh S(k + 1) cũng đúng, tức là (k + 1)((k + 1) + 1) 0 + 1 + 2 + ··· + k + k + 1 = . 2 Sử dụng giả thiết quy nạp rằng S(k) đúng, vế trái có thể viết thành k(k + 1) k(k + 1) + 2(k + 1) + (k + 1) = 2 2 (k + 1)(k + 2) = 2 (k + 1)((k + 1) + 1) = . 2 Vậy S(k + 1) cũng đúng. Vì cả bước cơ sở quy nạp và bước quy nạp đã được thực hiện, mệnh đề S(n) đúng với mọi số tự nhiên n.  4
9. 1 Ví dụ 1.1.2. Cho x + , x 6= 0 là một số nguyên. Chứng minh rằng với mọi x số nguyên dương n, số 1 T(n, x) = xn + xn cũng là số nguyên. Giải. Bài toán được giải quyết bằng quy nạp. 1 1. Cơ sở quy nạp: Với n = 1, theo giả thiết ta có T(1, x) = x + là số x nguyên, nên khẳng định đúng. 2. Quy nạp: Giả sử với n = k khẳng định đúng, nghĩa là 1 T(k, x) = xk + xk là số nguyên. Với n = k + 1 số 1 T(k + 1, x) = xk+1 + xk+1  1 1   1  = x + xk + − xk−1 + . x xk xk−1 1 1 1 Theo giả thiết quy nạp, các số x + , xk−1 + , xk + đều nguyên x xk−1 xk nên T(k + 1, x) là số nguyên và khẳng định đúng với mọi số nguyên dương n.  Ví dụ 1.1.3. Chứng minh rằng A(n) = 7n + 3n − 1 chia hết cho 9 với mọi số tự nhiên n. Giải. Bài toán được giải quyết bằng quy nạp. 1. Cơ sở quy nạp: Với n = 0, ta có A(0) = 0 chia hết cho 9, nên khẳng định đúng. 2. Quy nạp: Giả sử A(k) chia hết cho 9 với k 2 N. Ta sẽ chứng minh A(k + 1) cũng chia hết cho 9. Thật vậy, ta có A(k + 1) = 7k+1 + 3(k + 1) − 1 = 7A(k) − 9(2k − 1). Theo giả thiết quy nạp thì A(k) chia hết cho 9, do dó A(k + 1) cũng chia hết cho 9. Vậy A(n) chia hết cho 9 với mọi số tự nhiên n.  5
10. 1.2 Phương pháp phản chứng Để chứng minh một bài toán bằng phương pháp phản chứng gồm 3 bước: Bước 1 (Phủ định kết luận): Ta giả sử kết luận của bài toán là không đúng. 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): Như vậy kết luận của bài toán là đúng. Ưu điểm của phương pháp này là ta đã 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. Ví dụ 1.2.1 ([4]). Người ta đồn rằng ở một ngôi đền nọ rất thiêng do ba vị thần ngự trị: thần Thật Thà (luôn luôn nói thật), thần Dối Trá (luôn luôn nói rối) và thần Khôn Ngoan (khi nói thật, khi nói dối). Các vị thần đều ngự trên bệ thờ và sẵn sàng trả lời câu hỏi khi có người thỉnh cầu. Nhưng hình dạng của ba vị thần giống hệt nhau nên người ta không biết vị thần nào trả lời để mà tin hay không tin. Một hôm, một học giả từ phương xa đến gặp các vị thần để xin thỉnh cầu. Bước vào miếu, học giả hỏi thần ngồi bên phải: - Ai ngồi cạnh ngài? - Đó là thần Dối Trá. Tiếp đó hỏi thần ngồi giữa: - Ngài là thần gì? - Tôi là thần Khôn Ngoan. Cuối cùng ông ta quay sang hỏi thần ngồi bên trái: - Ai ngồi cạnh ngài? - Đó là thần thật thà. Nghe xong học giả khẳng định mỗi vị thần là gì. Bạn hãy cho biết học giả đó đã suy luận như thế nào? 6