ĐẠ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 11 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 11 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
- Xem thêm -