shoptinhyeu_boydangyeu1088
New Member
Download Luận văn Các bài toán hình học tổ hợp
Mục lục
Mụcl ục trang
Lời nói đầu i
Mụcl ục ii
Chương I: Nguyên lí cựchạn 1
Chương II:Sửdụng nguyên lí Dirichlet . 9
Chương III:Sửdụng tínhl ồi củatậphợp . 19
§1 Các bài toánsửdụng định lí Kelli . 19
§2 Phương phápsửdụng phépl ấy baol ồi . 27
Chương IV: Vài phương pháp khác . 32
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
đó Pi Pj Qj Qi là hình chữ nhật có bốn đỉnh
cùng màu đỏ.
2. Nếu tồn tại hai trong số bốn điểm R1, R2, R3, R4 màu đỏ (giả sử Ri , Rj).
Khi đó Pi Pj Rj Ri là hình chữ nhật có bốn đỉnh cùng màu đỏ.
3. Bốn điểm Q1, Q2, Q3, Q4 và bốn điểm R1, R2, R3, R4 trong đó tối đa chỉ
có một điểm đỏ. Khi đó rõ ràng theo nguyên lí Dirichlet tồn tại i , j mà Qi , Qj,
Ri , Rj cùng xanh.
Vậy Qi Qj Rj Ri là hình chữ nhật có bốn đỉnh cùng xanh. □
Ví dụ 2.8: 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: Kí hiệu M là mặt có số cạnh lớn nhất của khối đa diện. Giả sử mặt
M có k cạnh. Khi đó vì có k mặt có cạnh chung với M, nên đa diện có ít nhất
k + 1 mặt. Vì M là mặt có số cạnh lớn nhất bằng k , nên mọi mặt của đa diện
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 18 -
có số cạnh nhận một trong các giá trị { }3,4,..., k . Đa diện có ít nhất k + 1 mặt
số cạnh của nó nhận một trong k – 2 giá trị. 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. □
Ví dụ 2.9: Cho 1000 điểm M1 , M2 ,…, M1000 trên mặt phẳng. Vẽ một đường
tròn bán kính 1 tuỳ ý. Chứng minh rằng tồn tại điểm S trên đường tròn sao
cho: 1 2 100... 1000SM SM SM+ + + ³ .
Giải: Xét đường kính S1S2 tuỳ ý của đường tròn,
ở đây S1 và S2 là hai đầu của đường kính.
Vì S1S2 = 2, nên ta có:
1 1 2 1 1 2
1 2 2 2
1 1000 2 1000
2
2
...
2
S M S M S S
S M S M
S M S M
+ ³ =ì
ï + ³ï
í
ï
ï + ³î
Cộng từng vế 1000 bất đẳng thức trên ta có:
( ) ( )1 1 1 2 1 1000 2 1 2 2 2 1000... ... 2000S M S M S M S M S M S M+ + + + + + + ³ (1)
Từ (1) và theo nguyên lí Dirichlet suy ra trong hai của vế trái của (1), có ít
nhất một tổng lớn hơn hay bằng 1000.
Giả sử 1 1 1 2 1 1000... 1000S M S M S M+ + + ³ , khi đó lấy 1S S= . □
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 19 -
Chương III: SỬ DỤNG TÍNH LỒI CỦA TẬP HỢP
Tập hợp lồi có một đặc trưng cơ bản là khi nó chứa hai điểm, thì nó sẽ
chứa toàn bộ đoạn thẳng chứa hai điểm ấy. Tính ưu việt này được tận dụng
triệt để trong việc giải các bài toán hình học nói chung và các bài toán hình
học tổ hợp nói riêng. Trước hết xin nhắc lại một số kiến thức cơ bản về tập
hợp lồi sẽ dùng đến trong chương này.
Định nghĩa tập hợp lồi: Giả sử Ω là một tập hợp cho trước ( trên đường
thẳng, mặt phẳng hay không gian).
Tập hợp Ω được gọi là tập hợp lồi với bất kì hai điểm A, B Î Ω, thì cả đoạn
thẳng AB (với hai đầu mút A và B) nằm trọn trong Ω.
Ví dụ:
Tính chất tập hợp lồi: Nếu A, B là hai tập hợp lồi, thì A Ç B cũng là tập hợp
lồi.
Bằng quy nạp có thể chứng minh được:
Nếu A1, A2,…,An thì A1 Ç A2 Ç …Ç An cũng là tập hợp lồi.
Chú ý: Hợp của hai hợp lồi A và B chưa chắc là tập hợp lồi.
H-3.2
A
B
Ω
H - 3.1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 20 -
§1: CÁC BÀI TOÁN SỬ DỤNG ĐỊNH LÍ KELLI
Định lí Kelli là một trong các định lí rất quan trọng của hình học tổ hợp.
Định lí này cho ta một điều kiện đủ hữu hiệu để nhận biết rằng khi nào một ho
các hình lồi có giao khác rỗng.
I. Định lí Kelli trong không gian hai chiều 2¡
Trong mặt phẳng cho n hình lồi (n ≥ 4). Biết rằng giao của ba hình lồi bất
kì trong chúng khác rỗng. Khi đó giao của n hình lồi cũng khác rỗng.
Chứng minh: Ta chứng minh bằng quy nạp theo số n các hình lồi.
1. Xét n = 4.
Gọi 1 2 3 4, , ,F F F F là bốn hình lồi có tính chất là giao của ba hình bất kì trong
chúng là khác rỗng. Vì 2 3 4F F FÇ Ç ¹ Æ nên tồn tại 1 2 3 4A F F FÎ Ç Ç .
Tương tự tồn tại 2 1 3 4 3 1 2 4 4 1 2 3 ; A ; AA F F F F F F F F FÎ Ç Ç Î Ç Ç Î Ç Ç .
Chỉ có hai khả năng sảy ra:
a) Nếu 4 điểm 1 2 3 4, , ,A A A A không hoàn toàn khác nhau. Khi đó không giảm
tính tổng quát ta đánh giá là 1 2A Aº .Từ đó suy ra:
1 1 2 3 4A F F F FÎ Ç Ç Ç . Nên 1 2 3 4F F F FÇ Ç Ç ¹ Æ .
Vậy kết luận của định lí Kelli đúng trong trường hợp khi n = 4.
b) 1 2 3 4, , ,A A A A là 4 điểm phân biệt, khi đó lại có
hai khả năng xảy ra:
b1) Bao lồi của 1 2 3 4, , ,A A A A chính là tứ giác lồi
1 2 3 4A A A A .
Giả sử O là giao của hai đường chéo 1 2 3 4,A A A A .
Do 1 2 3 4A F F FÎ Ç Ç nên 1 3 2 1 3 4; AA F F F FÎ Î Ç Ç nên 1 3A FÎ .
Vì 3F lồi mà 1 3 2 3, AA F FÎ Î nên [ ]1 2 3,A A FÎ .
Nói riêng 3O FÎ .
A4
A3 A1
A2
H-3.3
O
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 21 -
Lập luận hoàn toàn tương tự suy ra 1 2 4 , , O F O F O FÎ Î Î . Điều đó có
nghĩa là:
4
1
i
i
O F
=
ÎI do đó
4
1
j
i
F
=
¹ ÆI .
b2) Bao lồi của chúng là tam giác chứa điểm bên trong. Không giảm tổng
quát ta có thể đánh giá là ∆ 1 2 3A A A chứa 4A .
Vì 1 2 3, ,A A A đều thuộc 4F , mà 4F lồi nên toàn bộ miền trong tam giác 1 2 3A A A
thuộc 4F .
Mặt khác
4
4 1 2 3 4
1
i
i
A F F F A F
=
Î Ç Ç Þ ÎI .
Từ đó suy ra
4
1
i
i
F
=
¹ ÆI .
Vậy định lí Kelli đúng khi n = 4.
2. Giả sử kết luận của định lí Kelli đúng đến n ≥ 4.
3. Xét trường hợp khi có n + 1 hình lồi, tức là ta có n + 1 hình lồi
1 2 1, ,..., ,n nF F F F + với giả thiết bất kì 3 hình lồi nào trong chúng đều có giao nhau
khác rỗng.
Xét các hình sau:
'
1 1
'
2 2
'
1 1
'
1
...
n n
n n n
F F
F F
F F
F F F
- -
+
=
=
=
= Ç
Rõ ràng 'iF là lồi với mọi 1, 1i n= - (vì 'i iF F= ), còn 'nF cũng là lồi vì nó
là giao của hai hình lồi nF và 1nF + .
Xét ba hình lồi bất kì ' ' ', , i j kF F F trong n hình lồi
' ' '
1 2, ,..., nF F F .
A2
A1
H-3.4
A4
*
A3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 22 -
Nếu trong chúng không có 'nF thì theo giả thiết
' ' 'i j k i j kF F F F F FÇ Ç = Ç Ç ¹ Æ .
Nếu trong chúng có ' 1n n nF F F += Ç . Khi đó có thể đánh giá là ' 'k nF F=
Từ đó ' ' ' 1i j k i j n nF F F F F F F +Ç Ç = Ç Ç Ç .
Vì giao của ba hình lồi trong các hình lồì 1 1, , ,j n nF F F F + là khác rỗng (giả
thiết), nên theo trường hợp n = 4 ta có 1i j n nF F F F +Ç Ç Ç ¹ Æ . Vậy với n hình
lồi ' ' '1 2, , ..., nF F F thoả mãn điều kiện giao của ba hình lồi bất kì trong chúng khác
rỗng, nên theo giả thiết quy nạp suy ra:
' ' '1 2 ... nF F FÇ Ç Ç ¹ Æ .
Điều đó có nghĩa là 1 2 1... n nF F F F +Ç Ç Ç Ç ¹ Æ .
Định lí Kelli đúng trong trường hợp có n + 1 hình lồi. Theo nguyên lí quy nạp
suy ra định lí Kelli đúng với mọi n ≥ 4. Định lí Kelli được chứng minh trong
2¡ .
Chú ý: Ta thấy rằng điều kiện n ≥ 4 là cần thiết.
Thật vậy, hãy xét mệnh đề tương tự với n = 3.
“Cho một họ n hình lồi (n ≥ 3) trong mặt phẳng.
Biết rằng giao của hai hình lồi bất kì trong
chúng khác rỗng. Khi đó giao của n hình lồi cũng khác rỗng”.
Rõ ràng mệnh đề này không chắc đúng.
Thật vậy, xét với n = 3. Xét ba hình lồi: đoạn thẳng AB, đoạn thẳng BC, đoạn
thẳng CA.
Rõ ràng giao của hai hình lồi bất kì trong chúng khác rỗng.
Nhưng AB Ç AC Ç BC =Æ .
C
A
B
H-3.5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 23 -
II. Định lí Kelli trong không gian một chiều 1¡ .
Trên đường thẳng cho n hình lồi (n ≥ 3) trong mặt phẳng. Biết rằng giao
của hai hình lồi bất kì trong chúng khác rỗng. Khi đó giao của n hình lồi cũng
khác rỗng.
Chứng minh: Ta biết rằng ...
Download miễn phí Luận văn Các bài toán hình học tổ hợp
Mục lục
Mụcl ục trang
Lời nói đầu i
Mụcl ục ii
Chương I: Nguyên lí cựchạn 1
Chương II:Sửdụng nguyên lí Dirichlet . 9
Chương III:Sửdụng tínhl ồi củatậphợp . 19
§1 Các bài toánsửdụng định lí Kelli . 19
§2 Phương phápsửdụng phépl ấy baol ồi . 27
Chương IV: Vài phương pháp khác . 32
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Tóm tắt nội dung:
Khiđó Pi Pj Qj Qi là hình chữ nhật có bốn đỉnh
cùng màu đỏ.
2. Nếu tồn tại hai trong số bốn điểm R1, R2, R3, R4 màu đỏ (giả sử Ri , Rj).
Khi đó Pi Pj Rj Ri là hình chữ nhật có bốn đỉnh cùng màu đỏ.
3. Bốn điểm Q1, Q2, Q3, Q4 và bốn điểm R1, R2, R3, R4 trong đó tối đa chỉ
có một điểm đỏ. Khi đó rõ ràng theo nguyên lí Dirichlet tồn tại i , j mà Qi , Qj,
Ri , Rj cùng xanh.
Vậy Qi Qj Rj Ri là hình chữ nhật có bốn đỉnh cùng xanh. □
Ví dụ 2.8: 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: Kí hiệu M là mặt có số cạnh lớn nhất của khối đa diện. Giả sử mặt
M có k cạnh. Khi đó vì có k mặt có cạnh chung với M, nên đa diện có ít nhất
k + 1 mặt. Vì M là mặt có số cạnh lớn nhất bằng k , nên mọi mặt của đa diện
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 18 -
có số cạnh nhận một trong các giá trị { }3,4,..., k . Đa diện có ít nhất k + 1 mặt
số cạnh của nó nhận một trong k – 2 giá trị. 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. □
Ví dụ 2.9: Cho 1000 điểm M1 , M2 ,…, M1000 trên mặt phẳng. Vẽ một đường
tròn bán kính 1 tuỳ ý. Chứng minh rằng tồn tại điểm S trên đường tròn sao
cho: 1 2 100... 1000SM SM SM+ + + ³ .
Giải: Xét đường kính S1S2 tuỳ ý của đường tròn,
ở đây S1 và S2 là hai đầu của đường kính.
Vì S1S2 = 2, nên ta có:
1 1 2 1 1 2
1 2 2 2
1 1000 2 1000
2
2
...
2
S M S M S S
S M S M
S M S M
+ ³ =ì
ï + ³ï
í
ï
ï + ³î
Cộng từng vế 1000 bất đẳng thức trên ta có:
( ) ( )1 1 1 2 1 1000 2 1 2 2 2 1000... ... 2000S M S M S M S M S M S M+ + + + + + + ³ (1)
Từ (1) và theo nguyên lí Dirichlet suy ra trong hai của vế trái của (1), có ít
nhất một tổng lớn hơn hay bằng 1000.
Giả sử 1 1 1 2 1 1000... 1000S M S M S M+ + + ³ , khi đó lấy 1S S= . □
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 19 -
Chương III: SỬ DỤNG TÍNH LỒI CỦA TẬP HỢP
Tập hợp lồi có một đặc trưng cơ bản là khi nó chứa hai điểm, thì nó sẽ
chứa toàn bộ đoạn thẳng chứa hai điểm ấy. Tính ưu việt này được tận dụng
triệt để trong việc giải các bài toán hình học nói chung và các bài toán hình
học tổ hợp nói riêng. Trước hết xin nhắc lại một số kiến thức cơ bản về tập
hợp lồi sẽ dùng đến trong chương này.
Định nghĩa tập hợp lồi: Giả sử Ω là một tập hợp cho trước ( trên đường
thẳng, mặt phẳng hay không gian).
Tập hợp Ω được gọi là tập hợp lồi với bất kì hai điểm A, B Î Ω, thì cả đoạn
thẳng AB (với hai đầu mút A và B) nằm trọn trong Ω.
Ví dụ:
Tính chất tập hợp lồi: Nếu A, B là hai tập hợp lồi, thì A Ç B cũng là tập hợp
lồi.
Bằng quy nạp có thể chứng minh được:
Nếu A1, A2,…,An thì A1 Ç A2 Ç …Ç An cũng là tập hợp lồi.
Chú ý: Hợp của hai hợp lồi A và B chưa chắc là tập hợp lồi.
H-3.2
A
B
Ω
H - 3.1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 20 -
§1: CÁC BÀI TOÁN SỬ DỤNG ĐỊNH LÍ KELLI
Định lí Kelli là một trong các định lí rất quan trọng của hình học tổ hợp.
Định lí này cho ta một điều kiện đủ hữu hiệu để nhận biết rằng khi nào một ho
các hình lồi có giao khác rỗng.
I. Định lí Kelli trong không gian hai chiều 2¡
Trong mặt phẳng cho n hình lồi (n ≥ 4). Biết rằng giao của ba hình lồi bất
kì trong chúng khác rỗng. Khi đó giao của n hình lồi cũng khác rỗng.
Chứng minh: Ta chứng minh bằng quy nạp theo số n các hình lồi.
1. Xét n = 4.
Gọi 1 2 3 4, , ,F F F F là bốn hình lồi có tính chất là giao của ba hình bất kì trong
chúng là khác rỗng. Vì 2 3 4F F FÇ Ç ¹ Æ nên tồn tại 1 2 3 4A F F FÎ Ç Ç .
Tương tự tồn tại 2 1 3 4 3 1 2 4 4 1 2 3 ; A ; AA F F F F F F F F FÎ Ç Ç Î Ç Ç Î Ç Ç .
Chỉ có hai khả năng sảy ra:
a) Nếu 4 điểm 1 2 3 4, , ,A A A A không hoàn toàn khác nhau. Khi đó không giảm
tính tổng quát ta đánh giá là 1 2A Aº .Từ đó suy ra:
1 1 2 3 4A F F F FÎ Ç Ç Ç . Nên 1 2 3 4F F F FÇ Ç Ç ¹ Æ .
Vậy kết luận của định lí Kelli đúng trong trường hợp khi n = 4.
b) 1 2 3 4, , ,A A A A là 4 điểm phân biệt, khi đó lại có
hai khả năng xảy ra:
b1) Bao lồi của 1 2 3 4, , ,A A A A chính là tứ giác lồi
1 2 3 4A A A A .
Giả sử O là giao của hai đường chéo 1 2 3 4,A A A A .
Do 1 2 3 4A F F FÎ Ç Ç nên 1 3 2 1 3 4; AA F F F FÎ Î Ç Ç nên 1 3A FÎ .
Vì 3F lồi mà 1 3 2 3, AA F FÎ Î nên [ ]1 2 3,A A FÎ .
Nói riêng 3O FÎ .
A4
A3 A1
A2
H-3.3
O
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 21 -
Lập luận hoàn toàn tương tự suy ra 1 2 4 , , O F O F O FÎ Î Î . Điều đó có
nghĩa là:
4
1
i
i
O F
=
ÎI do đó
4
1
j
i
F
=
¹ ÆI .
b2) Bao lồi của chúng là tam giác chứa điểm bên trong. Không giảm tổng
quát ta có thể đánh giá là ∆ 1 2 3A A A chứa 4A .
Vì 1 2 3, ,A A A đều thuộc 4F , mà 4F lồi nên toàn bộ miền trong tam giác 1 2 3A A A
thuộc 4F .
Mặt khác
4
4 1 2 3 4
1
i
i
A F F F A F
=
Î Ç Ç Þ ÎI .
Từ đó suy ra
4
1
i
i
F
=
¹ ÆI .
Vậy định lí Kelli đúng khi n = 4.
2. Giả sử kết luận của định lí Kelli đúng đến n ≥ 4.
3. Xét trường hợp khi có n + 1 hình lồi, tức là ta có n + 1 hình lồi
1 2 1, ,..., ,n nF F F F + với giả thiết bất kì 3 hình lồi nào trong chúng đều có giao nhau
khác rỗng.
Xét các hình sau:
'
1 1
'
2 2
'
1 1
'
1
...
n n
n n n
F F
F F
F F
F F F
- -
+
=
=
=
= Ç
Rõ ràng 'iF là lồi với mọi 1, 1i n= - (vì 'i iF F= ), còn 'nF cũng là lồi vì nó
là giao của hai hình lồi nF và 1nF + .
Xét ba hình lồi bất kì ' ' ', , i j kF F F trong n hình lồi
' ' '
1 2, ,..., nF F F .
A2
A1
H-3.4
A4
*
A3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 22 -
Nếu trong chúng không có 'nF thì theo giả thiết
' ' 'i j k i j kF F F F F FÇ Ç = Ç Ç ¹ Æ .
Nếu trong chúng có ' 1n n nF F F += Ç . Khi đó có thể đánh giá là ' 'k nF F=
Từ đó ' ' ' 1i j k i j n nF F F F F F F +Ç Ç = Ç Ç Ç .
Vì giao của ba hình lồi trong các hình lồì 1 1, , ,j n nF F F F + là khác rỗng (giả
thiết), nên theo trường hợp n = 4 ta có 1i j n nF F F F +Ç Ç Ç ¹ Æ . Vậy với n hình
lồi ' ' '1 2, , ..., nF F F thoả mãn điều kiện giao của ba hình lồi bất kì trong chúng khác
rỗng, nên theo giả thiết quy nạp suy ra:
' ' '1 2 ... nF F FÇ Ç Ç ¹ Æ .
Điều đó có nghĩa là 1 2 1... n nF F F F +Ç Ç Ç Ç ¹ Æ .
Định lí Kelli đúng trong trường hợp có n + 1 hình lồi. Theo nguyên lí quy nạp
suy ra định lí Kelli đúng với mọi n ≥ 4. Định lí Kelli được chứng minh trong
2¡ .
Chú ý: Ta thấy rằng điều kiện n ≥ 4 là cần thiết.
Thật vậy, hãy xét mệnh đề tương tự với n = 3.
“Cho một họ n hình lồi (n ≥ 3) trong mặt phẳng.
Biết rằng giao của hai hình lồi bất kì trong
chúng khác rỗng. Khi đó giao của n hình lồi cũng khác rỗng”.
Rõ ràng mệnh đề này không chắc đúng.
Thật vậy, xét với n = 3. Xét ba hình lồi: đoạn thẳng AB, đoạn thẳng BC, đoạn
thẳng CA.
Rõ ràng giao của hai hình lồi bất kì trong chúng khác rỗng.
Nhưng AB Ç AC Ç BC =Æ .
C
A
B
H-3.5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
- 23 -
II. Định lí Kelli trong không gian một chiều 1¡ .
Trên đường thẳng cho n hình lồi (n ≥ 3) trong mặt phẳng. Biết rằng giao
của hai hình lồi bất kì trong chúng khác rỗng. Khi đó giao của n hình lồi cũng
khác rỗng.
Chứng minh: Ta biết rằng ...