Tóm tắt luận văn Bài toán tô màu và ứng dụng giải toán sơ cấp

Nội dung text: Tóm tắt luận văn Bài toán tô màu và ứng dụng giải toán sơ cấp

1. 1 BỘ GIÁO D ỤC VÀ ĐÀO T ẠO ĐẠI H ỌC ĐÀ N ẴNG NGUY ỄN TH Ị VI ỆT TH ẢO BÀI TỐN TƠ MÀU VÀ ỨNG DỤNG GI ẢI TỐN SƠ CẤP Chuyên ngành: PH ƯƠ NG PHÁP TỐ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. 2 Cơng trình được hồ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. 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 tốn h ọc ứng dụng. Sử d ụng bài tốn tơ màu để gi ải tố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 tố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 tố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 tố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 tốn tơ màu đồ th ị nĩi riêng để gi ải các bài tốn khơng m ẫu m ực, các bài tốn th ường g ặp trong th ực t ế và m ột vài bài tốn trong các kì thi Tố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 tố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 tố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 tốn tơ màu và ứng d ụng gi ải tốn s ơ c ấp.
4. 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 tố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 tốn v ề đường đi 1.2.3 M ột s ố định lí 1.3 ĐỒ TH Ị PH ẲNG 1.3.1 Bài tố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 TỐ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. 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 đủ K n 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 K 3 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 đủ K n 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 = K n 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 TỐN TƠ MÀU ĐỈNH i) Lập danh sách các đỉnh đồ th ị. ’ [ ] E := v1, v 2 , , v n ≥ ≥ ≥ theo th ứ t ự b ậc gi ảm d ần: dv()1 dv () 2 dv ()n . Đặ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. 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 tốn s ắc s ố c ạnh v ề bài tố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 đủ K m,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) =∆( K) =− n 1 n n ii) N ếu n l ẻ thì χ '(K) =∆( K) += 1 n n 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 K n v ới m ỗi c ạnh được tơ bằng m ột trong hai màu xanh ho ặc đỏ thì (a) K n ch ứa ho ặc K i đỏ ho ặc K j xanh và (b) K n ch ứa ho ặc K j đỏ ho ặc K i 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. 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. 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 tố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 ố lồi s ẽ ăn th ịt lồi khác n ếu nh ốt chung chu ồng. Bảng sau đây cho bi ết nh ững lồ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 tốn tơ màu nh ư sau: M ỗi đỉnh c ủa đồ th ị là m ột lồi thú, hai đỉnh được n ối với nhau b ằng m ột c ạnh n ếu hai lồi thú khơng th ể nh ốt chung một chu ồng. Áp d ụng thu ật tố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. 9 Nh ư v ậy, ta thu được l ời gi ải cho bài tố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 tốn 3.1.2 Phân chia t ần s ố Bài tố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 x 1, x 2, x m gi ảng d ạy n l ớp y 1, y 2, y n, m ỗi l ớp được d ạy trong p i 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 tốn 3.1.4 Bài tốn n ữ sinh Lucas . Bài tốn 3.1.5 Tơ màu b ản đồ. Bài tố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 tố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 tố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 tố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. 10 Bài tố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 TỐ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 tố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 tố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à A 1, A 2, A 3, A 2n+1 . Xét G(V, E) là đồ th ị màu đầy đủ v ới t ập đỉnh là A 1, A 2, A 3, A2n+1 .
11. 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à A i. Khi đĩ, A và A i 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 tố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 tố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 tố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. 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 tố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 tố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 tố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. 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, a 2=5, a n+1 = (n+1)a n +1 u2 = 3, u 3 = 6, , u n+1 = (u n-1)n +2. Ta cĩ các kh ẳng định sau: Kh ẳng định 3.4 a) Đồ th ị đầy đủ v ới a n+1 đỉnh mà các c ạnh được tơ b ằng n màu, luơn luơn cĩ đồ th ị con đầy đủ K 3 v ới các c ạnh cùng màu. b) Đồ th ị đầy đủ v ới u n+1 (n ≥1) đỉnh mà các c ạnh được tơ bằng n màu, luơn luơn cĩ đồ th ị con đầy đủ K 3 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 tố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 tố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. 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 tố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 tố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 K 6 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 K 3 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 đủ K n được tơ b ởi m ột trong hai màu (ch ẳng h ạn xanh ho ặc đỏ) thì K n ch ứa K 3 xanh ho ặc đỏ. Với m ọi s ố nguyên d ươ ng m>n thì đồ th ị K m c ũng cĩ tính ch ất
15. 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 tố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 tố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 hồn tồ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ĩ u n+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. 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 tố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 tố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. 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 K 9 v ới các c ạnh được tơ bằng m ột trong hai màu xanh, đỏ luơn tìm được đồ th ị đầy đủ K 3 xanh ho ặc đồ th ị đầy đủ K 4 đỏ (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 hồn tồn cĩ th ể ch ứng minh nh ư ở M ệnh đề 2.8.
18. 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 K 3 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 ả tồn b ộ quan h ệ được cho trong bài tốn và tho ả mãn điều ki ện c ủa kh ẳng định 3.7 , do đĩ trong G ho ặc cĩ đồ th ị đầy đủ K 3 ho ặc cĩ K 4 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ĩ K 3 màu xanh, t ức là trong G luơn cĩ K 4 đỏ. 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 tốn được ch ứng minh. Kh ẳng định 3.8 Trong đồ th ị đầy đủ g ồm m ười bốn đỉnh K 14 v ới các c ạnh được tơ b ằng m ột trong hai màu xanh, đỏ luơn tìm được đồ th ị đầy đủ K 3 (mà các đỉnh c ủa nĩ n ằm trong t ập đỉnh đã cho) v ới các
19. 19 cạnh được tơ cùng màu xanh, ho ặc đồ th ị đầy đủ K 5 (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 tố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 tố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 tốn trên đồ th ị: Theo kh ẳng định 3.8 thì trong đồ th ị G(V, E) luơn t ồn t ại K 3 ho ặc K 5 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ĩ K 3 xanh. Suy ra trong G cĩ K 5 đỏ. T ừ đĩ ta cĩ l ời gi ải cho bài tốn. Kh ẳng định 3.9 Cho đồ th ị đầy đủ g ồm m ười tám đỉnh K 18 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 đủ K 4 (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 tốn: - T ập đỉnh V: L ấy 18 đỉnh trên m ặt ph ẳng t ươ ng ứng v ới 18 ng ười
20. 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 tố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 K 16 . 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 đủ K 4 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 tố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 tố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 K 3n+1 . T ại m ỗi đỉnh c ủa đồ th ị K 3n+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 đủ K 4 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
21. 21 hợp b ất k ỳ 4 ng ười nào đĩ trong phịng c ũng cĩ 2 ng ười quen nhau? Gi ải Câu tr ả l ời là cĩ. Ta cĩ th ể th ấy được điều này khi áp Kh ẳng định 3.11 với n=33. Kh ẳng định 3.12 Cho đồ th ị đầy đủ cĩ 16 đỉnh K16 . T ại m ỗi đỉnh c ủa đồ th ị K 16 , trong s ố 15 c ạnh n ối nĩ v ới các đỉnh cịn l ại, ta tơ màu ít nh ất 13 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 n ăm đỉnh khác n ữa để l ập thành đồ th ị đầy đủ K 6 cĩ các cạnh đều được tơ màu. Ví d ụ 3.23 Trong m ột thành ph ố cĩ 16 qu ận và m ỗi qu ận cĩ đường giao thơng n ối v ới ít nh ất 13 qu ận khác. Ch ứng minh r ằng luơn t ồn t ại 6 qu ận đơi m ột cĩ đường giao thơng n ối chúng v ới nhau. Gi ải Xây d ựng đồ th ị G = (V, E) mơ t ả các đường giao thơng n ối các qu ận v ới nhau. Đỉnh đồ th ị là các qu ận. C ạnh c ủa đồ th ị: Hai đỉnh được n ối v ới nhau b ởi m ột c ạnh n ếu nh ư hai qu ận cĩ 1 đường giao thơng n ối chúng v ới nhau. Theo k ết qu ả c ủa Kh ẳng định 3.12 ta suy ra đồ th ị G = (V, E) luơn t ồn t ại đồ th ị con K 6. V ậy luơn tồn t ại 6 qu ận đơi m ột cĩ đường giao thơng n ối chúng v ới nhau. Kh ẳng định 3.13 Ch ứng minh r ằng trong đồ th ị G(X, E) v ới ít nh ất kn+1 đỉnh, m ỗi đỉnh cĩ b ậc khơng nh ỏ h ơn (k-1)n+1 luơn t ồn t ại đồ th ị con đầy đủ g ồm k+1 đỉnh. 3.3.2 M ột s ố bài tốn áp d ụng khác Ví d ụ 3.24 Trên m ột tàu du l ịch, ng ười ta nh ận th ấy c ứ 10 ng ười b ất k ỳ thì cĩ ít nh ất 3 ng ười cùng qu ốc t ịch. H ỏi cĩ nhi ều nh ất bao nhiêu qu ốc gia cĩ khách du l ịch đi trên tàu. Gi ải : Xây d ựng đồ th ị G(V, E) nh ư sau: - T ập đỉnh V: L ấy n điểm trên m ặt ph ẳng ho ặc trong khơng gian t ươ ng ứng v ới n khách du l ịch. Dùng mã s ố vé tàu c ủa khách để kí hi ệu các đỉnh.
22. 22 - T ập c ạnh E: Hai đỉnh được n ối v ới nhau b ằng m ột c ạnh và được tơ màu khi hai hành khách t ươ ng ứng cĩ cùng qu ốc t ịch (v ới mỗi qu ốc t ịch ta tơ m ột màu) Gi ải tốn trên đồ th ị: Từ gi ả thi ết ta cĩ đồ th ị G(V, E) khơng th ể phân tích thành quá 5 đồ th ị con đầy đủ v ới các c ạnh khác màu là G 1, G 2, G 3, G 4, G5. Các đồ th ị con đầy đủ này cĩ ít nh ất 3 đỉnh. L ấy t ừ m ỗi đồ th ị con 2 đỉnh và các c ạnh n ối chúng, ta được đồ th ị con c ủa G(V, E) gồm 10 đỉnh nh ưng khơng cĩ chu trình tam giác cùng màu. Điều này mâu thu ẫn v ới gi ả thi ết c ứ 10 đỉnh thì cĩ 3 đỉnh t ạo thành tam giác cùng màu. Xét tr ường h ợp G (V, E) phân tích được thành 4 đồ th ị con đầy đủ v ới các c ạnh cùng màu. Khi đĩ, n ếu ta l ấy 10 đỉnh b ất kì cùng các c ạnh n ối các đỉnh đĩ (n ếu cĩ) thì ít nh ất cĩ 3 đỉnh được ch ọn t ừ cùng m ột đồ th ị con. Suy ra cĩ tam giác v ới các c ạnh cùng màu. V ậy nhi ều nh ất cĩ 4 qu ốc gia cĩ khách du l ịch trên tàu. Ví d ụ 3.25 Một nhà tri ển lãm cĩ n 2 phịng tam giác đều. Hai phịng tri ển lãm được g ọi là hai phịng láng gi ềng n ếu chúng cĩ c ạnh chung. Từ m ỗi phịng đều cĩ c ửa đi sang phịng láng gi ềng c ủa nĩ. M ột khách du l ịch mu ốn đi xem càng nhi ều càng t ốt s ố phịng tri ển lãm với điều ki ện m ỗi phịng ch ỉ đi qua đúng m ột l ần. H ỏi anh ta cĩ th ể đi t ối đa bao nhiêu phịng. Gi ải: Tơ các phịng tri ển lãm thành các ơ hai màu đen tr ắng xen k ẽ nh ư Hình 3.16 . Hình 3.16 Hình 3.17
23. 23 n( n + 1) Với n ≥2, s ố phịng cĩ màu tr ắng s ẽ là 1+ 2 ++ 3 +n = . 2 n( n − 1) Số phịng đen s ẽ là: 1+ 2 ++ 3 +n −= 1 . 2 Nh ư v ậy, s ố ơ đen nh ỏ h ơn s ố ơ tr ắng là nn(+ 1) nn ( − 1) − =n ≥ 2 ơ. 2 2 Trong quá trình đi xem, khách du l ịch luơn ph ải đi t ừ phịng tr ắng sang phịng đen ho ặc ng ược l ại. Gi ả s ử cĩ th ể đi tham quan tất c ả các phịng sao cho m ỗi phịng đi qua đúng m ột l ần. Khi đĩ, số phịng đen ch ỉ ít h ơn s ố phịng tr ắng m ột phịng. Mâu thu ẫn v ới tính tốn trên. Nh ư v ậy, khơng th ể đi tham quan t ất c ả các phịng được. Do m ỗi phịng ch ỉ đi qua đúng m ột l ần mà ph ải đi xen k ẽ các phịng đen tr ắng liên ti ếp nên s ố phịng màu tr ắng đi qua ch ỉ hơn s ố phịng màu đen m ột phịng. Nh ư v ậy, n ếu đi qua t ất c ả phịng đen thì t ối đa t ổng s ố phịng cĩ th ể tham quan là: nn(− 1) nn ( − 1) + +=−−1n2 n 1 phịng. Cĩ th ể th ực hi ện điều này theo 2 2 đường đi nh ư Hình 3.17 . Ví d ụ 3.26 Cho 9 điểm trong khơng gian, trong đĩ khơng cĩ 4 điểm nào nằm trong cùng m ột m ặt ph ẳng. T ất c ả nh ững điểm này được n ối với nhau t ừng c ặp b ằng đoạn th ẳng. M ỗi đoạn th ẳng được tơ màu xanh ho ặc đỏ ho ặc khơng tơ màu. Tìm giá tr ị nh ỏ nh ất c ủa n sao cho v ới m ọi cách tơ màu n đoạn th ẳng tùy ý ta đều tìm được m ột tam giác cĩ các c ạnh cùng màu (Thi h ọc sinh gi ỏi qu ốc t ế n ăm 1992) Ví d ụ 3.27 Ch ứng minh ta cĩ th ể tơ màu các c ạnh c ủa đồ th ị liên thơng G b ởi hai màu xanh, đỏ sao cho s ố c ạnh đỏ và s ố c ạnh xanh xu ất phát t ại m ỗi đỉnh c ủa đồ th ị luơn b ằng nhau khi và ch ỉ khi G cĩ s ố ch ẵn c ạnh và b ậc c ủa m ỗi đỉnh c ủa G là s ố ch ẵn.
24. 24 3.4 TƠ MÀU ĐIỂM TRONG M ẶT PH ẲNG VÀ TRONG KHƠNG GIAN Bài tốn 3.4.1 Các điểm trong m ặt ph ẳng được tơ b ởi m ột trong hai màu xanh ho ặc đỏ. Ch ứng minh r ằng, v ới m ột kho ảng cách d cho tr ước, luơn t ồn t ại hai điểm cùng màu mà kho ảng cách gi ữa chúng bằng d. Bài tốn 3.4.2 Các điểm c ủa m ặt ph ẳng được tơ b ởi ba màu đỏ, xanh, vàng. Ch ứng minh r ằng , v ới m ột kho ảng cách d cho tr ước, luơn t ồn t ại hai điểm cùng màu mà kho ảng cách gi ữa chúng b ằng d. Bài tốn 3.4.3 Mỗi điểm trong đường th ẳng được tơ b ởi m ột trong hai màu xanh ho ặc đỏ. Ch ứng minh luơn t ồn t ại ba điểm cùng màu, trong đĩ cĩ m ột điểm là trung điểm c ủa đoạn th ẳng n ối hai điểm kia. Bài tốn 3.4.4 Các điểm c ủa m ặt ph ẳng được tơ b ởi m ột trong hai màu xanh, đỏ. Ch ứng minh r ằng luơn tìm được m ột tam giác đều v ới ba đỉnh cùng màu. Bài tốn 3.4.5 Mỗi điểm trong m ặt ph ẳng được tơ b ởi m ột trong hai màu xanh ho ặc đỏ. Ch ứng minh luơn t ồn t ại m ột hình ch ữ nh ật cĩ b ốn đỉnh cùng màu. Bài tốn 3.4.6 Mỗi điểm c ủa m ặt ph ẳng được tơ b ởi m ột trong n màu, v ới n là s ố nguyên d ươ ng cho tr ước. Ch ứng minh r ằng t ồn t ại m ột hình ch ữ nh ật v ới các đỉnh được tơ cùng màu.
25. 25 KẾT LU ẬN VÀ KI ẾN NGH Ị Lu ận v ăn đã nêu lên được m ột s ố ki ến th ức v ề b ộ mơn lý thuy ết đồ th ị nĩi chung và bài tốn tơ màu đồ th ị nĩi riêng qua vi ệc xây d ựng m ột cách cĩ h ệ th ống m ột vài k ết qu ả c ủa bài tốn tơ màu đồ th ị và các ví d ụ minh h ọa cho v ấn đề này. Qua đĩ, ng ười đọc cĩ th ể nh ận ra tính ưu vi ệt c ủa ph ươ ng pháp này trong gi ải tốn, t ừ đĩ cĩ th ể giúp ích ph ần nào cho nh ững ai quan tâm đến v ấn đề này, đặc bi ệt là nh ững h ọc sinh ở các l ớp chuyên. Một s ố k ết qu ả trong lu ận v ăn d ựa vào định lý Ramsey. Tuy nhiên, lu ận v ăn ch ỉ m ới d ừng l ại ở m ột s ố tr ường h ợp điển hình của định lý. Trong th ời gian t ới, h ướng phát tri ển c ủa lu ận v ăn là ch ứng minh được thêm nhi ều tr ường h ợp khác c ủa định lý này và xây d ựng thêm các l ớp bài tốn cĩ th ể gi ải được b ằng cách áp dụng các k ết qu ả trên bên c ạnh cách gi ải truy ền th ống, t ừ đĩ, ng ười đọc cĩ th ể so sánh để nh ận ra cái hay, cái thú v ị c ủa bài tốn tơ màu. Đĩ c ũng chính là mong mu ốn c ủa tác gi ả lu ận v ăn.