Xem mẫu
- 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
nguon tai.lieu . vn
