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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:90

Thêm vào BST

Báo xấu

45
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Hình học tổ hợp với các phương pháp chứng minh

ĐẠ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
ĐẠ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
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
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
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
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
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
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 ∀n ≥ 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 ∀n ≥ 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
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 ) = x n + n x 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 ) = x k + xk là số nguyên. Với n = k + 1 số 1 T (k + 1, x ) = x k+1 + k+1 x 1 k 1 k −1 1 = x+ x + k − x + k −1 . x x x 1 1 1 Theo giả thiết quy nạp, các số x + , x k−1 + k−1 , x k + k đều nguyên x x x 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 ∈ 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
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
Giải. Câu hỏi của học giả cho ba vị thần nhưng đều nằm mục đích: thần ngồi giữa là thần gì? Học giả đã nhận được ba câu trả lời với thông tin hoàn toàn khác nhau về vị thần ngồi giữa. Học giả có thể suy luận như sau (có thể vì có nhiều cách suy luận khác cũng giải được bài toán này): 1. Nếu thần ngồi bên trái là thần Dối Trá thì thần bên phải là thần Thật Thà hoặc Khôn Ngoan. - Nếu thần ngồi bên phải là Thật Thà thì ngồi giữa là thần Dối Trá (do câu trả lời của thần Thật Thà). Điều này vô lý, vì bên trái cũng là thần Dối Trá. - Nếu thần ngồi bên phải là Khôn Ngoan, thì ngồi giữa là thần Thật Thà. Điều này cũng vô lý, vì ngài đã nói: “Tôi là thần Khôn Ngoan”. Vậy bên trái không phải là thần Dối Trá. 2. Nếu thần ngồi bên phải là thần Dối Trá thì thần ngồi giữa là thần Thật Thà hoặc Khôn Ngoan. - Thần ngồi giữa không phải là Thật Thà, vì ngài đã nói: “Tôi là thần Khôn Ngoan”. - Nếu thần ngồi giữa là Khôn Ngoan, thì thần ngồi bên trái là Thật Thà. Điều này cũng vô lý, vì ngài đã nói: “Ngồi giữa là thần Thật Thà”. Vậy bên phải không phải là thần Dối Trá. 3. Vậy chỉ còn ngồi giữa là thần Dối Trá. Như vậy bên trái không phải là thần Thật Thà, vì ngài đã nói: “Ngồi giữa là thần Thật Thà” Thế thì bên trái là Khôn Ngoan. Cuối cùng, bên phải là thần Thật Thà. Ví dụ 1.2.2 ([4]). Nếu g, h, k là ba đường thẳng phân biệt trong mặt phẳng sao cho g và h song song với k, thì g song song với h. Chứng minh. Ta giả sử ngược lại g không song song với h. Vì g và h nằm trên cùng mặt phẳng, mà không song song với nhau thì chúng cắt nhau tại một điểm P. Trong trường hợp này từ P có hai đường thẳng song song với k. Điều này không thể được vì ở phổ thông ta công nhận mệnh đề sau luôn đúng: Qua một điểm đã cho chỉ tồn tại duy nhất một đường thẳng song song với một đường thẳng đã cho. Như vậy điều giả sử là sai, do đó kết luận của bài toán là đúng. 7
1.3 Nguyên lý Dirichlet Người đầu tiên đề xuất nguyên lý này được cho là nhà toán học người Đức Johann Dirichlet (1805–1859) khi ông đề cập tới nguyên lý với tên gọi “nguyên lý ngăn kéo” (The Drawer Principle). Ngoài ra nguyên lý này còn được biết đến như nguyên lý chim bồ câu hoặc nguyên lý những cái lồng nhốt thỏ. Nguyên lý Dirichlet cơ bản: Nhốt n + 1 thỏ vào n lồng thì tồn tại một lồng có ít nhất hai thỏ. Chứng minh. Giả sử ngược lại mỗi lồng chỉ nhốt nhiều nhất một con thỏ, như vậy số thỏ nhỏ hơn hoặc bằng số lồng n, mà theo giả thiết số thỏ là n + 1 nhiều hơn số lồng, điều này dẫn đến vô lý. Từ đó suy ra có ít nhất 2 con thỏ trong cùng một lồng. Dù mở rộng bất cứ cách nào, nguyên lý này đều được chứng minh bằng phương pháp phản chứng. Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k N hộp, N không chia hết cho k, thì sẽ tồn tại một hộp chứa ít nhất +1 k đồ vật. Nguyên lý Dirichlet vô hạn: 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. Nguyên lý Dirichlet đối với đoạn thẳng: Ta kí hiệu d( I ) là độ dài của đoạn thẳng I nằm trong mặt phẳng. Cho A là một đoạn thẳng, A1 , A2 , . . . , An là các đoạn thẳng sao cho Ai ⊂ A với i = 1, n và d( A) < d( A1 ) + d( A2 ) + . . . + d( An ). Khi đó ít nhất có hai đoạn thẳng trong số các đoạn thẳng trên có một điểm trong chung. Chứng minh. Giả sử không có hai đoạn thẳng nào trong các đoạn thẳng đã cho có điểm trong chung. Khi đó d ( A1 ∪ A2 ∪ . . . ∪ A n ) = d ( A1 ) + d ( A2 ) + . . . + d ( A n ) > d ( A ). Mà từ Ai ⊂ A, i = 1, n, ta có d( A1 ∪ A2 ∪ . . . ∪ An ) ≤ d( A). 8
Hai bất đẳng thức trên mâu thuẫn với nhau nên điều giả sử là sai. Vậy có ít nhất có hai đoạn thẳng trong số các đoạn thẳng trên có một điểm trong chung. Ví dụ 1.3.1. Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 40. Hỏi rằng có ít nhất bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau? Giải. Theo nguyên lý Dirichlet, số học sinh cần tìm là 42 vì ta có 41 kết quả điểm thi khác nhau. Ví dụ 1.3.2. Trong một phòng họp n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau. Giải. Số người quen của mỗi người trong phòng họp nhận các giá trị từ 0 đến n − 1. Rõ ràng trong phòng không thể đồng thời vừa có người có số người quen là 0 (tức là không quen ai) và vừa có người có số người quen là n − 1 (tức là quen tất cả). Vậy theo nguyên lý Dirichlet tồn tại một nhóm có ít nhất 2 người, tức là luôn tìm được ít nhất 2 người có ngươi quen là như sau. Ví dụ 1.3.3. Trong một tháng 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trận nhưng chơi không quá 45 trận. Chứng minh rằng tìm được một giai đoạn gồm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận. Giải. Gọi a j là số trận mà đội chơi từ ngày đầu tháng đến hết ngày j. Khi đó 1 ≤ a1 < a2 < · · · < a30 ≤ 45. Hay 15 ≤ a1 + 14 < a2 + 14 < · · · < a30 + 14 ≤ 59. Sáu mươi số nguyên a1 , a2 , . . . , a30 , a1 + 14, a2 + 14, . . . , a30 + 14 nằm giữa 1 và 59. Do đó theo nguyên lý Dirichlet phải có ít nhất 2 trong số 60 này bằng nhau. Vì vậy tồn tại i và j sao cho ai + 14 = a j (i < j). Điều này có nghĩa là từ ngày i + 1 đến hết ngày j đội đã chơi đúng 14 lần. 9
1.4 Nguyên lý cực hạn Ví dụ 1.4.1 ([4]). Ngày xửa ngày xưa có một ông vua có rất nhiều người con và có số vàng rất lớn. Trước khi chết ông vua muốn chia số vàng cho các con, nhưng ông vua không muốn chia đều cho các con mà đặt ra luật lệ: Mỗi người nhận được số vàng lớn hơn hoặc bằng trung bình cộng của hai người anh em nào đó của họ. Hãy chỉ ra rằng có ít nhất ba người con được chia cùng số lượng vàng. Giải. Bài toán có thể diễn đạt lại: Mỗi một người con được chia số lượng vàng ký hiệu là a thì có hai người anh em có số lượng vàng là b và c sao b+c cho a ≥ . 2 Bây giờ ta gọi a là số lượng vàng nhỏ nhất của một người con đã được chia (điều này luôn luôn xảy ra vì số con vua là hữu hạn) và cũng có hai người anh em có số lượng vàng b và c như ở trên. Ta thấy ngay a ≤ b và a ≤ c. Công theo vế hai bất đẳng thức này ta nhận được 2a ≤ b + c, hay b+c là a ≤ . Ta có kết quả 2 b+c a≤ ≤ a. 2 b+c Suy ra a = . Nhưng điều này chỉ xảy ra khi những bất đẳng thức 2 a ≤ b và a ≤ c xảy ra dấu bằng. Nghĩa là a = b = c. Ta chú ý rằng để giải bài toán trên phải dùng đến “phần tử nhỏ nhất” a. Chỉ có phần tử này cho ta thêm thông tin là nhỏ hơn các phần tử khác vốn bình đẳng. Tuy thêm được chút thông tin như vậy nhưng bài toán đã được giải nhờ chính những phần tử này. Trong toán học thường thường người ta nghiên cứu những tập hợp những đối tượng được xác định theo một nghĩa nào đấy bình đẳng nhau, nhưng những tính chất của chúng biết rất ít. Trong trường hợp như vậy để giải những bài toán người ta xem xét những phần tử trong tập hợp có những tính chất đặc biệt nào đó như “tính cực tiểu” hoặc “tính cực đại”. Bởi vì ngoài những tính chất được cho trong đề bài toán, những phần tử cực tiểu hoặc cực đại có thêm những tính chất mà chúng cho 10
phép đưa ta đến kết luận bài toán cho chính các phần tử này hoặc cho phần tử còn lại nói chung. Nguyên lý cực hạn có dạng đơn giản sau: Nguyên lý 1 ([7]). Trong tập hợp hữu hạn và khác rỗng các số thực luôn có thể chọn được số bé nhất và số lớn nhất. Nguyên lý 2 ([7]). Trong một tập hợp khác rỗng các số tự nhiên luôn luôn có thể chọn được số bé nhất. Nguyên lý cực hạn thường được sử dụng kết hợp với các phương pháp khác, đặc biệt là phương pháp phản chứng, được vận dụng trong trường hợp tập các giá trị cần khảo sát chỉ là tập hợp hữu hạn (nguyên lý 1) hoặc có thể vô hạn nhưng tồn tại một phần tử lớn nhất hoặc nhỏ nhất (nguyên lý 2). Ví dụ 1.4.2. Với những số dương x, y và z biết rằng 2y 2z 2x x= ,y = ,z = . 1+y 1+z 1+x Chứng minh rằng x = y = z = 1. Giải. Vai trò các số x, y và z tương đương, ta lấy x là số nhỏ nhất trong 2x các số. Khi đó x ≤ = z. Ta chia hai vế bất đẳng thức sau cùng cho 1+x 2 x, điều này có thể làm được do x > 0, và ta nhận được 1 ≤ . Từ 1+x đây suy ra x ≤ 1. Trong trường hợp này 2y = x ≤ 1 ⇔ 2y ≤ 1 + y ⇔ y ≤ 1. 1+y 2y 2y Suy ra 1 + y ≤ 2, vì thế x = ≥ = y. Bất đẳng thức này chỉ có 1+y 2 khả năng khi nếu x = y, vì x là số nhỏ nhất trong các số x, y, z. Điều kiện 2y 2x x= trở thành dạng x = , từ đây tìm được x = 1. Như vậy 1+y 1+x 2x 2z z= = 1, y = = 1. 1+x 1+z 11
Ví dụ 1.4.3. Tại cuộc dạ hội, không có một người đàn ông nào khiêu vũ với tất cả những người đàn bà có mặt, nhưng mỗi người đàn bà khiêu vũ với ít nhất một người đàn ông. Chứng minh rằng tồn tại hai cặp khiêu vũ bg và b0 g0 , ở đó b không khiêu vũ với g0 và đồng thời g không khiêu vũ với b0 . Giải. Ký hiệu b là người đàn ông khiêu vũ với số lượng đàn bà lớn nhất. Còn g0 là người đàn bà không khiêu vũ với b, và b0 là người đàn ông khiêu vũ với g0 . Giữa những bạn khiêu vũ của b, phải tồn tại ít nhất một người đà bà g, mà người này không khiêu vũ với b0 (nếu ngược lại thì số bạn khiêu vũ của b0 sẽ lớn hơn của b). Như vậy cặp bg và b0 g0 là lời giải của bài toán. 12
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 Các bài toán về Hình học tổ hợp thường không đòi hỏi vận dụng quá nhiều định lý, nhiều tính toán phức tạp mà đòi hỏi lập luận chặt chẽ, chính xác, hợp logic. Để giải những bài toán này, có nhiều cách tiếp cận riêng. Sau đây là tổng quan về Hình học tổ hợp và một số phương pháp thường dùng để giải các bài toán về Hình học tổ hợp. 2.1 Tổng quan về hình học tổ hợp Thật khó để định nghĩa chính xác thế nào là Hình học tổ hợp vì bộ môn này có liên quan chặt chẽ chỉ với một số nội dung, chẳng hạn như hình học rời rạc, topo tổ hợp, và đặc biệt là lý thuyết về các hình lồi. Theo nhà toán học Thụy Sĩ Hugo HadWiger (1908–1981, là người đã đặt ra tên cho môn học này), đối tượng của Hình học tổ hợp là nghiên cứu các vấn đề liên quan đến việc tìm ra cách “tối ưu” các hình. Trong cuốn sách “Một số chuyên đề hình học tổ hợp” của thầy Nguyễn Hữu Điển ([6]) cho rằng “Không dễ để phân biệt rạch ròi Hình học tổ hợp trong hình học nói chung. Nhưng trong đó, ta xét các bài toán có liên quan đến việc tìm và đặc trưng hóa tối ưu theo nghĩa nào đó số lượng điểm hoặc một số dạng hình. Ví dụ như cho một đa giác được phủ bởi những đa giác khác, một số hình vuông nằm trong một hình vuông đã cho, ... Tất cả những bài toán này đều liên quan đến việc nghiên cứu và so sánh những tổ hợp khác nhau của những phần tử mà chúng thỏa mãn những điều kiện đã cho. Để giải những bài 13
toán này, người ta sử dụng những kiến thức toán học có tính chất tổ hợp cho hình học.” Trong cuốn sách “Các bài toán hình học tổ hợp” của giáo sư Phan Huy Khải ([7]) chỉ nhấn mạnh “Các bài toán hình học tổ hợp thường liên quan đến các đối tượng là các tập hữu hạn. 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 khi 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)”. Trong cuốn sách “Hình học tổ hợp” của thầy giáo Vũ Hữu Bình ([1]) cũng chỉ khẳng định “Nói một cách nôm na, một 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 (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à phương pháp phân chia và kết hợp các thành phần với nhau”. Một đặc trưng khác khi nghiên cứu Hình học tổ hợp là nhiều bài toán phát biểu đơn giản, có thể dễ dàng hình dung và 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 hình học tổ hợp tổng quát cho không gian vẫn chưa có lời giải. Những bài toán này đã tạo nên sự hấp dẫn cho các nhà toán học nghiên cứu, cho cả học sinh và sinh viên yêu toán tìm hiểu. Được thể hiện là trong các cuộc thi cho học sinh phổ thông, những bài toán Hình học tổ hợp xuất hiện khá nhiều. Các bài toán hình học tổ hợp thường nghiên cứu các tổ hợp khác nhau của một hình để chọn ra những hình có cùng tính chất nào đó. Những tính chất đó có thể liên quan đến các điểm (điểm nằm trong một hình, sự tồn tại các điểm khá gần nhau, các đỉnh là đỉnh cá đa giác đặc biệt. . .), các đường thẳng (các đường thẳng giao nhau, đồng quy, tạo lưới ô vuông. . .), các hình (hình nằm trong một hình, hình phủ một hình, cắt ghép cá hình. . .), các góc (đánh giá góc, tồn tại góc đủ lớn hay đủ nhỏ. . .). Các bài toán về Hình học tổ hợp thường không đòi hỏi vận dụng quá nhiều định lý, nhiều tính toán phức tạp mà đòi hỏi lập luận chặt chẽ, chính xác, hợp logic. Để giải những bài toán này, có nhiều cách tiếp cận 14
riêng. Sau đây là một số phương pháp thường dùng để giải các bài toán về Hình học tổ hợp. 2.2 Vận dụng phương pháp quy nạp Ví dụ 2.2.1. Chứng minh rằng trên mặt phẳng n đường thẳng khác nhau cùng đi qua một điểm, chia mặt phẳng thành 2n phần khác nhau. 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 = 1, ta có một đường thẳng. Nó chia mặt phẳng thành hai phần, nên khẳng định đúng. 2. Quy nạp: Giả sử với n = k khẳng định đã đúng, nghĩa là k đường thẳng tùy ý cùng đi qua một điểm M đã chia mặt phẳng thành 2k phần khác nhau. Xét k + 1 đường thẳng khác nhau tùy ý cùng đi qua một điểm. Kí hiệu các đường này lần lượt bằng δ1 , δ2 , . . . , δk , δk+1 . Theo giả thiết quy nạp k đường thẳng δ1 , δ2 , . . . , δk đã chia mặt phẳng thành 2k phần khác nhau. Hình 2.1 Vì các đường thẳng đều khác nhau và cùng đi qua điểm M, nên tồn tại các chỉ số s, t (1 ≤ s, t ≤ k) để δk+1 là đường thẳng duy nhất nằm trong góc được lập nên bởi δs và δt . Khi đó δk+1 chia hai phần mặt phẳng được giới hạn bởi δs và δt thành bốn phần. Bởi vậy k + 1 đường thẳng δ1 , δ2 , . . . , δk , δk+1 chia mặt phẳng thành 2k − 2 + 4 = 2k + 2 = 2(k + 1) 15
phần khác nhau. Khẳng định được chứng minh. Ví dụ 2.2.2 ([5]). Cho nửa đường tròn H bán kính 1 và đường kính AB. Trong nó vẽ đường tròn nội tiếp k1 với bán kính 12 . Dãy những đường tròn k1 , k2 , . . . với các bán kính tương ứng r1 , r2 , . . . được xác định như sau: đường tròn k n+1 tiếp xúc với nửa đường tròn H, đường tròn k n và với đoạn thẳng AB, k = 1, 2, 3, . . . Chứng minh rằng với mọi n = 1, 2, . . . số an = r1n là số nguyên. Chứng minh rằng khi n là số chẵn, thì an là số chính phương. Khi n là số lẻ thì an là 2 lần số chính phương. Hình 2.2 Giải. Ký hiệu M, M1 , M2 , . . . là tâm của các đường tròn H, k1 , k2 , . . .. Lấy x và y là hai bán kính của đường tròn k n và k n+1 (hình 2.2), còn Mn0 và Mn0 +1 là những điểm tiếp xúc của k n và k n+1 với AB. Khi đó Mn0 Mn02+1 = ( x + y)2 + ( x − y)2 , MMn02 = MS · MT = 1 − 2x, MMn02+1 = 1 − 2y, Mn0 Mn0 +1 = MMn0 +1 − MMn0 . Từ những đẳng thức trên ta nhận được p √ p 1 − 2y − 1 − 2x = 4xy. Bình phương hai vế đẳng thức ta tìm được 6xy = x2 + y2 + 4x2 y2 + 4x2 y + 4xy2 . Đặt a = 1x , b = y1 . Nhân hai vế đẳng thức trên với a2 b2 ta nhận được 6ab = a2 + b2 + 4 + 4( a + b), 16