NGuyên lý chuồng và thỏ

Chia sẻ: Nguyễn Đăng Khoa | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

76
lượt xem 8
download

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

Tài liệu tham khảo về nguyên lý chuồng và thỏ...

Chủ đề:

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

Lưu

Nội dung Text: NGuyên lý chuồng và thỏ

www.laisac.page.tl N U Ê L C U N V T Ỏ NG Y N LÝ CH Ồ G VÀ TH GUYÊ HUỒN HỎ TS. Trần Nam Dũng Nguyên lý chu ng và th (hay còn ư c g i là nguyên lý Dirichlet) kh ng nh m t s ki n “hi n nhiên” r ng n+1 con th không th ư c x p vào n chu ng sao cho m i con u riêng m t chu ng. M t cách t ng quát hơn, nguyên lý chu ng và th kh ng th nh r ng: N u m t t p h p g m nhi u hơn kn i tư ng ư c chia thành n nhóm, thì có m t nhóm nào ó có nhi u hơn k i tư ng. Chân lý này r t d ki m tra: n u nhóm nào cũng có nhi u nh t k i tư ng thì t ng c ng ch có nhi u nh t kn i tư ng ư c chia ra. ây là m t trong nh ng nguyên lý không xây d ng (non-constructive) lâu i nh t: nó ch nói n s t n t i c a m t chu ng trong ó có nhi u hơn k v t mà không nói gì n cách tìm ra chu ng này. Ngày nay chúng ta ã có nh ng t ng quát hóa r t m nh c a nguyên lý này (các nh lý ki u Ramsey, phương pháp xác su t…). M c dù nguyên lý chu ng và th ư c phát bi u r t ơn gi n, nó có hàng lo t các ng d ng không t m thư ng. Cái khó c a vi c ng d ng nguyên lý này là xác nh ư c xem th là gì và chu ng là gì. Chúng ta s minh h a i u này b ng m t s ví d . 1. M t s ví d m u kh i ng, chúng ta s b t u b ng nh ng ng d ng ơn gi n nh t. B c c a m t nh trong th G là s d(x) các c nh c a G k v i x. M nh 1. Trong m i th t n t i hai nh có cùng b c. th G có n nh. Ta t o ra n cái chu ng ư c ánh s t 0 Ch ng minh. Gi s ta có n n-1 và x p nh x vào chu ng th k khi và ch khi d(x) = k. N u như trong m t chu ng nào ó có nhi u hơn 1 nh thì ta có pcm. Vì th ta có th gi s r ng không có chu ng nào ch a hơn 1 nh. Có t t c n nh ư c chia vào n cái chu ng, nhưng v y m i m t chu ng có úng 1 nh. G i x và y là các nh n m trong các chu ng ánh s 0 và n- 1 tương ng. nh x có b c 0 vì v y nó không ư c n i v i các nh khác, trong ó có y. Nhưng y có b c n-1 nên nó l i ư c n i v i t t c các nh, trong ó có x, mâu thu n. c l p (independent number) α(G) là s l n nh t N u G là m t th h u h n, ch s các nh ôi m t không k nhau c a G. S c s (chromatic number) χ(G) c a G là s nh tô các màu c a G sao cho không có hai nh k nhau ư c tô nh t các màu c n dùng cùng màu.
nh ta có n ≤ α(G).χ(G). M nh 2. Trong m i th G v i n Ch ng minh. Ta chia các nh c a G thành χ(G) nhóm (các t p h p các nh có cùng màu). Theo nguyên lý chu ng và th , m t trong các nhóm ó có ch a ít nh t n/χ(G) nh, và các nh này ôi m t không k nhau. Như v y α(G) ≥ n/χ(G) và ó chính là i u c n ch ng minh. nh b t kỳ c a nó có m t ư ng i. Mt th là liên thông n u gi a hai M nh 3. Cho G là m t th n nh. N u m i nh c a G có b c ít nh t là (n-1)/2 thì G liên thông. Ch ng minh. Ta xét hai nh x, y b t kỳ. N u hai nh này không k nhau thì có ít nh t n- 1 nh n i chúng v i các nh còn l i, vì c x và y u có b c ít nh t là (n-1)/2. Vì ch còn n-2 nh khác, nguyên lý chu ng và th suy ra r ng ph i có m t trong các nh ó n i v i c x và y. Ta ã ch ng minh ư c r ng m i c p nh thì ho c k nhau, ho c có nh k chung, và như v y G liên thông. Ghi chú. M t k t qu là t t nh t n u như k t lu n không còn úng khi ta làm y u i m t i u ki n. Ví d , trong k t qu trên: gi s n là ch n và G là h p c a hai th y v i n/2 nh thì b c c a m i nh b ng (n-2)/2 nhưng th không liên thông. Bài t p 1. Gi s 5 i m ư c ch n trong hình vuông c nh 1. Ch ng minh r ng t n t i ít nh t 1 c p i m cách nhau không quá 1/2. Bài t p 2. Các viên á c a 8 màu khác nhau ư c x p vào 6 cái h p. Có 20 viên á cho m i màu. Ch ng minh r ng tìm ư c m t h p ch a hai c p có cùng màu khác nhau. Bài t p 3. Ch ng minh r ng m t t p h p b t kỳ g m n+1 ph n t ư c ch n t {1, 2,…,2n} u ch a m t c p ph n t có t ng b ng 2n+1. Hãy ch ng minh k t qu này là t t nh t. Bài t p 4. Ch ng minh r ng m t t p h p b t kỳ g m n+1 s nguyên ư c ch n t {1, 2,…, 2n} ch a hai s mà s này chia h t cho s kia. 2. nh lý Erdos-Szekeres Cho A = (a1, a2,…, an) là dãy g m n s phân bi t. M t dãy con k ph n t c a A là dãy B g m k s h ng ph n t c a A xu t hi n theo úng th t mà chúng xu t hi n trong A. Có nghĩa là B = (ai1, ai2,…, aik) v i i1 < i2 < …< ik. Dãy con B ư c g i là tăng n u ai1 < ai2 ai2 >…> aik. dài l n nh t c a dãy con tăng và gi m c a A. Suy lu n tr c quan cho Ta quan tâm n dài này. N u như dãy con tăng dài nh t th y ph i có m t s cân i nh t nh gi a hai là ng n, ch ng h n có chi u dài là s, thì m i dãy con c a A có dài s+1 ph i ch a c p
ph n t gi m, như v y có r t nhi u c p ph n t gi m. Vì th ta trông i r ng dãy con gi m dài nh t s l n. M t trư ng h p c c biên x y ra khi s = 1. Khi ó c dãy s A là gi m. dài c a dãy con tăng dài nh t và dãy con Làm sao ta có th s hóa i u d c m r ng gi m dài nh t không th cùng nh ? K t qu n i ti ng c a Erdos và Szekeres (1935) cho u tiên c a t i ưu chúng ta câu tr l i cho câu h i này và ây là m t trong nh ng k t qu t h p. nh lý 4 (Erdos-Szekeres 1935). Cho A = (a1, a2,…, an) là dãy g m n s th c phân bi t. N u n ≥ rs + 1 thì ho c A có dãy con tăng dài s+1 ho c A có dãy con gi m dài r+1 (hay c hai). Ch ng minh. (c a Seidenberg 1959). Ta cho tương ng m i ph n t ai c a A v i c p “ i m s “ (xi, yi) trong ó xi là s ph n t c a dãy con tăng dài nh t k t thúc t i ai và yi là s ph n t c a dãy con gi m dài nh t b t u t ai. Chú ý r ng không có hai ph n t nào có cùng i m s , t c là (xi, yi) ≠ (xj, yj) v i m i i ≠ j. Th t v y, n u ta có ... ai ... aj ..., thì ho c ai < aj và dãy con tăng dài nh t k t thúc t i ai có th kéo dài n aj (và do ó xi < xj), ho c ai > aj và dãy con gi m dài nh t b t u t aj có th ư c b t u t ai (và như th yi > yj). Bây gi ta t o ra m t lư i g m n chu ng th . n s 1 1 r n (xi, yi). M i m t ph n t c a A có th ư c Ta t m i ph n t ai vào chu ng v i t a t vào m t chu ng vì 1 ≤ xi, yi ≤ n v i m i i = 1, 2, ..., n. Hơn n a, không có chu ng nào ư c ch a nhi u hơn m t ph n t , vì (xi, yi) ≠ (xj, yj) v i m i i ≠ j. Vì |A| = n ≥ rs + 1, ta có nhi u v t hơn là s chu ng th ư c tô m trong hình v trên. Như v y ph i có m t ph n t ai n m ngoài mi n tô m. Nhưng i u này có nghĩa là xi ≥ s+1 ho c yi ≥ r + 1 (ho c c hai), úng i u chúng ta c n. T p h p các s th c ư c s p toàn ph n. i u này có nghĩa là v i hai s phân bi t x, y dư i ây, thu c v Dilworth, s t ng quát hóa nh lý thì ho c x < y ho c y < x. B Erdos-Szekeres cho các t p h p mà trong ó hai ph n t có th không so sánh ư c.
M t th t b ph n (y u) trên t p h p P là quan h hai ngôi < gi a các ph n t c a P. Ta nói hai ph n t x và y là so sánh ư c n u x < y ho c y < x (ho c c hai). M t xích là m t t p h p Y ⊆ P sao cho hai ph n t b t kỳ c a Y là so sánh ư c. N u không có hai ph n t khác nhau nào c a Y là so sánh ư c, thì Y ư c g i là i xích. 5 (Dilworth 1950). Trong m i th t b ph n trên t p h p P g m n ≥ sr + 1 ph n B t , t n t i xích có kích thư c s+1 ho c i xích có kích thư c r+1. nh nghĩa hàm s f: Ch ng minh. Gi s r ng không có xíc dài s+1. Khi ó ta có th P {1,..., s} trong ó f(x) là s ph n t l n nh t c a m t xích có ph n t l n nh t x. Theo nguyên lý chu ng và th , s có r+1 ph n t c a P có cùng nh qua ánh x f. Theo nh nghĩa c a f, các ph n t này không so sánh ư c; và như v y chúng t o thành m t i xích có kích thư c r+1. Bài t p 5. T b Dilworh hãy suy ra nh lý Erdos-Szekeres. Bài t p 6. Cho n2+1 i m trong m t ph ng. Ch ng minh r ng t n t i dãy g m n+1 i m (x1,y1),(x2,y2),…,(xn+1,yn+1) sao cho x1 ≤ x2 ≤ …≤ xn+1 và y1 ≥ y2 ≥ … ≥ yn+1, ho c dãy g m n+1 i m sao cho x1 ≤ x2 ≤ …≤ xn+1 và y1 ≤ y2 ≤ … ≤ yn+1 3. nh lý Mantel Dư i ây chúng ta s th o lu n v m t tính ch t t i ưu c trưng c a th . M t th G g m 2n nh không ch a tam giác có th có bao nhiêu c nh? Tam giác là t p h p {x, y, z} g m ba nh mà hai nh b t kỳ u ư c n i v i nhau b i m t c nh. Dĩ nhiên là G có th ch a n2 c nh mà không ch a tam giác: ch c n l y th hai phe y g m hai t p h p m i t p h p có n nh và t t c các c nh n i gi a hai t p h p. Th c t là n2 chính là s c nh l n nh t có th : n u ta thêm m t c nh và th thì s xu t hi n tam giác. Ta s ưa ra 4 ch ng minh cho k t qu p này: ch ng minh th nh t dùng nguyên lý chu ng và th , ch ng minh th hai d a trên phương pháp m b ng hai cách, ch ng minh th ba s d ng b t ng th c AM-GM và ch ng minh th tư s d ng “lý lu n d ch chuy n“ (ta s c p t i ch ng minh này trong ph n sau). nh có n2+1 c nh thì G ch a tam giác. nh lý 6 (Mantel 1907). N u th G v i 2n Ch ng minh th nh t. Ta ch ng minh b ng quy n p theo n. V i n = 1, thì G không th có n2+1 c nh và vì v y m nh úng. Gi s m nh ã úng n n, ta xét th G v i 2 2(n+1) nh và (n+1) + 1 c nh. G i x và y là hai nh k nhau trong G, và H là th con c m sinh trên 2n nh còn l i. N u H ch a ít nh t n2+1 c nh thì theo gi thi t quy n p, ta có ngay pcm. Gi s r ng H có nhi u nh t n2 c nh, khi ó có ít nh t 2n+1 c nh c a G s n i t x và y n các nh c a H.
Theo nguyên lý chu ng và th , gi a 2n+1 c nh này có ít nh t 1 c nh n i t x và m t c nh n i t y n cùng m t nh z thu c H. Như v y G ch a tam giác {x, y, z}. th trên t p h p V g m 2n nh và có m ≥ n2+1 c nh. Ch ng minh th hai. Cho G là Gi s r ng G không ch a tam giác. Khi ó các c nh k nhau không có nh k chung, do ó d(x) + d(y) ≤ 2n v i m i c nh {x, y} ∈ E. C ng theo t t c các c nh c a G, ta có ∑ d ( x) ∑ (d ( x) + d ( y)) ≤ 2mn. = 2 x∈V { x , y }∈E ∑ d ( x) = 2m , ta M t khác, s d ng b t ng th c Cauchy-Schwarz và ng th c Euler x∈V ưc 2    ∑ d ( x)  2m 2 ∑ d ( x) 2 ≥=  x∈V | V |  = n . x∈V ng th c này suy ra m ≤ n2, mâu thu n v i gi thi t. T hai b t Ch ng minh th ba. Gi s G = (V, E) là th trên t p V g m 2n nh và gi s G A ⊆ V là t p h không ch a tam giác. Gi s p c l p l n nh t, t c là t p h p l n nh t các nh sao cho không có nh nào k nhau trong G. Vì G không ch a tam giác t t c các nh k v i nh x ∈ V t c l p và ta suy ra d(x) ≤ |A| v i m i x. o thành m t t p T p h p B = V – A giao v i m i c nh c a G. Tính các c nh c a G tương ng v i nh cu i c a chúng trong B, ta có | E |≤ ∑ x∈B d ( x) . Bây gi b t ng th c AM-GM cho ta | A | + | B | 2 | E |≤ ∑ x∈B d ( x ) ≤| A | . | B |≤   =n . 2   2 4. nh lý Turan th v i k nh mà hai nh b t kỳ u ư c n i v i nhau b i m t M t k-clique là m t c nh. Ví d tam giác là 3-clique. nh lý Mantel kh ng nh r ng n u th v i n nh 2 không ch a 3-clique thì nó có nhi u nh t n /4 c nh. Còn n u k > 3 thì sao? Câu tr l i ư c cho b i k t qu cơ b n c a Paul Turan, k t qu ãm u cho lý thuy t th t i ưu. nh không ch a (k+1)-clique, k ≥ nh lý 7 (Turan 1941). N u th G = (V, E) trên n 2, thì  1n 2 | E |≤ 1 −  . (1)  k 2 Cũng gi ng như nh lý Mantel, nh lý này ư c nghiên c u nhi u l n v i nhi u các ây chúng ta ưa ra ch ng minh nguyên th y c a Turan. Phép ch ng minh khác nhau.
ch ng minh d a trên lý lu n “d ch chuy n tr ng lư ng” s ư c c p trong ph n bài t p. Ngoài ra s còn m t cách ch ng minh s d ng m t ý tư ng hoàn toàn khác – lý lu n xác su t. Ch ng minh. Ta s d ng phép quy n p theo n. Khi n = 2, b t ng th c (1) là hi n nhiên úng. Trư ng h p k=2 chính là nh lý Mantel. Bây gi gi s b t ng th c úng cho mi th trên nhi u nh t n-1 nh, và G = (V, E) là th trên n nh không có (k+1)- th này dĩ nhiên là ph i ch a k-clique, b i n u không ta clique và có s c nh l n nh t. có th thêm c nh. Gi s A là k-clique và B = V – A. k  nh c a A ư c n i b i m t c nh, A ch a e A =   c nh. G i eB là s c nh Vì m i c p 2  n i các nh c a B và eA,B là s c nh n i gi a các c nh c a A và B. Theo gi thi t quy n p, ta có  1  (n − k ) 2 e B ≤ 1 −  .  k 2 Vì G không có k+1 clique nên m i x ∈ B k v i nhi u nh t k-1 nh thu c A, và ta thu ưc eA,B ≤ (k-1)(n-k). C ng các b t ng th c này l i và s d ng ng th c 2  k  n   1n 2 1 −  =      k  2  2  2  ta suy ra r ng  k   k  n − k  2 | E |≤ e A + e B + e A, B ≤   +    2   2  2  + (k − 1)(n − k )       k  n − k  2  1n 2 =  1 − = 1 −  .  2   k  k 2 Bài t p 7. Gi s r ng n là b i s c a k. Hãy xây d ng m t th không ch a (k+1)-clique, trong ó s các c nh t ư c c n trên (1) trong nh lý 7. c l p α(G) c a th G là s l n nh t các nh ôi m t không k nhau c a G. Bài t p 8. Nh c l i ch s th v i n nh và nk/2 c nh, k ≥ 1, thì α(G) ≥ Hãy ch ng minh i ng u c a nh lý Turan: N u G là n/(k+1). 5. nh lý Dirichlet ây ta trình bày m t ng d ng c a nguyên lý chu ng và th mà Dirichlet ã s d ng, và chính vì ng d ng này mà nguyên lý này ư c g n v i tên ông. Nó liên quan n v n t n t i x p x h u t t t cho các s vô t . K t qu này thu c v lý thuy t s nhưng lý lu n là t h p.
nh lý 8 (Dirichlet 1879). N u x là m t s th c. V i m i s nguyên dương n,t n t i s h u t p/q sao cho 1 ≤ q ≤ n và p 1 1 x− < ≤ 2. q nq q Ch ng minh. Cho ch ng minh này, ta g i {x} là ph n l c a s th c x, t c là {x} = x – [x]. N u x là s h u t thì không có gì ch ng minh. Vì th , ta gi s r ng x là vô t và xét n+1 s {ax}, a = 1, 2, …, n+1. Ta t n+1 s này vào n chu ng  1   1 2   n −1   0, ,  , ,...,  ,1.  n n n  n  (Không có s nào trong các s nói trên trùng v i u mút các o n, vì x là vô t ). Theo nguyên lý chu ng và th , có m t o n nào ó ch a nhi u hơn m t s , vì d là {ax} và {bx}v i a > b, và do ó cách nhau không quá 1/n. t q = a – b, ta th y r ng t n t i s nguyên p sao cho |qx – p| < 1/n, t ó suy ra k t qu c n ch ng minh b ng cách chia cho q. Hơn n a, q là hi u c a hai s nguyên thu c 1, 2, …, n+1, do ó q ≤ n. 6. th ư c tô cs c th ư c tô c s c Ta tô màu các c nh c a th y Kn trên n nh. Ta nói r ng (swell-colored) n u m i tam giác ch a 1 ho c 3 màu, nhưng không ch a 2 màu và th có nhi u hơn m t màu. Có nghĩa là, ta c n s d ng ít nh t 2 màu và v i m i tam giác, ho c là t t c các c nh c a nó có cùng màu ho c có màu khác nhau. Ta có th ch ng minh ư c r ng (hãy ch ng minh!) Kn không th ư c tô c s c v i úng hai màu. Cũng có th th y r ng K3 và K4 là nh ng th Kn duy nh t có th tô c th Kn khác c n nhi u màu hơn vì chúng có b c liên thông cao hơn. s c v i 3 màu; các S d ng nguyên lý chu ng và th , ta có th ch ng minh ư c ch n dư i sau. ư c tô nh lý 9 (Ward-Szabo 1994). th y trên n nh không th c s c v i ít hơn n + 1 màu. Ch ng minh. Gi s Kn ư c tô c s c v i r màu khác nhau. G i N(x, c) là s c nh k v i nh x ư c tô màu c. C nh x0 và c0 sao cho N(x0, c0) l n nh t, và ký hi u giá tr l n nh t này là N. n-1 c nh k v i x0 có th ư c chia thành ≤ r nhóm màu, m i nhóm có N ho c ít hơn ph n t . Theo nguyên lý chu ng và th N.r ≥ n – 1.
G i x1, x2, …, xN là các nh k v i x0 b i N c nh có màu c0. G i G là th con ( y ) c a Kn c m sinh t t p h p các nh {x0, x1,..., xN}. Tính c s c c a Kn ư c c m sinh cho G và như v y m i c nh c a G có cùng màu c0. Vì Kn có ít nh t hai màu nên t n t i nh y thu c Kn không n m trong G và sao cho ít nh t m t c nh n i y v i G có màu khác c0 . nh 10. N+1 c nh n i y t i G ư c tô màu khác nhau và khác v i c0. Kh ng T kh ng nh này ta suy ra r ≥ N + 2, t ó, cùng v i b t ng th c N.r ≥ n – 1 suy ra r(r-2) ≥ n – 1, và t ó r ≥ n + 1 là i u c n ch ng minh. Như v y ta ch còn c n ch ng minh kh ng nh trên. N u m t c nh n i y t i G, ví d {y, x1}, có màu c0 thì theo tính c s c, c nh {y,x0} ph i ư c tô màu c0, mâu thu n v i cách ch n y (nh c l i là x1, x2,…,xN là t t c các nh k v i x0 ư c n i b ng c nh màu c0). Ti p theo, n u hai c nh nào ó n i y v i G, ch ng h n {y, x1} và {y, x2} có cùng màu thì theo tính c s c c a Kn ta có c nh {x1, x2} cũng ư c tô b ng màu ó. Nhưng {x1, x2} thu c G và có màu c0 và như v y {y, x1} ph i có màu c0 là i u mà ta ã ch ng minh trên là không th . i u này k t thúc phép ch ng minh kh ng nh và cũng là k t thúc ch ng minh nh lý. Tính t i ưu c a c n dư i cho b i nh lý 9 có th ư c ch ng t s d ng m t c u hình c q ch a úng q2 i m g i là “m t ph ng afine”. Ta hi u r ng m t ph ng afine AG(2,q) b và úng q+1 l p ( ư c g i là “bút chì”) các ư ng th ng song song, m i l p ch a q ư ng th ng (hai ư ng th ng là song song n u chúng không có i m chung). Hơn n a, hai i m b t kỳ n m trên úng m t ư ng th ng. Khi có 1 m t ph ng như v y, ta có th xây d ng m t phép tô c s c cho K q v i q+1 2 màu như sau. Ta nh c a K q v i các i m c a AG(2,q) và cho tương ng ng nh t các 2 m t màu duy nh t cho m i m t trong s q+1 bút chì các ư ng th ng song song. xác nh cách tô c s c, ta xét hai i m khác nhau x và y c a K q . Hai i m này thu c duy 2 nh t m t ư ng th ng và ư ng th ng này, n lư t mình thu c duy nh t m t bút chì. Ta tô màu c nh {x,y} b ng màu c a bút chì này. Vì hai i m b t kỳ n m trên m t ư ng th ng duy nh t và hai ư ng th ng song song không có i m chung, m i c nh c a m t tam giác s ư c tô b ng các màu khác và như v y, phép tô là c s c như mong mu n. Th c t , Ward và Szabo (1994) ã ch ng minh r ng i u ngư c l i cũng úng: n u th K q (q ≥ 2) có th tô c s c b ng q+1 màu thì phép tô này có th ư c dùng xây d ng 2 m t ph ng afine b c q. [Trích t cu n Extremal Combinatorics c a Stasys Jukna]