Luận văn Về lục giác lồi rỗng

Nội dung tài liệu: Luận văn Về lục giác lồi rỗng

1. ĐẠI HÅC QUÈC GIA HÀ NËI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIÊN ------------------ NGUYỄN GIANG THÀNH VỀ LỤC GIÁC LÇI RỖNG LUẬN VĂN THẠC SỸ TOÁN HÅC Chuy¶n ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP M¢ sè: 60 46 01 13 Người hướng d¨n khoa học PGS. TS. TẠ DUY PHƯỢNG HÀ NËI- 2013
2. Mục lục Mở đầu 3 1 TÊNG QUAN VỀ BÀI TOÁN ERDOS¨ VỀ ĐA GIÁC LÇI RỖNG 5 1.1 Bài to¡n 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Bài to¡n 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Bài to¡n 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Bài to¡n 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.4 Bài to¡n 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.5 Bài to¡n 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Bài to¡n 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Bài to¡n 3 (Bài to¡n v· tồn t¤i đa gi¡c chùa k điểm trong ) . . . . . 19 1.4 Bài to¡n 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 CHỨNG MINH ĐÁNH GIÁ E(6) ≤ ES(9) VÀ HỆ QUẢ 23 2.1 Định lý E(6) ≤ ES(9) ........................... 23 2.2 Lược đồ chùng minh . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.1 K½ hi»u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 C¡c định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 C¡c trường hñp đơn gi£n . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 C¡c trường hñp (3; ≥ 0) và (≥ 6; 3) .................... 27 2.4.1 C¡c trường hñp (3; ≥ 0) và (8,3) . . . . . . . . . . . . . . . . . 27 2.4.2 C¡c trường hñp (6,3) và (7,3) . . . . . . . . . . . . . . . . . . 29 2.5 C¡c trường hñp (4; ≥ 0) và (≥ 7; 4) .................... 34 2.5.1 Bước 1a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.2 Bước 1b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.3 Bước 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.4 Bước 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.5 Têng k¸t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 C¡c trường hñp (5; 0) và (≥ 7; 5; 0) .................... 40 2.6.1 C¡c trường hñp (5; 0) và (8; 5; 0) . . . . . . . . . . . . . . . . . 40 2.6.2 Trường hñp (7; 5; 0) ........................ 40 2.7 C¡c trường hñp ri¶ng . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.7.1 Trường hñp (5,1) . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.7.2 Trường hñp (6,1) . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.7.3 C¡c trường hñp (6,2) và (7,1) . . . . . . . . . . . . . . . . . . 43 2.8 C¡c trường hñp (5; ≥ 2) .......................... 43 1
3. 2.8.1 Mët quan s¡t cơ b£n . . . . . . . . . . . . . . . . . . . . . . . 43 2.8.2 C¡c trường hñp (5; ≥ 2) ...................... 46 2.9 C¡c trường hñp (6; ≥ 4) .......................... 48 2.9.1 TWX \ TXY 6= ? .......................... 49 2.9.2 TWX \ TXY = ? .......................... 51 2.10 C¡c trường hñp (≥ 7; ≥ 5; ≥ 1) ...................... 52 2.10.1 Quy t­c 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.10.2 Quy t­c 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.10.3 Ứng dụng cõa Quy t­c 1 và 2 . . . . . . . . . . . . . . . . . . 54 2.10.4 Quy t­c 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.10.5 Ứng dụng c¡c Quy t­c 1-3 . . . . . . . . . . . . . . . . . . . 58 2.10.6 Trường hñp (1; 1; 1; 1; 1; 1; 1) . . . . . . . . . . . . . . . . . . 59 2.10.7 Trường hñp (1; 1; 1; 1; 1; 1; 1; 0) . . . . . . . . . . . . . . . . . 59 2.10.8 Trường hñp (1; 1; 1; 1; 1; 1; 1; 1) . . . . . . . . . . . . . . . . . . 61 K¸t luªn ..................................... 65 Tài li»u tham kh£o .............................. 66 2
4. Mở đầu N«m 1935, Erdos} và Szekeres đã đưa ra gi£ thuy¸t sau đây (gi£ thuy¸t Erdos-} Szekeres): Mọi tªp không ½t hơn 2n−2 + 1 điểm tr¶n mặt ph¯ng ở vị tr½ têng qu¡t (không có ba điểm nào th¯ng hàng) đều chùa n điểm là đỉnh cõa mët đa gi¡c lồi. Gi£ thuy¸t Erdos-Szekeres} có ý nghĩa tri¸t học s¥u s­c: Tø mët tªp hñp hén độn, không có trªt tự, đủ lớn (tªp c¡c điểm b§t k¼ tr¶n mặt ph¯ng), ta có thº t¼m được mët tªp con có c§u trúc đẹp (đa gi¡c lồi). K½ hi»u ES(n) là sè điểm ở vị tr½ têng qu¡t nhỏ nh§t mà tø đó ta có thº chọn ra n điểm là đỉnh cõa n-gi¡c lồi. Khi §y, gi£ thuy¸t Erdos-Szekeres} nói r¬ng ES (n) = 2n−2 + 1: B§t ch§p sự cè g­ng cõa hàng tr«m nhà to¡n học đã vi¸t hàng tr«m bài b¡o, gi£ thuy¸t Erdos-Szekeres} mới ch¿ được chùng minh cho c¡c trường hñp n = 3; 4; 5; 6: Trường hñp n = 6 mới được chùng minh g¦n đây (2006) bởi Szekeres và Peters nhờ m¡y t½nh. Tr¶n con đường chùng minh gi£ thuy¸t Erdos-Szekeres,} nhi·u phương ph¡p và bài to¡n mới đã xu§t hi»n. N«m 1978 [xem 5], Erdos} đã ph¡t biºu mët bài to¡n mới, đó là Bài to¡n Erdos} v· đa gi¡c lồi réng: Cho n là mët sè tự nhi¶n b§t k¼. Tồn t¤i hay không sè nguy¶n dương nhỏ nh§t E(n) sao cho tø mọi tªp chùa tèi thiºu E(n) điểm ở vị tr½ têng qu¡t tr¶n mặt ph¯ng, đều có thº chọn ra được n điểm là đỉnh cõa mët đa gi¡c lồi réng (đa gi¡c không chùa điểm nào cõa tªp đã cho b¶n trong nó). Bài to¡n này đã thu hút nhi·u nhà nghi¶n cùu h¼nh học tê hñp tr¶n th¸ giới. N«m 1978, Harborth đã chùng minh E(5) = 10. N«m 1983, với mọi n, Horton đã x¥y dựng tªp (sau này được gọi là tªp Horton), mà tø đó không thº l§y ra được đa gi¡c lồi réng b£y đỉnh. Như vªy, ch¿ cán ph£i nghi¶n cùu với trường hñp n = 6. N«m 2003, Overmars đã chùng minh, n¸u E(6) tồn t¤i th¼ E(6) ≥ 30. N«m 2008, Gerken đã chùng minh E(6) ≤ ES(9) và tø đó suy ra ES(6) tồn t¤i và ta có đánh gi¡ 30 ≤ E(6) ≤ 1717. Nhi·u người tin r¬ng, E(6) = 30. Tuy nhi¶n, gi£ thuy¸t này cho đến nay v¨n chưa được chùng minh. Luªn v«n V· lục gi¡c lồi réng có mục đ½ch tr¼nh bày têng quan v· bài to¡n Erdos-} 3
5. Szekeres và bài to¡n Erdos} đồng thời tr¼nh bày chùng minh chi ti¸t bài b¡o cõa Gerken v· đánh gi¡ E(6) ≤ ES(9). Luªn v«n gồm hai Chương: Chương 1 tr¼nh bày têng quan v· gi£ thuy¸t Erdos-Szekeres.} Chương 2 tr¼nh bày c¡ch chùng minh E(6) ≤ ES(9) cõa Gerken (n«m 2008). Luªn v«n được hoàn thành t¤i trường Đại học Khoa học Tự nhi¶n, Đại học Quèc gia Hà Nëi dưới sự hướng d¨n cõa PGS. TS. T¤ Duy Phượng- Vi»n To¡n học. Tôi xin bày tỏ láng bi¸t ơn s¥u s­c tới Th¦y hướng d¨n. Tôi xin được c£m ơn Khoa sau đại học, c¡c Thày Cô trường Đại học Khoa học Tự nhi¶n, Đại học Quèc gia Hà Nëi và Vi»n To¡n học đã nhi»t t¼nh truy·n thụ ki¸n thùc và t¤o điều ki»n giúp đỡ tôi hoàn thành khóa Cao học. Và cuèi cùng, xin c£m ơn Gia đình đã động vi¶n và kh½ch l» tôi r§t nhi·u trong thời gian nghi¶n cùu và học tªp. 4
6. Chương 1 TÊNG QUAN VỀ BÀI TOÁN ERDOS¨ VỀ ĐA GIÁC LÇI RỖNG 1.1 Bài to¡n 1 Với méi sè tự nhi¶n n ≥ 3 , h¢y x¡c định sè nguy¶n dương nhỏ nh§t ES(n) sao cho mọi tªp t¤o thành tø tèi thiºu ES(n) điểm tr¶n mặt ph¯ng ở vị tr½ têng qu¡t ph£i chùa n điểm là đỉnh cõa mët đa gi¡c lồi. Bài to¡n 1 được ph¡t biºu vào n«m 1935 và sau này được gọi là Bài to¡n Erd¨os- Szekeres. Erd¨osđã gọi bài to¡n này là bài to¡n có k¸t h¤nh phúc (happy end problem hay happy ending problem), v¼ không l¥u sau khi bài b¡o được in ra (1935), Gy¨orgy Szekeres và Esther Klein đã tê chùc đám cưới (1937) và sèng h¤nh phúc b¶n nhau 60 n«m. Bài to¡n 1 đã được t¡ch ra thành hai bài to¡n: 1.1.1 Bài to¡n 1a Tồn t¤i hay không tồn t¤i sè ES(n)? 1.1.2 Bài to¡n 1b N¸u sè ES(n) tồn t¤i th¼ x¡c định ES(n) như mët hàm cõa n. Sự tồn t¤i sè ES(n) có thº được chùng minh b¬ng hai c¡ch. C¡ch thù nh§t do Szekeres chùng minh không l¥u sau khi E. Klein ph¡t biºu bài to¡n, dựa tr¶n định l½ Ramsey (mà Æng đã tự t¼m l¤i do không bi¸t định l½ này). Tø đó ta có b§t đẳng thùc ES(n) ≤ R4(n; 5) , trong đó R4(n; 5) là sè Ramsey. Tuy nhi¶n, đánh gi¡ này là qu¡ lớn so với thực t¸. Th½ dụ, với n = 5 th¼ ES(5) ≤ 210000 qu¡ xa so với ES(5) = 9. C¡ch thù hai do Erd¨oschùng minh dựa tr¶n mët sè quan s¡t h¼nh học và k¸t 2n−4 qu£ ta đưñc mët đánh gi¡ tèt hơn ES(n) ≤ Cn−2 + 1. Như vªy, bài to¡n 1a đã được tr£ lời kh¯ng định. 5
7. Rã ràng ba điểm không th¯ng hàng là đủ để t¤o ra mët tam gi¡c n¶n ES(3) = 3. Dưới đây ta x²t mët sè trường hñp cụ thº cõa bài to¡n với n = 4; 5; 6. 1.1.3 Bài to¡n 1.1 (E. Klein) Tø n«m điểm b§t kỳ tr¶n mặt ph¯ng ở vị tr½ têng qu¡t bao giờ cũng chọn được bèn điểm là đỉnh cõa mët tù gi¡c lồi. Đây cũng k¸t qu£ cho bài to¡n 1 trong trường hñp n = 4. Bài to¡n đã được E.Klein chùng minh vào n«m 1932. Chùng minh Trước ti¶n ta nhªn th§y, tồn t¤i bèn điểm không t¤o thành mët tù gi¡c lồi (H¼nh 1.1). H¼nh 1.1 Vªy sè điºm mà tø đó có thº t¤o thành tù gi¡c lồi ph£i không ½t hơn 5. X²t bao lồi cõa n«m điểm (tªp lồi nhỏ nh§t chùa n«m điểm đã cho) ở vị tr½ têng qu¡t. Ch¿ có ba kh£ n«ng kh¡c nhau sau đây. • Kh£ n«ng 1 (H¼nh 1.2): H¼nh 1.2 Bao lồi cõa n«m điểm là mët ngũ gi¡c ABCDE. Khi §y mọi bë bèn điºm tø n«m điểm §y đều t¤o thành tù gi¡c lồi (và điểm cán l¤i n¬m ngoài tù gi¡c lồi đó). Trong 6
8. 4 trường hñp này ta có t§t c£ C5 = 5 tù gi¡c lồi. Đó ch½nh là c¡c tù gi¡c ABCD, ABCE, ABDE, ACDE, BCDE. T§t c£ c¡c tù gi¡c này đều không chùa điểm cán l¤i (điểm thù n«m n¬m b¶n ngoài tù gi¡c). Ta gọi c¡c tù gi¡c lồi này là tù gi¡c lồi réng. Ngoài ra, ta có t§t c£ 10 tam gi¡c được t¤o thành tø n«m điºm A, B, C, D, E (ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE). Và t§t c£ c¡c tam gi¡c này đều là c¡c tam gi¡c réng. • Kh£ n«ng 2 (H¼nh 1.3): H¼nh 1.3 Bao lồi là mët tù gi¡c chùa mët điểm cán l¤i ở b¶n trong. Trong trường hñp này ta có mët tù gi¡c lồi (k½ hi»u là ABCD) chùa mët điểm E ở b¶n trong. Tù gi¡c ABCD (ch¿ chùa đúng mët điểm E ở b¶n trong) được gọi là tù gi¡c g¦n réng. V¼ không có ba điºm nào th¯ng hàng n¶n E ph£i n¬m v· cùng ph½a với B (hoặc với D) cõa đường th¯ng AC. Do đó ta có tù gi¡c AECD (hoặc ABCE) là tù gi¡c lồi réng, cán tù gi¡c ABCE (hoặc tương ùng AECD) là tù gi¡c lãm. Tương tự, điểm E ph£i n¬m cùng ph½a với A (hoặc với C) cõa đường ch²o BD. Khi §y tù gi¡c BEDC (hoặc tù gi¡c ABED) là tù gi¡c lồi réng và tù gi¡c ABED (hoặc tù gi¡c BCDE) là tù gi¡c lãm. Như vªy, trong Trường hñp 2 ta có hai tù gi¡c lồi réng, mët tù gi¡c lồi g¦n réng và hai tù gi¡c lãm. Ngoài ra, trong trường hñp này, ta có t§t c£ 10 tam gi¡c được t¤o thành tø n«m điểm A, B, C, D, E. Đó là c¡c tam gi¡c: ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. Trong đó t§t c£ 6 tam gi¡c có đỉnh E đều là tam gi¡c réng (không chùa hai điºm cán l¤i b¶n trong). V¼ khi k´ đường ch²o AC (hoặc BD) cõa tù gi¡c lồi ABCD th¼ do c¡c điểm không th¯ng hàng n¶n E ph£i n¬m trong mët trong hai tam gi¡c ABC hoặc ACD (ABD hoặc BCD). Như vªy ta có hai tam gi¡c g¦n réng (chùa điểm E) và th¶m hai tam gi¡c réng núa. • Kh£ n«ng 3 (H¼nh 1.4): 7
9. H¼nh 1.4 Bao lồi chùa ba điểm t¤o thành tam gi¡c, th½ dụ, ABC. Hai điểm cán l¤i E và D n¬m b¶n trong tam gi¡c. Do không có ba điểm nào th¯ng hàng (c¡c điºm ở vị tr½ têng qu¡t) n¶n hai điểm E và D x¡c định mët đường th¯ng chia mặt ph¯ng tam gi¡c ABC thành hai ph¦n sao cho có hai đỉnh cõa tam gi¡c ABC, th½ dụ, A và B, n¬m tr¶n cùng mët nûa mặt ph¯ng mở. Hai điºm E và D cùng với A và B t¤o thành mët tù gi¡c lồi réng ABDE. Tù gi¡c này là tù gi¡c lồi duy nh§t. Bèn tù gi¡c ABDC, ABEC, BDCE, ADCE cán l¤i là c¡c tù gi¡c lãm. Ngoài ra, ta có t§t c£ 10 tam gi¡c được t¤o thành tø n«m điểm A, B, C, D, E. Đó là c¡c tam gi¡c: ABC (chùa hai điºm b¶n trong), ACD và BEC chùa mët điểm b¶n trong (tam gi¡c g¦n réng). B£y tam gi¡c cán l¤i ABD, ABE, ACE, ADE, BCD, BDE, CDE là c¡c tam gi¡c réng. 1.1.4 Bài to¡n 1.2 Với ch½n điểm cho trước ở vị tr½ têng qu¡t (không có ba điểm nào th¯ng hàng) bao giờ ta cũng t¼m đưñc n«m điểm t¤o thành mët ngũ gi¡c lồi. Theo Erdos} và Szekeres, công thùc ES(5) = 9 đã được Endre Makai chùng minh. H¼nh 1.5 Tuy nhi¶n không có bài vi¸t nào cõa E. Makai tr¼nh bày chùng minh đó, mà ch¿ có ph£n v½ dụ cõa E. Makai (H¼nh 1.5, xem [6]) ch¿ ra r¬ng tồn t¤i t¡m điểm mà 8
10. không có n«m điểm nào trong sè đó t¤o thành ngũ gi¡c lồi, tùc là ES(5) ≥ 9 (xem [6]). Bài to¡n 1.2 đã được Hoàng Chúng giới thi»u với b¤n đọc Vi»t Nam trong To¡n học và Tuêi tr´ sè 4, th¡ng 2 n«m 1967. Ngay sau đó công thùc ES(5) = 9 đã được Đoàn Húu Dũng chùng minh trong To¡n học và Tuêi tr´ sè 6 th¡ng 6, 1967. Hoàn toàn độc lªp (nhưng cùng phương ph¡p) với Đoàn Húu Dũng, công thùc này cũng được chùng minh bởi Bonnice n«m 1974. Dưới đây chúng tôi tr¼nh bày chùng minh chi ti¸t công thùc ES(5) = 9, k¸t hñp c£ phương ph¡p h¼nh học, (xem [1]) cõa Đoàn Húu Dũng (sû dụng c¡c đa gi¡c lồi bao nhau) và ngôn ngú c§u h¼nh cõa Bonnice (xem [3]). Chùng minh (Đoàn Húu Dũng, 1967; Bonnice, 1974) L§y bao lồi cõa 9 điểm b§t kỳ. Gọi méi trường hñp (kh£ n«ng) có thº x£y ra là mët c§u h¼nh. Để ph¥n lo¤i c¡c c§u h¼nh, ta x²t c¡c đa gi¡c lồi bao nhau, tùc là đầu ti¶n l§y bao lồi cõa 9 điểm, bao lồi ch¿ có thº là đa gi¡c 9; 8; 7; 6; 5; 4; 3 đỉnh. C¡c điểm cán l¤i b¶n trong bao lồi tương ùng s³ là 0; 1; 2; 3; 4; 5; 6. Khi sè điểm cán l¤i b¶n trong bao lồi lớn hơn 3, ta l¤i l§y bao lồi cõa c¡c điểm này để được c¡c đa gi¡c lồi. Ch¿ có duy nh§t mët trường hñp ba tam gi¡c bao nhau. C¡c trường hñp cán l¤i ch¿ có thº là hai hoặc mët đa gi¡c bao nhau (có thº chùa mët hoặc hai điểm trong). Ta được t§t c£ 12 c§u h¼nh kh¡c nhau sau đây: Trường hñp 1 (H¼nh 1.6a) C§u h¼nh (9;0): Bao lồi là đa gi¡c lồi 9 đỉnh. Mọi tªp n«m đỉnh đều t¤o thành ngũ gi¡c lồi (thªm ch½ lồi réng). Trường hñp 2 (H¼nh 1.6b) C§u h¼nh (8;1): Bao lồi là đa gi¡c lồi 8 đỉnh, mët điểm cán l¤i n¬m trong đa gi¡c. Do không có ba điểm nào th¯ng hàng n¶n n«m đỉnh b§t k¼ cõa bao lồi t¤o thành ngũ gi¡c lồi (có thº réng hoặc chùa mët điểm trong). Trường hñp 3 (H¼nh 1.6c) C§u h¼nh (7;2): Bao lồi là đa gi¡c lồi 7 đỉnh, hai điểm cán l¤i n¬m trong đa gi¡c. Do không có ba điểm nào th¯ng hàng n¶n n«m đỉnh b§t k¼ cõa bao lồi t¤o thành ngũ gi¡c lồi (có thº réng, chùa mët hoặc hai điểm trong). 9