Về định lý Ramsey, các số Ramsey 2 màu và một số ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

63
lượt xem 5
download

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

Bài viết này nhằm mục đích tổng quan định lý Ramsey, các số Ramsey và một số vấn đề liên quan; Trên cơ sở đó xem xét ứng dụng của chúng vào trò chơi Ramsey và việc phát biểu một số bài toán sơ cấp hay và khó.

Chủ đề:

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

Lưu

Nội dung Text: Về định lý Ramsey, các số Ramsey 2 màu và một số ứng dụng

VỀ ĐỊNH LÝ RAMSEY, CÁC SỐ RAMSEY 2 MÀU VÀ MỘT SỐ ỨNG DỤNG NGUYỄN THÀNH THÁI Khoa Toán học 1 GIỚI THIỆU Định lý Ramsey và các vấn đề liên quan đã đặt ra rất nhiều vấn đề thú vị và phần lớn trong số đó vẫn là những vấn đề mở. Bên cạnh đó, định lý Ramsey và các vấn đề liên quan cũng có rất nhiều ứng dụng vào các lĩnh vực khác. Bài viết này nhằm mục đích tổng quan định lý Ramsey, các số Ramsey và một số vấn đề liên quan; trên cơ sở đó xem xét ứng dụng của chúng vào trò chơi Ramsey và việc phát biểu một số bài toán sơ cấp hay và khó. 2 MỘT SỐ KHÁI NIỆM VỀ ĐỒ THỊ 1. Cho tập hợp V và E là tập hợp bao gồm các tập con 2 phần tử của V . Khi đó, ta gọi cặp G = (V, E) là đồ thị G với tập đỉnh V và tập cạnh E. Đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh đều được nối bởi một cạnh, kí hiệu Kn . 2. Đồ thị H được gọi là đồ thị con của đồ thị G nếu V (H) ⊆ V (G) và E(H) ⊆ E(G). 3. Đồ thị con H = (V (H), E(H)) của G với V (H) = {x1 , x2 , . . . xn } và E(H) = {x1 x2 , x2 x3 . . . xn−1 xn } được gọi là đường đi nối x1 với xn đi qua x2 , x3 , . . . , xn−1 và có độ dài n, kí hiệu P = x1 x2 . . . xn . Nếu tập E(H) có thêm cạnh xn x1 thì ta nói H là n−chu trình đi qua x1 , x2 , . . . , xn , kí hiệu C = x1 x2 . . . xn x1 . Đồ thị chu trình là đồ thị mà trong đó có chu trình đi qua tất cả các đỉnh và ngoài ra không có cạnh nào khác, kí hiệu Cn . 4. Siêu đồ thị G = (V (H), E(H)) có tập đỉnh V (H) như đồ thị thông thường và tập cạnh E(H) trong đó mỗi cạnh e ∈ E(H) là một tập con bất kì của V (H) (hay mỗi cạnh là một đường đi). Nếu tập cạnh của siêu đồ thị G chỉ gồm những đường đi độ dài n thì ta nói G là siêu đồ thị n-đều. Siêu đồ thị được gọi là n-đều đầy đủ nếu tập cạnh của nó chứa tất cả các đường đi độ dài n. Để biết thêm về lý thuyết đồ thị người đọc có thể tìm hiểu ở [1]. Kỷ yếu Hội nghị Khoa học Sinh viên năm học 2013-2014 Trường Đại học Sư phạm Huế, tháng 12/2013: tr. 37-46
38 NGUYỄN THÀNH THÁI 3 ĐỊNH LÝ RAMSEY VÀ CÁC SỐ RAMSEY Khi giảng về lý thuyết Ramsey, Paul Erdos, một nhà toán học lỗi lạc và là người đi đầu trong việc đề xuất những vấn đề về lý thuyết Ramsey, đã giới thiệu hai bài toán. Bài toán thứ nhất được mang tên là "Party problem". Nội dung bài toán là trong 6 người cùng đi dự tiệc, liệu có thể tìm ra 3 người quen biết lẫn nhau (đôi một quen biết) hoặc 3 người không quen biết lẫn nhau hay không? Bài toán được phát biểu tương đương là với một cách tô 2 màu các cạnh đồ thị đầy đủ 6 đỉnh, liệu ta có thể tìm ra một tam giác cùng màu? Và xa hơn, liệu rằng với chỉ 5 người dự tiệc, ta có thể làm được điều tương tự không? Lời giải của những câu hỏi trên sẽ đề cập tới số đỉnh nhỏ nhất của một đồ thị đầy đủ mà với một cách tô 2 màu bất kì luôn tìm được một tam giác cùng màu, gọi là số Ramsey, kí hiệu R(3, 3). Định lý Ramsey khẳng định rằng với mọi cách tô màu một đồ thị (trong suốt bài viết này, khi nói đến tô màu đồ thị ta hiểu là tô màu các cạnh đồ thị) đầy đủ bậc đủ lớn, ta luôn có thể tìm được một đồ thị con đầy đủ đồng màu. Với số màu tô là 2, định lý Ramsey phát biểu rằng với bất kì 2 số nguyên dương (m, n), tồn tại số nguyên dương nhỏ nhất R(m, n) sao cho với mọi cách tô màu các cạnh của đồ thị đầy đủ có R(m, n) đỉnh bởi 2 màu xanh và đỏ, thì luôn tồn tại một đồ thị con đầy đủ với m đỉnh màu xanh hoặc một đồ thị con đầy đủ với n đỉnh màu đỏ. Định lý 3.1. Với 2 số tự nhiên m, n > 1 thì số R(m, n) tồn tại hữu hạn. Định lý Ramsey cũng đúng trong trường hợp mở rộng cho nhiều màu. Với các số tự nhiên r > 2 và n1 , n2 , . . . , nr > 1, số Ramsey R(n1 , n2 , . . . , nr ) là số tự nhiên n nhỏ nhất sao cho với mọi cách tô Kn (đồ thị đầy đủ bậc n) bởi r màu (được đánh số [r] = {1, 2, . . . , r}), luôn tồn tại chỉ số m sao cho trong Kn có đồ thị con Kim đồng màu m. Định lý 3.2. Với mọi n1 , n2 , . . . , nr > 1, R(n1 , n2 , . . . , nr ) tồn tại hữu hạn. Thực chất 2 định lý trên chỉ là một trường hợp đặc biệt của định lý Ramsey cho siêu đồ thị. Hai định lý dưới đây được Frank Plumpton Ramsey đưa ra trong bài báo "On a problem of formal logic" trên Proceedings London Mathematical Society năm 1928 (được đăng năm 1930) dưới ngôn ngữ tập hợp, trong đó định lý cho siêu đồ thị vô hạn là tổng quát nhất. Định lý 3.3. Cho các số tự nhiên n1 , n2 , . . . , nr , k > 1. Khi đó, tồn tại số tự nhiên n thỏa mãn với mọi cách tô màu một đồ thị k-đều đầy đủ với n đỉnh bằng r màu được đánh số [r], luôn tồn tại chỉ số i sao cho siêu đồ thị con k-đều đầy đủ với ni đỉnh là đồng màu i. Số n nhỏ nhất trong định lý trên gọi là số Ramsey cho siêu đồ thị, kí hiệu Rk (n1 , n2 , . . . , nr )
VỀ ĐỊNH LÝ RAMSEY, CÁC SỐ RAMSEY 2 MÀU... 39 Định lý 3.4. Cho số tự nhiên n > 1 và G là một siêu đồ thị n-đều đầy đủ với số đỉnh vô hạn đếm được. Khi đó, nếu tô màu G bằng hữu hạn màu thì tồn tại một đồ thị con n-đều đầy đủ với số đỉnh vô hạn đồng màu. Bài toán thứ hai Erdos đặt ra là giả sử chúng ta phải trả lời chính xác giá trị R(5, 5) cho người ngoài hành tinh hoặc họ sẽ hủy diệt trái đất thì khi đó chúng ta nên làm gì? Và nếu thay R(5, 5) bằng R(6, 6) thì sao? Với R(5, 5), Erdos nói rằng tất cả các nhà toán học cùng với máy tính trên trái đất cần làm việc cật lực để tìm ra lời giải. Còn với R(6, 6), Erdos khuyên rằng ta nên giành thời gian để nghĩ cách hủy diệt người ngoài hành tinh trước khi quá muộn! Bởi thực tế người ta đã chỉ ra rằng 102 ≤ R(6, 6) ≤ 165. Việc nghiên cứu tất cả những đồ thị tô màu với số đỉnh từ 102 đến 165 hầu như là điều không tưởng. Bằng một phép tính đơn giản, số các đồ thị 102 đỉnh cần nghiên cứu là 2102 - một số có hơn 30 chữ số! Những nỗ lực không biết mệt mỏi của các nhà toán học trong suốt gần một thế kỉ qua chỉ mang lại được hiếm hoi các kết quả về giá trị của số Ramsey (xem [2], [7]) . 1. R(m, n) = R(n, m) với mọi số nguyên m, n > 1. 2. R(2, n) = n với mọi số nguyên n > 1. 3. R(3, 3) = 6, R(3, 4) = 9, R(3, 5) = 14, R(3, 6) = 18, R(4, 4) = 18. 4. R(4, 5) = 25, R(3, 7) = 23, R(3, 8) = 28, R(3, 9) = 36. 5. R(3, 3, 3) = 17 và R3 (4, 4) = 13. Bản thân những số Ramsey ở mục 4 phía trên cũng được tìm ra nhờ sự hỗ trợ của máy tính. Sự khó khăn quá lớn trong việc tìm ra giá trị của các số Ramsey cổ điển khiến một số nhà toán học chuyển sang nghiên cứu các số Ramsey cho các loại đồ thị đặc biệt khác (thay đổi điều kiện phải tìm Km đồng màu thành tìm các đồ thị G đồng màu) và đã đem lại nhiều kết quả đáng chú ý (xem [7]). Những nhà toán học tiếp tục với các số Ramsey cổ điển chuyển sang nghiên cứu về các chặn trên và chặn dưới của các số Ramsey (trong trường hợp tổng quát và cụ thể) để tiến tới tìm ra giá trị chính xác của chúng. n2n/2 Định lý 3.5. (Erdos) Với mọi số nguyên n > 1, √ ≤ R(n, n) . e 2 Dạng chung của chặn √ dưới Erdos là với hằng số c nào đó R(n, n) ≥ cn2n/2 . Hằng số tốt nhất hiện nay là e2 . Theo chúng tôi được biết thì đây cũng là dạng chặn dưới tốt nhất cho đến nay (xem [7],[6],[3]) . c4k Định lý 3.6. R(n, n) ≤ √ với hằng số c nào đó. k
40 NGUYỄN THÀNH THÁI √ 1 1 Từ định lý 1.12 và 1.13 ta có 2 ≤ lim inf R(n, n) n ≤ lim sup R(n, n) n ≤ 4. Kết quả chặn trên tốt nhất hiện này được coi là của David Conlon (xem [8]). ! log(n−1) −c log log(n−1) 2n − 2 R(n, n) ≤ (n − 1) n−1 Ngoài chặn trên và chặn dưới, việc nghiên cứu các chặn đệ quy (xem [6], [7]) và cách xây dựng các loại đồ thị phản ví dụ (đồ thị tồn tại cách tô màu mà không tìm được đồ thị con đồng màu) cũng đóng vai trò rất quan trọng. Định lý sau được Turan phát biểu năm 1941 (xem [3]) như là một ví dụ đầu tiên trong việc xây dựng các loại đồ thị nói trên. Định lý 3.7. (Turan) Một đồ thị đầy đủ bậc n được tô bởi 2 màu xanh đỏ nếu không chứa (r − 2)n2 đồ thị con Kr màu đỏ thì có số cạnh màu đỏ không vượt quá . 2(r − 1) 2 Với r = 3, số cạnh xanh không quá b n4 c trong đó bxc là số nguyên lớn nhất không vượt quá x. Các đồ thị phản ví dụ và chặn liên quan đến R(3, n) được nghiên cứu rất nhiều hiện nay (xem [3]). 4 ỨNG DỤNG CỦA ĐỊNH LÝ RAMSEY 4.1 Trò chơi Ramsey Trò chơi Ramsey được phân chia thành 3 loại: trò chơi Ramsey, trò chơi Sim và trò chơi Pekec. 3 loại trò chơi này đều bắt đầu với một đồ thị Kn , một đồ thị con Km cùng 2 người chơi (hoặc nhiều người chơi ở trò chơi Ramsey). Mỗi người chơi với một màu của riêng mình (các màu đôi một không trùng nhau) lần lượt tô màu các cạnh chưa được tô của Kn với điều kiện mỗi lượt chỉ được tô đúng một cạnh. Ở trò chơi Ramsey, mỗi người chơi sẽ cố gắng tạo ra một đồ thị con Km đồng màu của mình. Ở trò chơi Sim, mỗi người chơi đều cố gắng buộc đối thủ phải tạo ra Km đồng màu trước. Và ở trò chơi Pekec, một người sẽ cố gắng tạo ra Km đồng màu và người còn lại chỉ cố gắng ngăn chặn không cho người kia đạt được mục đích. Trò chơi kết thúc khi có một người thắng hoặc không còn nước đi nào. Một số loại biến thể khác của các dạng trò chơi này là thay đổi Km bằng một đồ thị G bất kì (xét đến đẳng cấu), 2 người cố gắng tạo ra đồ thị đồng màu còn 1 người cố gắng ngăn chặn điều đó, mỗi người chơi cố gắng tạo ra một dạng đồ thị khác nhau (quy định trước và xét đẳng cấu), trò chơi On-line Ramsey . . .. Một số kết quả tổng quát đối với các trò chơi là (xem [4], [5]) 1. Trong trò chơi Ramsey, nếu tồn tại một chiến lược để thắng thì người chơi thứ nhất sẽ giành chiến thắng.
VỀ ĐỊNH LÝ RAMSEY, CÁC SỐ RAMSEY 2 MÀU... 41 2. Trong trò chơi Pekec, nếu n ≥ 2R(m, m) thì người chơi thứ nhất (cố gắng tạo ra Km đồng màu) sẽ giành chiến thắng. Ngoài ra, ở trò chơi Sim, người ta chỉ ra với n = 6 thì người thứ hai sẽ thắng (xem [4]) .Tuy nhiên, phát biểu chiến lược chơi cụ thể để thắng trong các trò chơi này vẫn là bài toán mở. Sau đây, chúng ta xem xét 2 trường hợp với đồ thị cần tạo đơn giản, khi đó trò chơi Ramsey và Pekec là khá giống nhau. 1/ Đồ thị cần tạo ra là K3 . Trong trường hợp này, định lý Ramsey chỉ ra một đồ thị đầy đủ bậc 6 (hoặc bậc cao hơn) sẽ đảm bảo trò chơi kết thúc với một người thắng. Tuy nhiên, ta có thể chỉ ra rằng, nếu chơi với đồ thị K5 thì người thứ nhất vẫn thắng với chiến lược thích hợp. Người chơi thứ nhất cần tô màu các cạnh như Hình 1, nước đi tiếp theo sau Hình 1 là của người thứ 2. Hình 1: Người thứ nhất tô màu các cạnh liền nét Rõ ràng sau khi tô màu được các cạnh với dạng như Hình 1, người thứ nhất sẽ chiến thắng ở lượt đi kế tiếp cho dù người chơi thứ 2 chơi tiếp như thế nào. Với trường hợp đồ thị K5 hoặc cao hơn, sau đúng 3 lượt đi, người chơi thứ nhất có thể tô màu các cạnh như trên. Thật vậy, xét các đỉnh bắt nguồn từ 1 đỉnh bất kì, có ít nhất là 4 cạnh như vậy. Người chơi thứ nhất lần lượt tô màu các cạnh này. Trước khi người thứ nhất tô màu 3 cạnh trong số các cạnh này, người chơi thứ 2 không thể tạo ra được K3 đồng màu (ở trò chơi Ramsey) bởi ở lượt chơi thứ hai, người thứ hai cần phải chặn không cho người thứ nhất tạo K3 . Và cũng vì vậy, trường hợp ở Hình 2 cũng không thể xảy ra, nước đi tiếp theo Hình 2 là của người thứ nhất. Như vậy, sau nhiều nhất 4 lượt chơi (có thể là 3 nếu người thứ hai chơi sai), người thứ nhất sẽ thắng. Điều này được đảm bảo bởi vì sau 4 lượt, số cạnh được tô màu là 7 trong
42 NGUYỄN THÀNH THÁI Hình 2: Cách tô màu sai của người thứ hai khi số cạnh có thể tô ít nhất là 10 (ứng với K5 ). 2/ Đồ thị cần tạo ra là C4 . Định lý Ramsey chỉ ra với đồ thị K6 hoặc cao hơn sẽ đảm bảo chiến thắng cho một người khi trò chơi kết thúc. Chiến lược của người chơi thứ nhất sẽ là tô màu để tạo ra các đỉnh bậc 2 với màu của mình (để tạo nên một chu trình). Đầu tiên, ta thấy rằng, nếu người thứ nhất tạo được dạng đồ thị như sau, nước đi tiếp theo là của người thứ 2, thì ngay lượt chơi tiếp theo, người thứ nhất sẽ thắng. Dĩ nhiên, trong các dạng hình trên, nếu có thêm cạnh được tô màu bởi người thứ nhất thì việc chiến thắng càng dễ dàng hơn. Để tạo được dạng hình như trên, trước hết người thứ nhất cần tạo ra tam giác đồng màu. Đối với đồ thị K6 hoặc bậc cao hơn, việc này diễn ra trong vòng tối đa 4 lượt chơi. Thật vậy, sau 2 lượt chơi đầu tiên, có 2 trường hợp xảy ra 1. Người chơi thứ nhất tô màu 2 cạnh ij và jk mà cạnh ki chưa được người thứ hai tô. Trong trường hợp này, người thứ nhất tiếp tục tô màu cạnh kl để buộc người thứ hai phải tô màu cạnh li trong nước đi tiếp theo (lượt thứ 3 của người thứ hai). Điều này giúp người thứ nhất chủ động trong các nước đi kế tiếp của mình (nếu không ở lượt đi thứ 4 người thứ nhất có thể phải chặn việc tạo C4 của người thứ hai. Trong lượt đi thứ 4, người chơi thứ nhất chỉ việc tô màu cạnh ki. 2. Người chơi thứ nhất tô màu 2 cạnh ij và jk mà cạnh ki đã được người thứ hai tô (ở lượt chơi thứ 2 của mình). Khi đó người chơi thứ nhất tiếp tục tô màu cạnh jl. Như vậy, bất kể nước đi tiếp theo của người thứ hai như thế nào, người thứ nhất cũng tạo được tam giác đồng màu.
VỀ ĐỊNH LÝ RAMSEY, CÁC SỐ RAMSEY 2 MÀU... 43 Hình 3: Lượt chơi trước khi thắng Sau khi tạo được tam giác đồng màu ijki, nếu có 1 đỉnh l ngoài i, j, k mà cạnh nối nó với 3 đỉnh i, j, k nào đó chưa được người thứ 2 tô, người thứ nhất tô màu một trong các cạnh il, jl, kl và như vậy sẽ tạo được dạng hình 4 (trường hợp ở dưới bên phải). Do đó, trường hợp này, sau tối đa 6 lượt chơi, người thứ nhất sẽ thắng. Điều này được đảm bảo vì chỉ có tối đa 11 cạnh được tô trong số ít nhất 15 cạnh có thể tô. Trường hợp ngược lại chỉ diễn ra ở đồ thị K6 nghĩa là người thứ nhất tạo được tam giác ijk và người thứ hai đã tô màu các cạnh ii0 , jj 0 , kk 0 . Lúc này người thứ nhất chỉ việc tô màu cạnh ij 0 ở nước đi tiếp theo, buộc người thứ hai phải tô màu cạnh j 0 k. Người chơi thứ nhất tiếp tục tô màu cạnh jk 0 để tạo được dạng hình 4 và chiến thắng ở lượt chơi kế tiếp. Điều này được đảm bảo vì sau tối đa 7 lượt chơi, số cạnh được tô là 13 trong số 15 cạnh có thể tô. 4.2 Các bài toán sơ cấp Trong mục này chúng tôi sẽ giới thiệu một số bài toán sơ cấp được phát biểu từ kết quả và chứng minh của định lý Ramsey. Đầu tiên là một số bài toán mà chứng minh suy ra trực tiếp từ kết quả các số Ramsey Bài toán 1. (Trung Quốc 2005 ) Có n học sinh nhập học. Cứ mỗi 3 người thì có 2 người quen nhau. Cứ mỗi 4 người thì có 2 người không quen nhau. Giá trị lớn nhất của n là bao nhiêu?
44 NGUYỄN THÀNH THÁI HD: n = R(3, 4) − 1 = 8. Bài toán 2. (IMO 1964 ) Có 17 nhà bác học trao đổi thư từ với nhau trong đó mỗi người trao đổi thư với tất cả những người còn lại. Họ chỉ trao đổi với nhau về 3 vấn đề trong thư và mỗi cặp chỉ trao đổi 1 vấn đề. Chứng minh rằng có ít nhất 3 nhà bác học trao đổi cùng vấn đề. HD: R(3, 3, 3) = 17. Bài toán 3. Người ta xây dựng một số đường giao thông giữa 6 thành phố sao cho giữa 2 thành phố có không quá 1 đường giao thông. Chứng minh rằng hoặc có thể tìm được 4 thành phố sao cho từ bất kì thành phố nào trong số 4 thành phố đó cũng có đường đi qua cả 3 thành phố còn lại và trở về mà không cần qua thành phố nào khác, hoặc có thể tìm ra 4 thành phố mà số đường đi trực tiếp giữa chúng là 2 và trong đó không có thành phố nào có cả 2 đường đi. Nếu thay 6 bằng 5 thì điều trên có thể xảy ra không? HD: R(C4 , C4 ) = 6. Sử dụng các kĩ thuật chứng minh trong định lý Ramsey và các vấn đề liên quan, ta xây dựng được cái bài toán hay và khó Bài toán 4. (IMO 1992 ) Trong không gian cho 9 điểm trong đó không có 4 điểm nào đồng phẳng. Giữa các điểm ta nối n cạnh (n ≤ 36) và tô màu xanh đỏ. Tìm n nhỏ nhất để tồn tại tam giác đồng màu. HD: n = 33. Sử dụng kĩ thuật chứng minh và xây dựng đồ thị phản ví dụ với R(3, 3) = 6. Bài toán 5. Có 18 đội bóng tham gia vào một giải đấu vòng tròn một lượt (2 đội bất kì gặp nhau đúng 1 trận). Chứng minh rằng sau 8 vòng đấu có thể tìm ra 3 đội bóng mà trong đó không có 2 đội nào từng gặp nhau. HD: Lập luận tương tự trong chứng minh R(3, 3) = 6. Bài toán 6. (Nhật Bản 1998 ) Trong một đất nước có 1998 thành phố người ta xây dựng các đường giao thông nối giữa các thành phố sao cho giữa 2 thành phố có nhiều nhất một đường giao thông (nối trực tiếp) và cứ mỗi 3 thành phố thì có 2 thành phố không có đường giao thông. Số đường giao thông lớn nhất là bao nhiêu? HD: 998001. Sử dụng định lý Turan. n2 Bài toán 7. Cho các số thực x1 , x2 , . . . , xn . Chứng minh rằng có không quá 2 cặp (i, j) sao cho a < |xi − xj | < 2a với a > 0 cho trước.
VỀ ĐỊNH LÝ RAMSEY, CÁC SỐ RAMSEY 2 MÀU... 45 HD: Xét đồ thị n đỉnh được đánh số x1 , x2 , . . . , xn . Một cạnh được nối nếu 2 đỉnh thỏa mãn a < |xi − xj | < 2a. Bài toán 8. (Mỹ 1978 ) Có n nhà khoa học tham dự hội nghị. Mỗi nhà khoa học biết nhiều nhất k ngôn ngữ. Cứ mỗi 3 nhà khoa học thì có ít nhất 2 người có thể nói chuyện với nhau (biết chung một ngôn ngữ). Tìm n nhỏ nhất theo k sao cho ta luôn tìm được một ngôn ngữ mà ngôn ngữ này là ngôn ngữ chung của ít nhất 3 nhà khoa học. HD: n = 2k + 3. Xét đồ thị có các đỉnh tương ứng với các nhà khoa học và mỗi cạnh nối 2 đỉnh ứng với 2 nhà khoa học không có ngôn ngữ chung. Một ý tưởng tự nhiên khác là: ta đã biết với mỗi cách tô 2 màu đồ thị K6 , luôn tìm được K3 đồng màu. Vậy thì có thể tìm được bao nhiêu K3 đồng màu? Câu trả lời là ít nhất có 2 đồ thị K3 đồng màu. Tổng quát câu hỏi trên ta sẽ được kết quả: Với mỗi cách tô 2 màu đồ thị Kn luôn tìm được n(n − 1)(n − 5) ít nhất đồ thị K3 đồng màu. Một bài toán sử dụng ý tưởng này là 24 Bài toán 9. (Tạp chí AMM ) Chứng minh rằng đồ thị bù của một đồ thị không chứa K3 với n đỉnh và m cạnh có ít nhất n(n − 1)(n − 5) 2 n2 − n 2 + (m − ) 24 n 4 tam giác. ! n n 1 P HD: Số tam giác là m = − 2 di (n − di − 1) với di là bậc của đỉnh i. 3 i=1 Bài toán 10. Có 2013 nhà khoa học từ 6 quốc gia đến tham dự hội nghị và được xếp ngồi theo các ghế có đánh số thứ tự từ 1 đến 2013. Chứng minh rằng có thể tìm được 3 nhà khoa học đến từ một quốc gia sao cho số ghế của một người bằng tổng số ghế 2 người còn lại, hoặc có thể tìm ra 2 nhà khoa học đến từ một quốc gia mà số ghế người này gấp đôi số ghế người còn lại. HD: Đặt nk = k!(1 + 1!1 + 2!1 + . . . + k! 1 ) + 1. Chứng minh rằng với mọi cách tô k màu một đồ thị Knk ta luôn tìm được một tam giác đồng màu. Dựa trên ý tưởng ma trận kề (liên kết) với đồ thị (ma trận vuông có aij = 1 nếu 2 đỉnh i, j của đồ thị được nối, ngược lại aij = 0). Bài toán 11. Hãy tìm một ma trận vuông A cấp 17, có một giá trị riêng bằng 8 và chỉ gồm các phần tử 0, 1 sao cho không tồn tại i, j, k, l mà aij = ajk = akl = ali = 0.
46 NGUYỄN THÀNH THÁI HD: Xây dựng ma trận kề với đồ thị phản ví dụ R(4, 4) (đồ thị Paley). Bài toán 12. Cho ma trận vuông A cấp 18, đối xứng và có các phần tử là 0 hoặc 1 thỏa mãn trên đường chéo chính toàn số 0 và không tồn tại i, j, k sao cho aij = ajk = aki = 1. Chứng minh A có giá trị riêng bằng 5 và đây là giá trị riêng lớn nhất. Chứng minh tồn tại i, j, k, l sao cho aij = ajk = akl = ali = 1 và hơn nữa, tồn tại i1 , i2 , . . . , i6 sao cho aij ik = 0 với j, k ∈ {1, 2, . . . , 6}. HD: Dùng kết quả trong chứng minh R(3, 6). TÀI LIỆU THAM KHẢO [1] Reinhard Diestel (2005), Graph Theory, Electronic Edition, Springer-Verlag Heidel- berg, New York. [2] Bruce M.Landman và Aaron Robertson (2003), Ramsey Theory on the Integers, Stu- dent Mathematical Library Volume 24, American Mathematical Society. [3] Alexander Soifer (2010), Ramsey Theory: Yesterday, Today and Tomorrow, Springer. [4] Wolfgang Slany (1999), Graph Ramsey games, DBAI Technical Report. [5] Aleksandar Pekec (1996), A winning strategy for the Ramsey graph game, Combina- torics, Probability and Computing, 5(3), 267-276. [6] F.R.K.Chung và C.M.Grinstead (1983), A Survey of Bounds for Classical Ramsey Numbers, Journal of Graph Theory, 7, 25-37. [7] Stanislaw P.Radziszowski (2006), Small Ramsey Numbers, The Electronic Journal of Combinatorics. [8] David Conlon (2009), A New Upper Bound for Diagonal Ramsey Numbers, Annals of Mathematics, 170(2), 941-960. [9] Titu Andreescu, Zuming Feng và George Lee Jr (1996-2001), Mathematical Olympiads - Problems and Solutions From Around the World, The Mathematical Association of America. [10] Các đề thi từ http://www.artofproblemsolving.com/Forum/resources.php NGUYỄN THÀNH THÁI SV lớp Toán 3B, Khoa Toán học, Trường Đại học Sư phạm - Đại học Huế ĐT: 01677391898, Email: sala_inception_sala@yahoo.com