Tóm tắt luận văn thạc sĩ khoa học: Bài toán màu và ứng dụng giải toán sơ cấp

Chia sẻ: Lang Nguyen | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

369
lượt xem 74
download

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

Tóm tắt luận văn thạc sĩ khoa học: Bài toán màu và ứng dụng giải toán sơ cấp nhằm ứng dụng lý thuyết đồ thị nói chung và bài toán tô màu nói riêng để giải quyết bài toán không mẫu mực, các bài toán thường gặp trong thực tế và một số bài toán trong các kỳ thi toán quốc tế.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận văn thạc sĩ khoa học: Bài toán màu và ứng dụng giải toán sơ cấp

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG NGUY N TH VI T TH O BÀI TOÁN TÔ MÀU VÀ NG D NG GI I TOÁN SƠ C P Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ C P Mã s : 60.46.40 TÓM T T LU N VĂN TH C SĨ KHOA H C Đà N ng - năm 2011
2 Công trình ñư c hoàn thành t i TRƯ NG Đ I H C SƯ PH M, Đ I H C ĐÀ N NG Ngư i hư ng d n khoa h c: PGS. TSKH Tr n Qu c Chi n Ph n bi n 1: TS. Cao Văn Nuôi Ph n bi n 2: PGS. TS. Huỳnh Th Phùng Lu n văn s ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p Th c sĩ khoa h c h p t i Đ i h c Đà N ng vào ngày 26/11/2011 Có th tìm hi u lu n văn t i: - Trung tâm Thông tin - H c li u, Đ i h c Đà N ng - Thư vi n trư ng ĐH Sư ph m, Đ i h c Đà N ng
3 M Đ U 1. Lý do ch n ñ tài Khái ni m lý thuy t ñ th ñư c nhi u nhà khoa h c ñ c l p nghiên c u và có nhi u ñóng góp trong lĩnh v c toán h c ng d ng. S d ng bài toán tô màu ñ gi i toán là m t phương pháp khá hay trong lý thuy t ñ th . Phương pháp này không ñòi h i nhi u v ki n th c và kh năng tính toán mà ch y u ñòi h i s sáng t o trong vi c ñưa ra m t mô hình c th và linh ho t trong cách tư duy, không th áp d ng m t cách máy móc ñư c. Đó là ñi m m nh cũng như cái khó c a bài toán tô màu. Mong mu n c a tác gi lu n văn là có th cung c p cho ngư i ñ c m t cái nhìn t ng quan nhưng cũng khá chi ti t v vi c s d ng tô màu như m t ngh thu t gi i toán, hy v ng nó s giúp ích ph n nào cho vi c b i dư ng h c sinh chuyên các trư ng THPT, phát tri n tư duy cho h c sinh, m ra m t hư ng nghiên c u m i cho nh ng ai quan tâm. 2. M c ñích nghiên c u ng d ng lí thuy t ñ th nói chung và bài toán tô màu ñ th nói riêng ñ gi i các bài toán không m u m c, các bài toán thư ng g p trong th c t và m t vài bài toán trong các kì thi Toán qu c t . 3. Đ i tư ng và ph m vi nghiên c u - Nghiên c u t ng quan v lí thuy t ñ th , tô màu ñ th . - Nghiên c u l p các bài toán ng d ng tô màu ñ th . 4. Phương pháp nghiên c u + Nghiên c u lí thuy t D a vào các giáo trình ñã ñư c h c, các tài li u liên quan ñ n lí thuy t ñ th và tô màu ñ th . + Nghiên c u th c ti n Nghiên c u các bài toán trong các giáo trình và tài li u tham kh o. 5. Ch n tên ñ tài Bài toán tô màu và ng d ng gi i toán sơ c p.
4 6. C u trúc lu n văn G m ba chương Chương 1: Ki n th c cơ s Chương 2: Bài toán tô màu ñ th Chương 3: ng d ng CHƯƠNG 1. KI N TH C CƠ S 1.1 CÁC KHÁI NI M CƠ B N 1.1.1 Các ñ nh nghĩa 1.1.2 B c c a ñ th 1.1.3 Các ñơn ñ th ñ c bi t 1.1.4 Đ th ñư ng 1.2 ĐƯ NG ĐI, CHU TRÌNH VÀ TÍNH LIÊN THÔNG 1.2.1 Các ñ nh nghĩa 1.2.2 Các bài toán v ñư ng ñi 1.2.3 M t s ñ nh lí 1.3 Đ TH PH NG 1.3.1 Bài toán m ñ u 1.3.2 Đ th ph ng 1.3.3 Công th c Euler 1.3.4 Đ nh lí Kuratowski CHƯƠNG 2. BÀI TOÁN TÔ MÀU Đ TH 2.1 GI I THI U 2.2 TÔ MÀU Đ NH 2.2.1 Đ th ñ i ng u 2.2.2 Các khái ni m cơ b n Đ nh nghĩa 2.1 Tô màu ñ nh m t ñơn ñ th là s gán màu cho các ñ nh c a nó sao cho không có hai ñ nh k nhau ñư c gán cùng m t màu. Đ nh nghĩa 2.2 S c s c a ñ th G, ký hi u là χ(G), là s màu t i thi u c n thi t ñ tô màu các ñ nh c a ñ th (m i ñ nh m t màu), sao cho hai ñ nh k nhau tùy ý ñư c tô b ng hai màu khác nhau.
5 2.2.3 M t s ñ nh lí Đ nh lí 2.1 M t chu trình ñ dài l luôn có s c s b ng 3. Đ nh lí 2.2 (Đ nh lí Konig) M t ñơn ñ th có th tô b ng hai màu khi và ch khi nó không có chu trình ñ dài l . H qu 2.1 T t c các chu trình ñ dài ch n ñ u có s c s b ng 2. Đ nh lí 2.3 Đ th ñ y ñ Kn v i n ñ nh luôn luôn có s c s b ng n. Đ nh lí 2.4 V i m i s nguyên dương n, t n t i m t ñ th không ch a K3 và có s c s b ng n. Đ nh lí 2.5 N u ñ th G ch a ñ th con ñ ng c u v i ñ th ñ y ñ Kn thì λ(G)≥n. Đ nh lí 2.6 χ(G) ≤ P ∆(G) + 1 v i m i ñ th G, trong ñó ∆(G) là b c ñ nh l n nh t c a G (ñ ng th c x y ra khi G = Kn ho c G là chu trình ñ dài l ). Đ nh lí 2.7 (Brooks) Cho G là ñơn ñ th n ñ nh, liên thông khác Kn và không ph i chu trình ñ dài l . Khi ñó χ (G) ≤ ∆(G). 2.3 THU T TOÁN TÔ MÀU Đ NH i) L p danh sách các ñ nh ñ th . E’:= [ v1 , v2 ,..., vn ] theo th t b c gi m d n: d (v1 ) ≥ d (v2 ) ≥ ... ≥ d (vn ) . Đ t i:=1 ii) Tô màu i cho ñ nh ñ u tiên trong danh sách. Duy t l n lư t các ñ nh ti p theo và tô màu i cho ñ nh không k ñ nh ñã ñư c tô màu i. iii) N u t t c các ñ nh ñã ñư c tô màu thì k t thúc: Đ th ñã ñư c tô màu b ng i màu. Ngư c l i sang bư c iv). iv) Lo i kh i E’ các ñ nh ñã tô màu, ñ t i:=i+1, và quay l i bư c ii). 2.4 TÔ MÀU Đ TH PH NG 2.4.1 M t s ñ nh lí v s c s c a ñ th ph ng Đ nh lí 2.8 M i b n ñ t o b i các ñư ng th ng trên m t ph ng có th tô b ng hai màu. Đ nh lí 2.9 Đi u ki n c n và ñ ñ b n ñ có th tô b ng hai màu là m i ñ nh c a ñ th ph ng tương ng có b c ch n l n hơn ho c b ng 2.
6 Đ nh lí 2.10 (Kempe – Heawood) M i ñ th ph ng không có ñ nh nút ñ u có s c s không l n hơn 5. Đ nh lý 2.11 (Appel - Haken)( Đ nh lí b n màu - 1976) M i ñ th ph ng không có ñ nh nút ñ u có s c s không quá b n. 2.4.2 M t ví d tìm s c s ñ th 2.5 TÔ MÀU C NH Đ nh nghĩa 2.3 Tô màu c nh m t ñơn ñ th là s gán màu cho các c nh c a nó sao cho không có hai c nh k ñư c gán cùng m t màu Đ nh nghĩa 2.4 S c s c nh c a ñ th G, kí hi u là χ’ (G) là s màu ít nh t c n dùng ñ tô trên các c nh c a ñ th , m i c nh m t màu sao cho hai c nh k nhau tùy ý ñư c tô b ng hai màu khác nhau. Ta có th chuy n bài toán s c s c nh v bài toán s c s . Ta có χ ' ( G ) = χ ( L ( G ) ) Đ nh lí 2.12 N u G là ñ th lư ng phân thì χ’ (G) = ∆(G). Đ c bi t, s c s c nh c a ñ th lư ng phân ñ Km,n là max{m, n}. Đ nh lí 2.13 (Đ nh lí Vizing) V i m i ñơn ñ th G, ∆ (G ) ≤ χ '( G ) ≤ ∆ ( G ) + 1 Đ nh lí 2.14 i) N u n ch n thì χ ' ( K n ) = ∆ ( K n ) = n − 1 ii) N u n l thì χ ' ( K n ) = ∆ ( K n ) + 1 = n 2.6 NGUYÊN LÝ DIRICHLET 2.6.1 M ñ u 2.6.2 Nguyên lý Dirichlet t ng quát 2.7 S RAMSEY Đ nh nghĩa 2.5 Cho hai s nguyên i ≥ 2, j ≥ 2 . S nguyên dương n g i là có tính ch t (i,j)-Ramsey, n u Kn v i m i c nh ñư c tô b ng m t trong hai màu xanh ho c ñ thì (a) Kn ch a ho c Ki ñ ho c Kj xanh và (b) Kn ch a ho c Kj ñ ho c Ki xanh. Đ nh nghĩa 2.6 S Ramsey R(i,j) là s nguyên dương nh nh t có tính ch t (i,j)-Ramsey. M nh ñ 2.2 R(3,3) = 6 M nh ñ 2.3 R(2,j) = j ∀ j ≥ 2
7 M nh ñ 2.6 (Đ nh lý Ramsey) R(i,j) t n t i v i m i i ≥ 2, j ≥ 2. M nh ñ 2.8 R(3,4) = 9 M nh ñ 2.9 R(3,5) = 14 M nh ñ 2.10 R(4,4) = 18 M nh ñ 2.11 R(2,2,....,2;2) = 2. M nh ñ 2.12 R(3,3,3;2) = 17
8 CHƯƠNG 3. NG D NG 3.1 NG D NG TÔ MÀU Đ TH Đ GI I QUY T CÁC V N Đ TH C T Bài toán 3.1.1 M t s thú nh p v 6 lo i thú khác nhau, mà ta kí hi u là A, B, C, D, E, F. M t s lo i trong s ñó có th s ng cùng trong m t chu ng, m t s loài s ăn th t loài khác n u nh t chung chu ng. B ng sau ñây cho bi t nh ng loài nào không th s ng chung v i nhau: Lo i A B C D E F Không th s ng B, A, C, A, B, D, C, B, C, D, v i C E E F F E H i c n ít nh t bao nhiêu chu ng ñ có th nh t t t c các lo i thú ñó? Gi i Ta s mô hình hóa b ng ñ th và ñưa v bài toán tô màu như sau: M i ñ nh c a ñ th là m t loài thú, hai ñ nh ñư c n i v i nhau b ng m t c nh n u hai loài thú không th nh t chung m t chu ng. Áp d ng thu t toán tô màu ñ th m c 2.3, ta tìm ra ñư c s lư ng chu ng ít nh t c n có là 3. (Hình 3.4) A(3) F(1) B(2) E(3) C(1) D(2) Hình 3.4
9 Như v y, ta thu ñư c l i gi i cho bài toán 3.1.1 như sau: Chu ng 1 Chu ng 2 Chu ng 3 C và F B và D A và E Bài toán 3.1.2 Phân chia t n s Bài toán 3.1.3 L p th i gian bi u Trong m t trư ng ñ i h c có m gi ng viên x1, x2, …xm gi ng d y n l p y1, y2, … yn, m i l p ñư c d y trong pi ti t. T i m t th i ñi m, m i gi ng viên ch có th d y nhi u nh t 1 l p và m i l p ch ñư c d y nhi u nh t b i m t gi ng viên. Ban giám hi u mu n l p m t th i gian bi u sao cho s d ng ít th i gian nh t th a mãn yêu c u trên. Bài toán 3.1.4 Bài toán n sinh Lucas. Bài toán 3.1.5 Tô màu b n ñ . Bài toán 3.1.6 Các thanh ghi ch s . 3.2 M T S BÀI T P LIÊN QUAN Đ N S C S C A Đ TH Bài toán 3.2.1 Ch ng minh không th dùng hai màu ñ tô các ñ nh c a m t th t giác ñ u ñư c. Gi i Xét ñ th G(V, E) v i các ñ nh là các ñ nh c a th t giác và các c nh là các c nh c a th t giác. Do G(V, E) là m t chu trình có ñ dài 7 – ñ dài l - nên có s c s b ng 3, vì th không th dùng hai màu ñ tô các ñ nh c a m t th t giác ñ u ñư c. Bài toán 3.2.2 Ch ng minh v i m i s t nhiên n, luôn t n t i ñ th G (V, E) có s c s b ng n. Bài toán 3.2.3 Cho G là m t ñơn ñ th ph ng. Ch ng minh r ng G có th tô ñúng b ng hai màu khi và ch khi G là ñ th lư ng phân.
10 Bài toán 3.2.4 Ch ng minh r ng m t ñơn ñ th ph ng liên thông có th tô ñúng các mi n b ng hai màu khi và ch khi ñó là m t ñ th Euler. 3.3 NG D NG TÔ MÀU Đ TH TRONG GI I TOÁN 3.3.1 M t s kh ng ñ nh v tô màu ñ th Kh ng ñ nh 3.1 Cho G(V, E) là ñ th ñ y ñ v i các c nh ñư c tô b ng màu xanh ho c ñ . Khi ñó t ng s ñ nh mà m i ñ nh là mút c a m t s l c nh màu ñ là s ch n. Ví d 3.1 Trong l p 10/1, An có s b n thân là m t s l . Ch ng minh r ng có m t h c sinh khác An mà s b n thân cũng là m t s l . Gi i Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: - T p ñ nh V: L y n ñi m trong m t ph ng tương ng v i n h c sinh và dùng th t c a n h c sinh ñó kí hi u các ñ nh. - T p c nh E: Hai ñ nh ñư c n i v i nhau b ng m t c nh màu xanh khi hai h c sinh tương ng v i hai ñ nh ñó không thân nhau, b ng m t c nh màu ñ khi hai h c sinh tương ng v i hai ñ nh ñó thân nhau. Gi i toán trên ñ th . Đ th G(V, E) trên là ñ th màu ñ y ñ v i các c nh ñư c tô màu xanh ho c ñ . T gi thi t suy ra, ñ th G(V, E) có m t ñ nh là mút c a m t s l c nh màu ñ . Theo kh ng ñ nh 3.1 thì ñ th G(V, E) còn có ít nh t m t ñ nh là mút c a m t s l c nh màu ñ . Suy ra có m t h c sinh khác An có s b n thân là s l . Ví d 3.2 Trong m t l p h c có m t em h c sinh có s b n thân là m t s l . Ch ng minh r ng trong l p có 2 em có s b n thân chung là m t s ch n. Gi i G i A là h c sinh chơi thân v i m t s l b n trong l p. Các h c sinh chơi thân v i A là A1, A2, A3, … A2n+1. Xét G(V, E) là ñ th màu ñ y ñ v i t p ñ nh là A1, A2, A3, … A2n+1.
11 Hai ñ nh n i v i nhau b ng m t c nh màu ñ n u hai h c sinh tương ng chơi thân v i nhau, b ng màu xanh n u không chơi thân v i nhau. Đ th G(V, E) có l ñ nh. Theo kh ng ñ nh 3.1, t ng s ñ nh mà m i ñ nh là mút c a l c nh màu ñ là m t s ch n, suy ra ñ th màu ñ y ñ G(V, E) ph i có ñ nh là mút c a ch n c nh màu ñ . G i ñ nh ñó là Ai. Khi ñó, A và Ai có s b n thân chung là m t s ch n. Kh ng ñ nh 3.2 G (V, E) là ñ th ñ y ñ v i các c nh ñư c tô b i màu xanh ho c màu ñ . Khi ñó t n t i ít nh t hai ñ nh c a ñ th mà s c nh màu ñ t i hai ñ nh này b ng nhau. Ví d 3.3 Có 10 ñ i bóng thi ñ u v i nhau theo th th c m i ñ i l n lư t ñ u v i các ñ i còn l i. Ch ng minh r ng b t kỳ th i ñi m nào ta cũng tìm ñư c ít nh t hai ñ i có s tr n ñã ñ u như nhau. Gi i Ta xây d ng ñ th màu ñ y ñ G(V, E) mô t bài toán. T p ñ nh V: L y 10 ñi m trên m t ph ng tương ng v i 10 ñ i bóng và dùng th t c a m i ñ i ñó ñ kí hi u các ñ nh. T p c nh E: Hai ñ nh ñư c n i v i nhau b ng m t c nh màu xanh khi hai ñ i bóng tương ng v i hai ñ nh ñó chưa ñ u v i nhau, b ng m t c nh màu ñ khi hai ñ i bóng tương ng v i hai ñ nh ñó ñã thi ñ u v i nhau. Gi i toán trên ñ th : Đ th G(V, E) ñư c xây d ng như th là ñ th màu ñ y ñ v i các c nh ñư c tô xanh ho c ñ . Theo kh ng ñ nh 3.2 thì ñ th G(V, E) có ít nh t hai ñ nh là mút c a cùng m t s c nh ñ . Suy ra có ít nh t hai ñ i bóng ñã ñ u m t s tr n như nhau. Ví d 3.4 Ch ng minh trong m t l p h c có ít nh t hai h c sinh mà s b n thân trong l p c a m i h c sinh này b ng nhau. Gi i Ta xây d ng ñ th màu G(V, E) ñ y ñ mô t bài toán. T p ñ nh V: L y n ñi m trên m t ph ng tương ng v i n h c sinh và dùng th t c a n h c sinh ñó ñ kí hi u các ñ nh. T p c nh E: Hai ñ nh ñư c n i v i nhau b ng m t c nh màu xanh khi hai h c sinh tương ng v i hai ñ nh ñó không thân nhau,
12 b ng m t c nh màu ñ khi hai h c sinh tương ng v i hai ñ nh ñó thân nhau. Gi i toán trên ñ th : Đ th G(V, E) ñư c xây d ng như th là ñ th màu ñ y ñ v i các c nh ñư c tô xanh ho c ñ . Theo kh ng ñ nh 3.2 thì ñ th G(V, E) có ít nh t hai ñ nh là mút c a cùng m t s c nh ñ . Suy ra có ít nh t hai h c sinh mà m i h c sinh có s b n thân trong l p b ng nhau. Ví d 3.5 Ch ng minh trong 100 s t nhiên b t kỳ, luôn t n t i hai s a và b sao cho trong 100 s ñã cho thì s các s nguyên t cùng nhau v i a b ng s các s nguyên t cùng nhau v i b. Kh ng ñ nh 3.3 Đ th ñ y ñ G(V, E) g m n ñ nh v i các c nh ñư c tô b ng màu xanh ho c ñ mà trong 4 ñ nh tùy ý có ít nh t m t ñ nh ñư c n i b ng c nh màu ñ v i 3 ñ nh còn l i. Khi ñó ñ th G(V, E) có ít nh t (n-3) ñ nh mà m i ñ nh này ñư c n i v i các ñ nh còn l i b ng c nh màu ñ Ví d 3.6 (Vô ñ ch Mĩ 1982) Trong m t nhóm g m có 1982 ngư i, c 4 ngư i b t kỳ thì có th ch n ra ñư c ít nh t m t ngư i quen v i 3 ngư i còn l i. H i có ít nh t bao nhiêu ngư i quen v i t t c nh ng ngư i trong nhóm Gi i Ta xây d ng ñ th màu ñ y ñ G(V, E) mô t bài toán. T p ñ nh V: L y 1982 ñi m trên m t ph ng hay trong không gian tương ng v i s ngư i c a nhóm và dùng mã s t ng ngư i ñ ghi tên các ñi m tương ng. T p c nh E: Hai ñ nh ñư c n i v i nhau b ng m t c nh màu ñ khi hai ngư i tương ng v i hai ñ nh ñó quen nhau, b ng m t c nh màu xanh khi hai ngư i ñó không quen nhau. Gi i toán trên ñ th : Đ th G(V, E) ñư c xây d ng như th là ñ th màu ñ y ñ v i 1982 ñ nh và c 4 ñ nh tùy ý thì có ít nh t m t ñ nh n i v i 3 ñ nh còn l i b ng c nh màu ñ . Theo kh ng ñ nh 3.3 thì ít nh t có 1982-3=1979 ñ nh ñư c n i v i các ñ nh còn l i b ng c nh màu
13 ñ . V y s nh nh t nh ng ngư i quen v i t t c ngư i còn l i là 1979. Ví d 3.7 Cho 2011 s t nhiên tùy ý, mà c 4 s b t kỳ trong s ñó thì có ít nh t m t s có ư c chung v i 3 s còn l i. Ch ng minh t n t i ít nh t 2008 s mà m i s này có ư c chung v i t t c các s còn l i. Xét hai dãy s nguyên dương: a1 = 2, a2=5,…an+1 = (n+1)an +1 u2 = 3, u3 = 6,…, un+1 = (un-1)n +2. Ta có các kh ng ñ nh sau: Kh ng ñ nh 3.4 a) Đ th ñ y ñ v i an+1 ñ nh mà các c nh ñư c tô b ng n màu, luôn luôn có ñ th con ñ y ñ K3 v i các c nh cùng màu. b) Đ th ñ y ñ v i un+1 (n≥1) ñ nh mà các c nh ñư c tô b ng n màu, luôn luôn có ñ th con ñ y ñ K3 v i các c nh cùng màu. Ví d 3.8 Ch ng minh r ng t sáu s vô t tùy ý có th ch n ra ñư c ba s (mà ta s g i là a, b, c) sao cho a+b, b+c, c+a cũng là s vô t . Gi i a) Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: - T p ñ nh V: L y 6 ñ nh không th ng hàng trên m t ph ng tương ng v i 6 s vô t . - T p c nh E: Hai ñ nh mang s a và b ñư c n i v i nhau b i m t c nh tô màu ñ n u t ng c a chúng là s vô t , tô màu xanh n u t ng c a chúng là s h u t . b) Gi i toán trên ñ th : Ta có ñ th ñ y ñ g m 6 ñ nh và ñư c tô b ng hai màu c nh. Theo kh ng ñ nh 3.4 thì trong ñ th G(V, E) luôn t n t i m t tam giác cùng màu. Gi s tam giác ñó có ba ñ nh kí hi u là a, b, c. Ch có hai kh năng x y ra: 1. N u tam giác ñó là tam giác xanh. Khi ñó, a+b, b+c, c+a là 3 s h u t . Lúc này (a+b) + (b+c) – (c+a) = 2b cũng là s h u t . Đi u này vô lý vì b là s vô t . 2. N u tam giác ñó là tam giác ñ . Khi ñó, a+b, b+c, c+a là 3 s vô t . Đó là ñi u ph i ch ng minh.
14 Ví d 3.9 Cho 6 s nguyên dương tùy ý. Ch ng minh r ng luôn có th ch n ra ñư c 2 b 3 s mà trong m i b , t ng ñôi m t ñ u là nguyên t cùng nhau ho c ñ u không nguyên t cùng nhau. Gi i a) Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: - T p ñ nh V: L y sáu ñ nh không th ng hàng trên m t ph ng tương ng v i sáu s cho ñ bài. - T p c nh E: Hai ñ nh ñư c n i v i nhau b i m t c nh tô màu xanh n u hai s tương ng nguyên t cùng nhau, tô màu ñ n u hai s tương ng không nguyên t cùng nhau. b) Gi i toán trên ñ th : Ta có ñ th ñ y ñ g m sáu ñ nh và ñư c tô b ng hai màu c nh. Theo kh ng ñ nh 3.4 thì trong ñ th G(V, E) luôn t n t i ít nh t tam giác v i các c nh cùng màu ñ ho c xanh. N u c hai tam giác ñ u màu ñ , thì ta có hai b ba s , mà trong m i b , chúng ñôi m t nguyên t cùng nhau. N u ch có m t tam giác màu ñ , thì ta ñư c m t b ba s ñôi m t nguyên t cùng nhau, và m t b ba s ñôi m t không nguyên t cùng nhau. N u c hai tam giác màu xanh, nghĩa là ta ñư c hai b ba s , mà trong m i b , chúng ñôi m t không nguyên t cùng nhau. Ví d 3.10 Cho sáu ñư ng th ng trong không gian, trong ñó không có ba ñư ng th ng nào song song, không có ba ñư ng th ng nào ñ ng quy và không có ba ñư ng th ng nào n m trong m t m t ph ng. Ch ng minh r ng t sáu ñư ng th ng ñó bao gi cũng l y ra ñư c ba ñư ng th ng ñôi m t chéo nhau. Nh n xét Các ví d 3.8, 3.9, 3.10 có th phát bi u l i như sau: “Cho ñ th ñ y ñ 6 ñ nh K6 v i các c nh ñư c tô b i m t trong hai màu. Ch ng minh luôn t n t i ñ th con K3 v i ba c nh cùng màu”. Trong m c 2.7 v s Ramsey, ta ñã bi t r ng R(3,3)=6 (m nh ñ 2.2), n=6 là s nguyên dương nh nh t th a mãn tính ch t: N u m i c nh c a ñ th ñ y ñ Kn ñư c tô b i m t trong hai màu (ch ng h n xanh ho c ñ ) thì Kn ch a K3 xanh ho c ñ . V i m i s nguyên dương m>n thì ñ th Km cũng có tính ch t
15 như th . Như v y, các ví d 3.8, 3.9, 3.10 có th gi i như cách ch ng minh m nh ñ 2.2. Ví d 3.11 Có 17 thành ph mà t m i thành ph ñ u có th ñi ñ n 16 thành ph còn l i b ng m t trong ba phương ti n: Xe bus, tàu ñi n ng m và xe l a. Bi t r ng t ng c p hai thành ph ch có th ñi l i b i m t phương ti n trong ba phương ti n trên. Ch ng minh r ng luôn có 3 thành ph mà ta có th ñi l i b i cùng m t phương ti n. Gi i a) Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: - T p ñ nh V: L y 17 ñ nh không th ng hàng trên m t ph ng tương ng v i 17 thành ph cho ñ bài. - T p c nh E: Hai ñ nh ñư c n i v i nhau b i m t c nh tô màu ñ n u hai thành ph có th ñi l i b ng xe bus, tô màu xanh n u hai thành ph ñi l i b ng tàu ñi n ng m, và tô màu vàng n u hai thành ph ñi l i b ng xe l a. b) Gi i toán trên ñ th : Ta có ñ th ñ y ñ g m 17 ñ nh và ñư c tô b ng ba màu c nh. Theo kh ng ñ nh 3.4 thì trong ñ th G(V, E) luôn t n t i m t tam giác cùng màu. Đi u ñó có nghĩa là luôn có 3 thành ph mà ta có th ñi l i b i cùng m t phương ti n. Nh n xét: Ta ñã bi t r ng R(3,3,3;2)=17 (M nh ñ 2.12), như v y, Ví d 3.11 hoàn toàn có th ñư c gi i như cách ch ng minh M nh ñ 2.12. Kh ng ñ nh 3.5 Trong m t ñ th ñ y ñ có un+1 – 1 ñ nh ( n ≥ 2 ) v i n màu c nh (các c nh ñư c tô b ng n màu), sao cho không tam giác cùng màu nào, luôn luôn có hình năm c nh v i các c nh cùng màu và các ñư ng chéo ñư c tô b ng các màu khác. Ví d 3.12 M t nhóm g m 5 thành viên trong ñó m i b ba ñ u có 2 ngư i quen nhau và 2 ngư i không quen nhau. Ch ng minh r ng có th x p c nhóm ng i xung quanh 1 bàn tròn ñ m i ngư i ng i gi a 2 ngư i mà thành viên ñó quen. Ví d 3.13 Cho 5 s t nhiên l n hơn 1, mà c 3 s b t kỳ ñ u có 2 s nguyên t cùng nhau và hai s không nguyên t cùng nhau.
16 Ch ng minh r ng có th ghi 5 s trên lên m t ñư ng tròn, ñ m i s ñ u ñ ng gi a 2 s mà nó nguyên t cùng nhau (ho c không nguyên t cùng nhau) v i hai s bên c nh. Gi i (Ví d 3.12 và Ví d 3.13) Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: a) T p ñ nh V: L y 5 ñi m trên m t ph ng, không có 3 ñi m nào th ng hàng tương ng v i 5 thành viên (5 s t nhiên l n hơn 1). Dùng ngay tên các thành viên (các s ) ñ ghi tên các ñi m tương ng. b) T p c nh E: C nh ñ ñ n i gi a hai ñ nh tương ng v i hai ngư i quen nhau (hai s nguyên t cùng nhau). C nh xanh ñ n i gi a hai ñ nh tương ng v i hai ngư i không quen nhau (hai s không nguyên t cùng nhau). T gi thi t bài toán suy ra trong ñ th G không có tam giác cùng màu. Theo kh ng ñ nh 3.5, v i n=2 ñ th G tương ng là ña giác 5 c nh v i các c nh màu ñ và các ñư ng chéo màu xanh ho c ngư c l i. Khi ñó d a theo ñư ng g p khúc khép kín màu ñ mà s p x p các thành viên (các s ) tương ng ng i xung quanh m t bàn tròn (lên m t ñư ng tròn), thì m i thành viên (m i s ) s ng i gi a hai ngư i mà thành viên có quen (ñ ng gi a hai s mà nó nguyên t cùng nhau). Kh ng ñ nh 3.6 Đ th ñ y ñ g m n ñ nh ( n ≥ 6 ) và ñư c tô b ng không quá 2 màu c nh, thì luôn có ít nh t n – 4 tam giác cùng màu. Ví d 3.14 Ch ng minh r ng trong n ( n ≥ 6 ) ngư i tùy ý luôn ch n ñư c n - 4 b ba, mà trong m i b ba này ho c t ng ñôi m t quen nhau ho c t ng ñôi m t không quen nhau. Ví d 3.15 Ch ng minh r ng trong n ( n ≥ 6 ) s nguyên dương tùy ý luôn luôn ch n ñư c n - 4 b ba, mà trong m i b ba này t ng c p s có ư c chung ho c nguyên t cùng nhau. Ví d 3.16 V i n=5 thì các kh ng ñ nh phát bi u trong các Ví d 3.14, 3.15 còn ñúng n a không?
17 Gi i (Ví d 3.14, 3.15) a) Xây d ng ñ th mô t quan h i) Đ nh: L y n ñi m ( n ≥ 6 ) tương ng v i n ngư i (n là s nguyên) ñã ch n ra. ii) C nh: C nh ñ ñ n i gi a hai ñi m tương ng v i hai ngư i quen (hai s có ư c chung); c nh xanh ñ n i gi a hai ñi m tương ng v i hai ngư i không quen nhau (hai s nguyên t cùng nhau). Theo kh ng ñ nh 3.6, trong ñ th G tương ng có ít nh t n-4 tam giác cùng màu. N u tam giác màu ñ , thì ba ngư i tương ng quen nhau t ng ñôi m t (ba s tương ng có ư c chung t ng ñôi m t). N u tam giác màu xanh, thì ba ngư i tương ng không quen nhau t ng ñôi m t (ba s tương ng nguyên t cùng nhau). Gi i (ví d 3.16) V i n=5, thì các kh ng ñ nh phát bi u trong các ví d 3.14, 3.15 không còn ñúng n a. Th t v y, n u xu t phát t ñ th G ñ y ñ g m 5 ñ nh (tương ng v i 5 ñ i tư ng ñư c xét) v i các c nh ñư c tô b ng hai màu. C nh ñ (nét li n) bi u hi n quan h quen nhau (có ư c chung), c nh xanh (nét ñ t) bi u hi n quan h không quen nhau (nguyên t cùng nhau). Vì ñ th G không có tam giác cùng màu Hình 3.10 nên không có: - M t b ba ngư i nào tương ng v i các ñ nh mà ho c quen nhau t ng ñôi m t ho c không quen nhau t ng ñôi m t. - M t b ba s nào tương ng v i các ñ nh mà ho c có ư c chung t ng ñôi m t ho c nguyên t cùng nhau. Kh ng ñ nh 3.7 Trong ñ th ñ y ñ g m chín ñ nh K9 v i các c nh ñư c tô b ng m t trong hai màu xanh, ñ luôn tìm ñư c ñ th ñ y ñ K3 xanh ho c ñ th ñ y ñ K4 ñ (ho c ngư c l i n u ta ñ i hai màu cho nhau). Nh n xét Ta ñã bi t r ng R(3,4)=9 (M nh ñ 2.8), t c là 9 là s nh nh t có tính ch t (3,4)-Ramsey. Như v y, Kh ng ñ nh 3.7 hoàn toàn có th ch ng minh như M nh ñ 2.8.
18 Ví d 3.17 Trong phòng có 9 ngư i, trong ñó b t kì 3 ngư i nào cũng có hai ngư i quen nhau. Ch ng minh r ng có 4 ngư i t ng ñôi m t quen nhau. Gi i Ta cho tương ng m i ngư i v i m t ñ nh c a ñ th , hai ñ nh ñư c n i v i nhau b ng c nh màu ñ n u 2 ngư i quen nhau, hai ñ nh ñư c n i v i nhau b ng c nh xanh n u 2 ngư i không quen nhau. Vì b t kì 3 ngư i nào cũng có hai ngư i quen nhau nên trong ñ th G không ch a K3 xanh. Do ñó, theo k t qu c a kh ng ñ nh 3.7 ñ th G ch a t giác ñ . T ñó ta có ñi u ph i ch ng minh. Ví d 3.18 Ch ng minh r ng trong 9 s nguyên dương tuỳ ý, mà 3 s b t kỳ ñ u có 2 s nguyên t cùng nhau, luôn luôn tìm ñư c 4 s nguyên t cùng nhau (t ng c p nguyên t cùng nhau). Gi i Xây d ng ñ th G = (V, E). + Đ nh c a ñ th : Trên m t ph ng l y 9 ñi m tương ng v i 9 s nguyên dương tùy ý ñã ch n ra. Dùng các s ñã ch n ñ ghi tên các ñi m tương ng. + C nh c a ñ th : Dùng c nh ñ ñ n i gi a hai ñ nh tương ng v i hai s nguyên t cùng nhau, c nh xanh ñ n i gi a hai ñ nh tương ng v i hai s không nguyên t cùng nhau. Đ th G nh n ñư c mô t toàn b quan h ñư c cho trong bài toán và tho mãn ñi u ki n c a kh ng ñ nh 3.7, do ñó trong G ho c có ñ th ñ y ñ K3 ho c có K4 v i các c nh cùng màu. L i do trong 3 s b t kỳ ñ u có 2 s nguyên t cùng nhau nên trong G không có K3 màu xanh, t c là trong G luôn có K4 ñ . V y trong 9 s nguyên dương tuỳ ý, mà 3 s b t kỳ ñ u có 2 s nguyên t cùng nhau luôn luôn tìm ñư c 4 s nguyên t cùng nhau (t ng c p nguyên t cùng nhau). Bài toán ñư c ch ng minh. Kh ng ñ nh 3.8 Trong ñ th ñ y ñ g m mư i b n ñ nh K14 v i các c nh ñư c tô b ng m t trong hai màu xanh, ñ luôn tìm ñư c ñ th ñ y ñ K3 (mà các ñ nh c a nó n m trong t p ñ nh ñã cho) v i các
19 c nh ñư c tô cùng màu xanh, ho c ñ th ñ y ñ K5 (mà các ñ nh c a nó n m trong t p ñ nh ñã cho) v i các c nh ñư c tô cùng màu ñ (ho c ngư c l i n u ta ñ i màu cho nhau). Nh n xét Ta nh c l i r ng, R(3,5)=14(M nh ñ 2.9). Như v y 14 là s nguyên dương nh nh t làm cho bài toán trên ñư c th a mãn. Ph n ch ng minh c a m nh ñ này có th làm l i gi i cho kh ng ñ nh 3.8 . Ví d 3.19 Có 14 hùng bi n viên tham gia cu c thi SV 2011. Bi t r ng c 3 ngư i b t kỳ thì có ít nh t hai ngư i cùng chung m t ñ tài. Ch ng minh luôn có 5 ngư i b t kỳ (trong s 14 ngư i này) cùng chung m t ñ tài Gi i a) Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: - T p ñ nh V: L y 14 ñ nh không th ng hàng trên m t ph ng tương ng v i 14 hùng bi n viên. - T p c nh E: Hai ñ nh ñư c n i v i nhau b i m t c nh tô màu ñ n u hai hùng bi n viên có chung ñ tài, tô màu xanh n u hai hùng bi n viên không có chung ñ tài b) Gi i toán trên ñ th : Theo kh ng ñ nh 3.8 thì trong ñ th G(V, E) luôn t n t i K3 ho c K5 cùng màu. M t khác, vì 3 ngư i b t kỳ thì có ít nh t hai ngư i cùng chung m t ñ tài nên trong ñ th G không có K3 xanh. Suy ra trong G có K5 ñ . T ñó ta có l i gi i cho bài toán. Kh ng ñ nh 3.9 Cho ñ th ñ y ñ g m mư i tám ñ nh K18 v i các c nh ñư c tô b ng m t trong hai màu. Ch ng minh luôn tìm ñư c ñ th ñ y ñ K4 (mà các ñ nh c a nó n m trong t p ñ nh ñã cho) v i các c nh ñư c tô cùng màu. Ví d 3.20 Ch ng minh r ng trong mư i tám ngư i tùy ý ta có th ch n ra b n ngư i ho c ñôi m t quen bi t nhau, ho c ñôi m t không quen bi t nhau. Gi i a) Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: - T p ñ nh V: L y 18 ñ nh trên m t ph ng tương ng v i 18 ngư i
20 - T p c nh E: Hai ñ nh b t kì ñư c n i v i nhau b i m t c nh tô màu ñ n u hai ngư i tương ng quen bi t nhau, tô màu xanh n u hai ngư i tương ng không quen bi t nhau. b) Gi i toán trên ñ th : Theo k t lu n c a Kh ng ñ nh 3.9 thì trong ñ th G(V, E) luôn t n t i m t t giác mà các c nh và các ñư ng chéo cùng màu, t c là luôn ch n ñư c b n ngư i ho c ñôi m t quen bi t nhau ho c ñôi m t không quen bi t nhau. Kh ng ñ nh 3.10 Cho ñ th ñ y ñ có 16 ñ nh K16. T i m i ñ nh c a ñ th K16, trong s 15 c nh n i nó v i các ñ nh còn l i, ta tô màu ít nh t 11 c nh. Ch ng minh r ng v i m t ñ nh b t kỳ thu c 16 ñ nh ñã cho, luôn t n t i ba ñ nh khác n a ñ l p thành ñ th ñ y ñ K4 có các c nh ñ u ñư c tô màu. Ví d 3.21 Có 16 em thi ñ u bóng bàn. Theo l ch, m i em ph i thi ñ u v i m t b n khác m t tr n. Hi n nay m i em thi ñ u 11 tr n. Ch ng minh r ng, khi ñó luôn tìm ñư c 4 em mà m i em ñ u ñã ñ u v i 3 em còn l i. Gi i a) Ta xây d ng ñ th ñ y ñ G(V, E) mô t bài toán: - T p ñ nh V: L y 16 ñ nh trên m t ph ng tương ng v i 16 em - T p c nh E: Hai ñ nh b t kì ñư c n i v i nhau b i m t c nh tô màu ñ n u hai em ñã thi ñ u v i nhau b) Gi i toán trên ñ th : V i m t ñ nh b t kỳ thu c 16 ñ nh ñã cho, luôn t n t i ba ñ nh khác n a ñ l p thành ñ th ñ y ñ K4 có các c nh ñ u ñư c tô màu. T c là luôn tìm ñư c b n em mà m i em ñã ñ u v i ba em còn l i. Kh ng ñ nh 3.11 Cho ñ th ñ y ñ có (3n+1) ñ nh K3n+1. T i m i ñ nh c a ñ th K3n+1, trong s 3n c nh n i nó v i các ñ nh còn l i, ta tô màu ít nh t 2n+1 c nh. Ch ng minh r ng v i m t ñ nh b t kỳ thu c 3n+1 ñ nh ñã cho, luôn t n t i ba ñ nh khác n a ñ l p thành ñ th ñ y ñ K4 có các c nh ñ u ñư c tô màu. Ví d 3.22 Trong phòng có 100 ngư i mà m i ngư i quen ít nh t 67 trong s 99 ngư i còn l i. H i li u có x y ra hay không trư ng