ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN XUÂN VINH
VỀ ĐỊNH LÝ VAN DER WAERDEN,
SỐ RAMSEY VÀ TẬP ĐƠN SẮC
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2018
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC ---------------------------
NGUYỄN XUÂN VINH
VỀ ĐỊNH LÝ VAN DER WAERDEN,
SỐ RAMSEY VÀ TẬP ĐƠN SẮC
Chuyên ngành: Phƣơng pháp Toán sơ cấp
Mã số: 8460113
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. Hà Huy Khoái
THÁI NGUYÊN - 2018
1
Mục lục
Mở đầu 2
1 Tổng quan về lý thuyết số tổ hợp
1.1. Định lý Van der Waerden và Định lý Szemerédi
4 . . . . . . 4 1.1.1. Định lý Van der Waerden 1927 . . . . . . . . . . 4 1.1.2. Số Van der Waerden . . . . . . . . . . . . . . . . . 8 . . . . . . . . . . . . . . . . . . 9 1.1.3. Định lý Szemerédi 1.2. Hệ phủ đồng dư . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2. Giả thuyết Selfridge và Schinzel và một số bài toán 13
2 Số Ramsey và tập đơn sắc
16 2.1. Số Ramsey . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2. Tính chất số Ramsey . . . . . . . . . . . . . . . . . 17 2.1.3. Tiệm cận số Ramsey . . . . . . . . . . . . . . . . . 18 2.1.4. Số Ramsey cho trường hợp tổng quát . . . . . . . . 22 2.2. Tập đơn sắc . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . 27 2.2.2. Tập đơn sắc và các vấn đề liên quan . . . . . . . . 28
Kết luận 34
Tài liệu tham khảo 35
2
Mở đầu
Lý thuyết số tổ hợp là một trong những chủ đề được nhiều người quan tâm nghiên cứu trong lý thuyết số. Các kết quả của lý thuyết số tổ hợp có nhiều ứng dụng trong nghiên cứu các bộ môn khoa học khác cũng như ứng dụng vào trong các vấn đề thực tế. Ngoài ra, nhiều vấn đề của lý thuyết số tổ hợp còn được đề cập đến trong các đề thi học sinh giỏi toán.
Mục đích của luận văn là tìm hiểu và trình bày một số vấn đề của lý thuyết số tổ hợp. Cụ thể, luận văn trình bày về Định lý Van der Waerden về sự tồn tại một cấp số cộng đơn sắc trong một tập số tự nhiên liên tiếp được tô màu, về Định lý Szemerédi về mật độ cấp số cộng trong tập hợp các số tự nhiên liên tiếp, về khái niệm hệ phủ đồng dư và ứng dụng trong giải toán, về số Ramsey và tập đơn sắc trong bài toán tô màu.
Ngoài phần kết luận, mở đầu và tài liệu tham khảo nội dung chính
của luận văn trình bày thành 2 chương:
Chương 1: Tổng quan về lý thuyết số tổ hợp. Mục đích của chương này là trình bày về Định lý Van der Waerden, Định lý Szemerédi, nêu ra một vài giá trị đã biết về số Van der Waerden và một số vấn đề liên quan tới hệ phủ đồng dư.
Chương 2: Số Ramsey và tập đơn sắc. Mục đích của chương này là trình bày khái niệm về số Ramsey và một số kết quả về số Ramsey, tập đơn sắc và một số vấn đề liên quan tới tập đơn sắc trong bài toán tô màu.
Luận văn được hoàn thành với sự hướng dẫn, chỉ bảo tận tình của GS.TSKH. Hà Huy Khoái và sự đóng góp ý kiến sát sao của các thầy, cô trường Đại học Khoa học - Đại học Thái nguyên. Qua luận văn này em xin được bày tỏ lòng biết ơn đến sự hướng dẫn tận tình của thầy hướng dẫn và các thầy, cô trường Đại học Khoa học - Đại học thái nguyên đã góp ý sâu sắc, tạo điều kiện thuận lợi để em hoàn thành luận văn nay.
3
Tôn xin trân trọng cám ơn đến Sở Giáo dục và Đào tạo Bắc Ninh, tập thể sư phạm trường THPT Lý Thường Kiệt đã tạo điều kiện cho tôi hoàn thành khóa học.
4
Chương 1
Tổng quan về lý thuyết số tổ hợp
1.1. Định lý Van der Waerden và Định lý Szemerédi
Trong Chương 1, luận văn trình bày hai định lý, gồm Định lý Van der Waerden và Định lý Szemerédi, một vài giá trị đã biết về số Van der Waerden và các khái niệm cơ bản về hệ phủ đồng dư. Tài liệu tham khảo chính của chương này là các tài liệu [1], [4].
Định lý Van der Waerden và Định lý Szemerédi là hai định lý quan trọng trong lý thuyết số nghiên cứu về cấp số cộng và mật độ của cấp số, đồng thời hai định lý này cũng là tiền đề để tìm hiểu và phát triển các kết quả mới về cấp số cộng.
Nhắc lại rằng cấp số cộng là một dãy số (hữu hạn hoặc vô hạn) mà trong đó, kể từ số hạng thứ hai trở đi, mỗi số hạng đều bằng tổng của số hạng đứng ngay trước nó với một số d không đổi. Ta có thể biểu diễn cấp số cộng dưới dạng như sau: a, a + d, a + 2d, . . . , a + (m − 1)d, ..., trong đó: m là số nguyên dương bất kỳ, a, d ∈ R, a được gọi là số hạng đầu tiên và d gọi là công sai của cấp số cộng.
Với mọi n là số tự nhiên, ta kí hiệu [n] = {1, 2, . . . ., n} là tập hợp
các số tự nhiên từ 1 đến n.
Cho một tập hợp X và t ∈ N, khi đó X(t) = {A ⊂ X, |A| = t} , tức
là X(t) là tập hợp gồm các tập con của X có lực lượng t.
1.1.1. Định lý Van der Waerden 1927
Định lý Van der Waerden phát biểu rằng: Với hai số nguyên dương m, k cho trước tồn tại một số nguyên N = N (m, k) sao cho với mọi
5
n ≥ N nếu [n] được tô bởi k màu thì luôn tồn tại một cấp số cộng đơn sắc độ dài m trong [n].
Giả sử Định lý Van der Waerden được chứng minh. Do tập [n] được tô bởi k màu nên ta có thể chia tập [n] thành k tập con được xác định bởi k màu riêng biệt. Theo Định lý Van der Waerden thì khi đó sẽ tồn tại một tập con trong k tập con trên mà trong đó tồn tại một cấp số cộng độ dài m.
Ta có thể phát biểu lại Định lý Van der Waerden dưới dạng sau:
Định lý 1.1 Đối với mọi cặp số tự nhiên k, l luôn tồn tại số tự nhiên n(k, l) sao cho nếu một đoạn bất kỳ của dãy số tự nhiên có độ dài n(k, l) được phân hoạch theo cách tuỳ ý thành k lớp, thì sẽ có ít nhất một lớp trong k lớp đó chứa một cấp số cộng độ dài l.
Để chứng minh Định lý Van der Waerden, ta sẽ chứng minh một
định lý tổng quát hơn:
Định lý 1.2 Cho trước dãy vô hạn số tự nhiên:
(1.1) t1, t2, ..., tq, ...
Đối với mỗi cặp số tự nhiên k, l luôn tồn tại một số tự nhiên n(k, l) sao cho nếu một đoạn bất kỳ của dãy số tự nhiên có dộ dài n(k, l) được phân hoạch theo cách tuỳ ý thành k lớp, thì sẽ có ít nhất một lớp mà trong đó tồn tại dãy số c1, c2, ..., cl thỏa mãn diều kiện sau:
(c2 − c1) : (c3 − c2) : ... : (cl − cl−1) = t1 : t2 : ... : tl−1.
Nói một cách ngắn gọn, l số đó lập nên một cấp số cộng tổng quát độ dài l được tạo ra bởi dãy số (1.1). Định lý Van der Waerden là trường hợp riêng của Định lý 1.2 trong trường hợp t1 = t2 = · · · = tq = · · · = 1.
Chứng minh Định lý 1.2.
Đặt số hạng đầu tiên của dãy (1.1) bằng đơn vị: t1. Dễ thấy rằng Định lý 1.2 là hiển nhiên với l = 2 và với mọi k (bởi vì số n(k, l) có thể nhận giá trị k + 1), tức là tồn tại một cấp số cộng trong dãy có độ dài là 2, điều này luôn đúng. Giả sử định lý đúng với mọi số l ≥ 2 và k bất kỳ.
Đặt:
(1.2) q0 = 1, n0 = n(k, l), qs = (1 + t1)ns−1qs−1, ns = n(kqs, l) > 0.
6
Ta sẽ chứng minh định lý đúng với l + 1, tức là số n(k, l + 1) có thể lấy bằng qk. Giả sử đoạn (cid:52) của dãy số tự nhiện có độ dài qk được phân hoạch thành k lớp. Hai số a và b của đoạn (cid:52) được gọi là cùng loại nếu chúng cùng nằm trong một lớp và được viết là a ∼ b. Hai đoạn (cid:52)(cid:48)(a, a + 1, ..., a + r) và (cid:52)(cid:48)(cid:48)(a, a(cid:48) + 1, ..., a(cid:48) + r) có độ dài bằng nhau và cùng nằm trong đoạn (cid:52) sẽ được gọi là cùng loại và được viết (cid:52)(cid:48) ∼ (cid:52)(cid:48)(cid:48), nếu a + j ∼ a(cid:48) + j, j = 0, 1, ..., r. Rõ ràng đối với các đoạn có độ dài m, thì số các loại khác nhau có thể sẽ bằng km.
Vì qk = (1 + tl)nk−1qk−1 nên đoạn (cid:52) có thể được xem như gồm hai phần không bằng nhau: Phần bên trái là một dãy gồm nk−1 đoạn có độ dài qk−1, còn phần bên phải là một dãy gồm tlnk−1 đoạn có độ dài qk−1. Ta sẽ nói rằng các đoạn có độ dài bằng nhau tạo nên một cấp số cộng tổng quát nếu cấp số đó được lập nên bởi các số đầu tiên của chúng. Do định nghĩa của số nk−1 nên ta có thể khẳng định được rằng: Phần bên trái của đoạn (cid:52) chứa một cấp số cộng tổng quát từ l đoạn cùng loại với nhau (cid:52)1, (cid:52)2, ..., (cid:52)l và cùng có độ dài là qk−1. Ký hiệu các khoảng cách giữa các đầu mút bên trái của hai đoạn kề nhau (tức là hiệu giữa hai số đầu tiên của hai đoạn kề nhau) là: d1, d1t2, ..., d1tl−1.
Đối với cấp số cộng tổng quát, từ các đoạn cùng loại đó ta gắn thêm vào nó phần tử thứ l + 1 là (cid:52)l+1, phần tử ấy có thể không cùng loại với các phần tử đứng trước và nó có thể vượt quá phần tử đầu tiên của đoạn (cid:52), nhưng vẫn nằm trong đoạn (cid:52).
Bây giờ ta lấy một phần tử (cid:52)i1 bất kỳ từ l phần tử của cấp số cộng tổng quát, đó là đoạn có độ dài qk−1. Ta sẽ tiến hành trên đoạn đó tương tự như đã tiến hành với đoạn (cid:52) (tức là coi đoạn (cid:52) như là dãy (1 + tl)nk−1 đoạn có độ dài qk−1). Do định nghĩa của số nk−1, ta có thể khẳng định rằng, phần bên trái của đoạn (cid:52)i1 bao gồm nk−1 đoạn có độ dài qk−2 chứa cấp số cộng tổng quát từ l đoạn cùng loại (cid:52)i2i2(1 ≤ i2 ≤ l) có cùng độ dài qk−1. Ta ký hiệu các khoảng cách giữa các đầu mút trái của hai đoạn kề nhau (cid:52)i2i2 là: d2, d2t2, ..., d2tl−1.
Một lần nữa, ta lại nối thêm vào cấp số cộng tổng quát này phần tử thứ l + 1 và rõ ràng phần tử ấy cũng vẫn nằm trong đoạn (cid:52)i1. Việc xây dựng như vậy được tiến hành với tất cả các đoạn (cid:52)i1(1 ≤ i1 ≤ l + 1) và trong tất cả các đoạn đó ta sẽ lấy các đoạn (cid:52)i2i2(1 ≤ i2 ≤ l + 1) theo vị trí tương ứng. Bởi vì tất cả là cùng loại nên rõ ràng mọi (cid:52)i2i2 sẽ là cùng loại, nếu 1 ≤ i1 ≤ l, 1 ≤ i2 ≤ l.
Quá trình xây dựng được tiếp tục k lần. Kết quả sau lần cuối cùng ta
7
Như vậy ta dễ thấy rằng, với 1 ≤ s ≤ k, 1 ≤ ir ≤ l, 1 ≤ i(cid:48) sẽ nhận được các đoạn có độ dài q0 = 1, tức là một đoạn đơn giản (cid:52) mà một cách tổng quát ta có thể ký hiệu là (cid:52)i1i2...ik (1 ≤ i1, i2, ..., ik ≤ l+1). r ≤ l(1 ≤
r ≤ s) thì
2...i(cid:48) s
r ≤ l(1 ≤ r ≤ s), 1 ≤ im ≤
. (1.3) (cid:52)i1i2...is ∼ (cid:52)i(cid:48) 1i(cid:48)
Hai nhận xét sau đây là rất quan trọng đối với phần còn lại trong chứng minh định lý. 1) Giả sử: 1 ≤ s ≤ k, 1 ≤ ir ≤ l, 1 ≤ i(cid:48) l + 1 (s + 1 ≤ m ≤ k). Khi đó
2...i(cid:48)
s+1...ik. si(cid:48)
(1.4) (cid:52)i1i2...isis+1...ik ∼ (cid:52)i(cid:48) 1i(cid:48)
2...i(cid:48) s
s = is + 1, các đoạn (cid:52)i1...is−1is và (cid:52)i1...is−1i(cid:48)
.
Thật vậy, do hai số đó đứng ở các vị trí giống nhau trong các đoạn cùng loại (cid:52)i1i2...is và (cid:52)i(cid:48) 1i(cid:48) 2) Với số s ≤ k, is ≤ l, i(cid:48) s là các đoạn kề nhau ở bước xây dựng thứ s của chúng ta, nên đối với mọi chỉ số is+1, ...ik, các số (cid:52)i1i2...s−1isis+1...ik và (cid:52)i1i2...s−1i(cid:48) sis+1...ik sẽ chiếm các vị trí giống nhau trong hai đoạn kề nhau, sao cho:
sis+1...ik − (cid:52)i1i2...s−1isis+1...ik = dstis.
(1.5) (cid:52)i1i2...s−1i(cid:48)
Để ngắn gọn, ta đặt l(cid:48) = l + 1. Xét k + l số
(1.6) , r = 0, 1, ..., k.
k−r
l(cid:48) · · · l(cid:48) (cid:124) (cid:123)(cid:122) (cid:125) ar = (cid:52)1 · · · 1 (cid:124) (cid:123)(cid:122) (cid:125)r
Trong các số đó, ta luôn tìm được hai số ar và as cùng nằm trong một lớp
(1.7) .
k−r
k−s
l(cid:48) · · · l(cid:48) (cid:124) (cid:123)(cid:122) (cid:125) l(cid:48) · · · l(cid:48) (cid:124) (cid:123)(cid:122) (cid:125) (cid:52)1 · · · 1 (cid:124) (cid:123)(cid:122) (cid:125)r ∼ (cid:52)1 · · · 1 (cid:124) (cid:123)(cid:122) (cid:125)s
Xét các số
(1.8) (1 ≤ i ≤ l(cid:48)).
k−s
l(cid:48) · · · l(cid:48) (cid:124) (cid:123)(cid:122) (cid:125) ar = (cid:52)1 · · · 1 (cid:124) (cid:123)(cid:122) (cid:125)r i · · · i (cid:124) (cid:123)(cid:122) (cid:125)s−r
Ta sẽ chứng minh rằng chúng cùng nằm trong một lớp, và tạo thành một cấp số cộng tổng quát.
Thật vậy, các số cl(cid:48) và c1 cùng loại do (1.7), còn tất cả các ci(i < l(cid:48)) là cùng loại do (1.4). Vì vậy tất cả các số ci(1 ≤ i ≤ l(cid:48)) cùng nằm trong một lớp. Phần còn lại, ta cần phải chỉ ra rằng các số đó lập thành một cấp số cộng, tức là:
(1.9) (c2 − c1) : (c3 − c2) : · · · : (cl(cid:48) − cl) = 1 : t2 : · · · : tl(cid:48).
8
Để ngắn gọn, ta đặt i(cid:48) = i + 1. Ta đưa vào xét các số sau:
(0 ≤ m ≤ s − r).
s−r−m
k−s
i · · · i (cid:124) (cid:123)(cid:122) (cid:125) l(cid:48) · · · l(cid:48) (cid:124) (cid:123)(cid:122) (cid:125) ci,m = (cid:52)1 · · · 1 (cid:124) (cid:123)(cid:122) (cid:125)s i(cid:48) · · · i(cid:48) (cid:124) (cid:123)(cid:122) (cid:125)m
s−r (cid:80) m=1
Khi đó ci+1 − ci = (ci,m − ci,m−1) bởi vì ci,0 = ci và ci,s−r = ci+1.
=
s−r−m
s−r−m+1
k−s
k−s
l(cid:48) · · · l(cid:48) (cid:124) (cid:123)(cid:122) (cid:125) i · · · i (cid:124) (cid:123)(cid:122) (cid:125) l(cid:48) · · · l(cid:48) (cid:124) (cid:123)(cid:122) (cid:125) Nhưng do (1.5) ta có ci,m−ci,m−1 = (cid:52)1 · · · 1 (cid:124) (cid:123)(cid:122) (cid:125)r i(cid:48) · · · i(cid:48) (cid:124) (cid:123)(cid:122) (cid:125)m −(cid:52)1 · · · 1 (cid:124) (cid:123)(cid:122) (cid:125)r i(cid:48) · · · i(cid:48) (cid:124) (cid:123)(cid:122) (cid:125)m−1
dr+mti, có nghĩa là: ci+1 − ci = dr+mti. i · · · i (cid:124) (cid:123)(cid:122) (cid:125) s−r (cid:80) m=1
s−r (cid:80) m=1
Nhưng do dr+m không phụ thuộc vào i, và do đó điều kiện (1.9)
được thỏa mãn. Do đó định lý được chứng minh với giả thiết rằng, phần tử đầu tiên của dãy số (1.1) bằng đơn vị (tức là bằng 1). Nếu t1 khác đơn vị, thì ta xét dãy số sau đây:
(1.10) 1, t1, · · · , tq, · · · .
Khi đó l + 1 số ci(i = 1, 2, · · · , l + 1) lập thành một cấp số cộng tổng quát độ dài l + 1, được tạo ra bởi dãy số (1.10) cùng nằm trong một lớp, vì thế đương nhiên nó chứa l số lập thành cấp số cộng tổng quát độ dài l, được tạo ra bởi dãy số (1.1) và cùng nằm trong một lớp. Do đó định lý được chứng minh.
1.1.2. Số Van der Waerden
Định nghĩa 1.1 Số tự nhiên nhỏ nhất N = N (m, k) thỏa mãn Định lý Van der Waerden được gọi là số Van der Waerden, và kí hiệu là w(m, k).
Một số giá trị chính xác của w(m, k) đã được chỉ ra. Ta có w(m, 1) = m và w(2, k) = k + 1. Với các giá trị khác của k và m, chúng ta đã biết w(3, 2) = 9, w(4, 2) = 35, w(5, 2) = 178, w(6, 2) = 1132, w(3, 3) = 27 và w(4, 3) = 76.
Sau đây ta kiểm tra lại, chẳng hạn hai kết quả w(m, 1) = m và
w(2, k) = k + 1.
Thật vậy: +) w(m, 1) = m, khi đó tất cả các phần tử của [n] được tô bằng 1 màu. Như vậy, nếu đặt N = m thì với mọi n ≥ N, trong [n] tồn tại cấp
9
số cộng độ dài m (chính là m số liên tiếp). Khi n < m thì hiển nhiên không thể tồn tại cấp số cộng độ dài m trong [n]. Vậy N (m, 1) = m chính là số nhỏ nhất cần tìm, tức là w(m, 1) = m.
+) w(2, k) = k + 1, khẳng định này tương đương với việc khi tô tập hợp [n] với n ≥ k + 1 bởi k màu, thì trong k + 1 phần tử tuỳ ý, phải tồn tại cấp số cộng hai số hạng cùng màu. Nhưng điều này là hiển nhiên, vì trong k + 1 số, có ít nhất hai số cùng màu, và dĩ nhiên chúng lập thành cấp số cộng 2 số hạng. Nếu chỉ lấy k số thì có thể xẩy ra trường hợp k số đó được tô bởi k màu khác nhau. Vậy số nhỏ nhất thoả mãn là k + 1, tức là w(2, k) = k + 1.
1.1.3. Định lý Szemerédi
Trong lý thuyết số, Định lý Szemerédi là một kết quả mà trước đó mang tên "giả thuyết Erd˝os–Turán". Năm 1936 Erd˝os và Turán đưa ra giả thuyết rằng: “Với mọi giá trị d, gọi là mật độ, thỏa mãn 0 < d < 1 và số nguyên k, tồn tại số nguyên N = N (d, k) sao cho mọi tập hợp con A của 1, ..., N với lực lượng lớn hơn hoặc bằng dN đều chứa một cấp số cộng độ dài k.
Đây là một tổng quát hóa của Định lý Van der Waerden. Trường hợp k = 1 và k = 2 là tầm thường. Trường hợp k = 3 được chứng minh năm 1956 bởi Klaus Roth bằng phương pháp đường tròn Hardy–Littlewood. Trường hợp k = 4 được chứng minh năm 1969 bởi Endre Szemerédi bằng phương pháp tổ hợp. Bằng phương pháp tương tự như cho trường hợp k = 3, Roth đưa ra một chứng minh khác cho kết quả này năm 1972.
Cuối cùng trường hợp tổng quát cho mọi k được chứng minh năm 1975, bằng một mở rộng phức tạp của chứng minh tổ hợp trước đó cũng bởi Szemerédi (đây là "một kiệt tác của lập luận tổ hợp", như đánh giá của R. L. Graham).
Định lý 1.3 (Định lý Szemerédi) Mọi dãy số nguyên mật độ dương đều chứa cấp số cộng độ dài tuỳ ý.
Ngày nay nhiều chứng minh khác của kết quả này đã được tìm ra, một vài chứng minh quan trọng trong số đó là của Hillel F¨urstenberg năm 1977 bằng lý thuyết Ergodic và bởi Timothy Gowers năm 2001 bằng giải tích Fourier và toán học tổ hợp.
10
Giả sử k là một số nguyên dương và 0 < δ ≤ . Một phiên bản 1 2
1.2. Hệ phủ đồng dư
hữu hạn của định lý khẳng định rằng, tồn tại số nguyên N = N (k, δ) sao cho mọi tập hợp con của {1, 2, ..., N } với kích thước δN đều chứa một cấp số cộng độ dài k. Chặn chặt nhất đến nay cho N (k, δ) là C log(1/δ)k−1 ≤ N (k, δ) ≤ 22δ−22k+9 . Với C > 1, chặn dưới là của Behrend (cho k = 3) và Rankin, chặn trên là của Gowers. Trong trường hợp đặc biệt k = 3 chặn trên chặt nhất đến nay là N (3, δ) ≤ C δ−2log(1/δ).
1.2.1. Định nghĩa
Hệ phủ đồng dư hay tập phủ đồng dư là một tập hữu hạn
(a1, n1), (a2, n2), · · · , (ar, nr),
với ai ∈ Z và n1 < n2 < · · · < nk, là các số tự nhiên sao cho với mọi số nguyên x, tồn tại chỉ số j, sao cho ta có đồng dư thức:
(1.11) x ≡ aj (mod nj).
Một câu hỏi cơ bản được đặt ra từ năm 1934 là: n1 có được chọn tùy ý không? Đặc biệt nó có thể lớn tuỳ ý không? Giá trị kỉ lục của nó cho đến nay là 20, do S.R. L Choi tìm ra. Một câu hỏi khác: “Đúng hay không, với mọi số d > 0, tồn tại một hệ phủ đồng dư với (ni, d) = 1"? Một tập số nguyên 1 < n1 < · · · < nk được gọi là hệ phủ đồng dư nếu chúng có thể lấy làm các modulo của hệ (1.11). Hệ phủ đồng dư được gọi là bất khả quy hay hệ phủ đồng dư thu gọn nếu không có tập con nào của nó là một hệ phủ đồng dư. Dễ thấy chỉ tồn tại một số hữu hạn hệ phủ đồng dư bất khả quy độ lớn k.
Ví dụ 1.1 . (0,2); (0,3); (1,4); (1,6); (11,12) là một phủ đồng dư có thể viết đơn giản (2,3,4,6,12) là một tập phủ đồng dư.
Chứng minh (Erd˝os).
Xét các hệ đồng dư, mà có thể chỉ ra rằng chúng lập thành một hệ phủ: 0 (mod 2), 0 (mod 3), 1 (mod 4), 3 (mod 8), 7 (mod 12), và 23 (mod 24). Mỗi một đồng dư thức kéo theo một đồng dư tương ứng đối với lũy thừa nào đó của 2. Ví dụ, đồng dư thức k ≡ 1 (mod 4) cùng với
11
24 ≡ 1(mod 5) kéo theo 2k ≡ 2(mod 5). Để thấy rõ điều này, giả sử k = 4n + 1 và nhận xét rằng: 2k ≡ 24n+1 ≡ 2(24)n ≡ 2 (mod 5).
Tương tự, nếu k là một số nguyên không âm thì ít nhất một trong các đồng dư sau nghiệm đúng: 2k ≡ 1 (mod 3), 2k ≡ 1 (mod 7), 2k ≡ 2 (mod 5), 2k ≡ 8 (mod 17), 2k ≡ 27 (mod 13) hoặc 2k ≡ 23 (mod 241). Bây giờ xét các đồng dư thức: 1 (mod 3), 1 (mod 7), 2 (mod 8), 8 (mod 17), 27 (mod 13), và 223 (mod 241).
Vì các modulo đôi một nguyên tố cùng nhau, tồn tại vô hạn số nguyên thỏa mãn tất cả các đồng dư thức trên (theo định lý phần dư Trung Hoa). Bây giờ nếu số nguyên lẻ a thỏa mãn tất cả các đồng dư, thì tất cả các số nguyên có dạng a − 2k chia hết cho một trong các modulo 3, 7, 5, 17, 13 hoặc 241. Suy ra rằng a − 2k không là số nguyên tố và do đó a không có dạng 2k + p.
Một ví dụ khác về ứng dụng hệ phủ đồng dư được biết đến bởi R. L Graham trong cuốn "A Fibonacci-like sequence of composite number", xuất bản năm 1964. Kết quả của ông về nghĩa nào đó là ngược lại với một giả thuyết được biết, nói rằng dãy Fibonacci, xác định bởi f0 = 0, f1 = 1, và với n ≥ 0, fn+2 = fn+1 + fn, chứa vô hạn số nguyên tố. Graham sử dụng hệ phủ đồng dư để chỉ ra rằng, có thể chọn các giá trị ban đầu f0 và f1 nguyên tố cùng nhau, sao cho dãy tương ứng chỉ chứa các hợp số. Giá trị nhỏ nhất được biết đến là:
f0 = 331636535998274737472200656430763
và
f1 = 1510028911088401971189590305498785.
Một bài toán mở quan trọng trong chủ đề này là giả thuyết của Erd˝os nói rằng: “Với mọi c ≥ 2, tồn tại hệ phủ đồng dư với n1 ≥ c và các modulo khác nhau”. Điều này được biết đến là đúng với một vài giá trị của c, kỷ lục cho đến nay là c = 20. Nếu có một hệ phủ đồng dư với các modulo khác nhau và n1 ≥ c với mọi c ≥ 2 thì ta nhận được một kết quả về cấp số cộng “với mọi số nguyên dương m, tồn tại một cấp số cộng mà không có số hạng nào của nó là tổng của một lũy thừa 2 và một số nguyên có không quá m ước nguyên tố".
Bài toán dưới đây cho chúng ta một áp dụng của hệ phủ đồng dư
trong giải toán.
Bài toán 1.1 (Kỳ thi toán học Mỹ (AIME)) Harold, Tanya và Ulysses sơn một hàng rào rất dài. Harold bắt đầu sơn từ cột thứ nhất
12
và sơn mỗi cột cách đều h cột, Tanya bắt đầu sơn từ cột thứ 2 và sơn mỗi cột cách đều t cột, Ulysses bắt đầu sơn từ cột thứ 3 và sơn mỗi cột cách đều u cột. Giả sử mỗi cột được sơn đúng một lần, hãy tìm tất cả các bộ ba có thể (h, t, u).
Lời giải.
Ta đánh số các cột lần lượt là 1, 2, 3, . . . , theo bài ra, Harold sơn cột 1 và mỗi cột cách đều h, Tanya sơn cột 2 và mỗi cột cách đều t, Ulysses sơn cột thứ 3 và mỗi cột cách đều u. Do đó Ulysses không thể sơn cột thứ 4, vì nếu ngược lại thì Ulysses sơn tất cả các cột tiếp theo. Giả sử rằng Harold sơn cột 4, khi đó Ulysses không thể sơn cột 5, vì nếu ngược lại thì cả Harold và Ulysses đều sơn cột 7. Do đó Tanya sơn cột 5, Ulysses sơn cột 6 và (h, t, u) = (3, 3, 3). Mặt khác, giả sử rằng Tanya sơn cột 4, khi đó Ulysses không thể sơn cột 5, vì nếu ngược lại thì không còn cột nào cho Harold sơn. Vì vậy Ulysses sơn cột 7 và (h, t, u) = (4, 2, 4). Bài toán này thực chất là hỏi rằng “làm thế nào có thể phân hoạch tập hợp các số nguyên thành 3 cấp số cộng”. Bộ ba thứ 2 (4,2,4) thú vị hơn một chút so với bộ ba (3,3,3) vì không phải tất cả các công sai đều bằng nhau. Trong lý thuyết số sơ cấp, cấp số cộng được gọi một cách tương đương là các lớp thặng dư với modulo khác nhau. Với cách đặt vấn đề như vậy, cấp số cộng a + km với k nguyên được ký hiệu bởi a (mod m).
Ta có thể tổng quát hóa bài toán trên như sau: “Tồn tại hay không một tập hữu hạn đồng dư với modulo khác nhau, lớn hơn hoặc bằng 2, sao cho chúng lập thành một phân hoạch của tập số nguyên” . Trong bài báo “New problems and results in combinatorialnumbertheory, Monogr. Enseign Math 28, L’EnseignementMathematique, Geneva, 1980” P. Er- dos và R. L. Graham đã chứng minh điều này là không thể. Khi giảm nhẹ một chút giả thiết, ta thay điều kiện phân hoạch bởi điều kiện tồn tại hữu hạn các đồng dư sao cho mọi số nguyên thuộc ít nhất một trong chúng. Mục đích của chúng ta là trình bày một chứng minh sơ cấp về mối quan hệ giữa hai giả thuyết nổi tiếng đã biết.
Năm 1849, A.de Poligna giả thuyết rằng, mọi số nguyên lẻ n (n ≥ 3) có thể biểu diễn dưới dạng 2k + p, ở đây k là một số nguyên không âm và p hoặc là số nguyên tố, hoặc là 1. Erd˝os đã bác bỏ điều này bằng cách chứng minh rằng, tồn tại một cấp số cộng mà không có số hạng nào của nó có dạng trên.
13
1.2.2. Giả thuyết Selfridge và Schinzel và một số bài toán
Trong mục này ta quan tâm đến hai giả thuyết quan trọng khác của Selfridge và Schinzel. Giả thuyết Selfridge nói rằng “Không tồn tại hệ phủ đồng dư với modulo là các số lẻ khác nhau”; Giả thuyết Schinzel nói rằng "Trong mỗi hệ phủ đồng dư ai (mod n1) với 1 ≤ n ≤ r, tồn tại i (cid:54)= j sao cho ni | nj".
Schinzel đã chứng minh rằng giả thuyết của Selfridge kéo theo giả thuyết Schinzel bằng cách sử dụng tính bất khả quy của một số đa thức.
Định lý 1.4 Giả thuyết của Sefridge kéo theo Schinzel.
Chứng minh.
Giả sử giả thuyết của Sefridge đúng nhưng giả thuyết của schinzel không đúng. Khi đó tồn tại một hệ phủ đồng dư thu gọn as (mod ns) sao cho mi (cid:54) |mj với mọi i (cid:54)= j.
Giả sử mi = 2βiOi ở đây Oi là số lẻ với 1 ≤ i ≤ r. Ta giả sử rằng các đồng dư được đánh số theo cách sao cho nếu i < j thì βi ≤ βj. Từ giả thuyết Selfridge suy ra rằng βr > 0 và rõ ràng tất cả các số Oi là khác nhau.
Nếu Oi ≥ 3 với mọi i, thì ta có mâu thuẫn với giả thuyết Selfridge. Vì nếu x ≡ ai (mod 2βiOi) và 2βi|(2βiOi) thì x ≡ ai (mod Oi) khi đó ta sẽ có hệ phủ đồng dư với tất cả các modulo lẻ. Cho nên, nếu ai (mod ni) là một hệ phủ đồng dư và ni|mi với mọi i, thì ai (mod ni) cũng là một hệ phủ đồng dư. Vì vậy, tồn tại i0 sao cho Oi0 = 1 và do đó mi0 = 2i0. Suy ra rằng i0 = r nếu ngược lại ta có mi0|mi0+1. Tiếp theo ta nâng hệ phủ đồng dư bởi −ar có nghĩa là thay đổi biến x thành x+ar, để sao cho có thể giả sử rằng đồng dư thứ r có dạng 0 (mod 2βr). Xét số nguyên có dạng x2βr − 1 với x ∈ Z, khi đó không có số nguyên nào trong các số đó được phủ bởi đồng dư thức 0 (mod 2βr). Tuy nhiên tất cả chúng là được phủ bởi các đồng dư thức còn lại vì hệ là một hệ phủ đồng dư. Hệ của chúng ta bây giờ có dạng:
(1.12) x2βr − 1 ≡ as (mod ms), 1 ≤ s ≤ r − 1.
Chú ý rằng có thể xảy ra trường hợp không phải tất cả các đồng dư thức có nghiệm, tuy nhiên khi một đồng dư thức có nghiệm ta phải có:
gcd(2βr, ms)|as + 1.
14
Vì gcd(2βs, ms) = 2βs nên suy ra rằng 2βs|as + 1. Đặt U = {s : 1 ≤ s ≤ r − 1 sao cho 2βs|as + 1}. Với mỗi s ∈ U hệ đồng dư thức (1.12) có dạng x2βr−βs ≡ (as + 1)/2βs (mod Os) hoặc x ≡ cs (mod Os) với số nguyên cs nào đó.
Bài toán 1.2 Tìm số lớn nhất trong hệ phủ đồng dư thu gọn 1 ≤ n1 < · · · < nk và có bao nhiêu hệ phủ đồng dư thu gọn có dạng 1 ≤ n1 < · · · < n(cid:96) ≤ x với (cid:96) tùy ý.
Để giải quyết được bài toán này Erd˝os đã chỉ ra rằng cần phải ước
. Khi đó có một câu hỏi là “liệu có
lượng hoặc xác định giá trị max (cid:80) 1 ni bao nhiêu số nguyên n sao cho các ước lớn hơn 2 của n lập thành một hệ phủ thu gọn”. Ví dụ với n = 12 thì tập {2, 3, 4, 6, 12} là các ước của 12 và lập thành hệ phủ đồng dư thu gọn.
Erd˝os giả thuyết giả rằng với mọi C tồn tại số nguyên N với σ(N )/N > C sao cho các ước của N không lập thành hệ phủ đồng dư, trong đó σ(N ) là tổng các ước của N . J. Haight đã chứng minh giả thuyết này trong bài báo của ông. Bây giờ có thể phát biểu Bài toán cực trị như sau:
1 < n(i)
σ(m)/m, ở đây cực đại được lấy theo mọi m mà Đặt f (x) = max
m các ước của m không lập thành hệ phủ đồng dư. Theo định lý Haight
f (x) tiến tới vô cùng khi x dần tới vô cùng. Đúng hay không f (x) =
o(loglogx)? Nói cách khác f (x) có dần tới vô cùng chậm hơn so với
maxσ(m)/m hay không? Có một bài toán cực trị như sau “Xác định hoặc
đánh giá số lớn nhất jx của hệ phủ đồng dư {n(i)
2 < · · · < n(i)
k }
trong đó mọi số ni đều khác nhau và nhỏ hơn x”. Chúng ta không biết
rằng f (x) dần tới vô cùng khi x dần tới vô cùng hay không vì từ đó suy
ra rằng tồn tại một hệ phủ đồng dư với n lớn bất kỳ. Chúng ta hy vọng
rằng jx tiến tới vô cùng rất chậm. , ở đây cực đại được lấy trên Đánh giá hoặc ước lượng max (cid:80) 1
mi các dãy {mi} không lập thành hệ phủ đồng dư và mọi phần tử của của
nó nhỏ hơn x. Giá trị lớn nhất này có lẽ lớn hơn log x − C, vì nếu không
thì lại tồn tại một hệ phủ đồng dư với n1 đủ lớn. Romanoff chứng minh năm 1934 rằng mật độ của tập các số nguyên
có dạng 2k + p là dương. Erd˝os chứng minh rằng tồn tại cấp số cộng
u (mod v) và tập hợp hữu hạn số nguyên tố P =
gồm các số lẻ
{p1, p2, · · · , pk}, sao cho với mọi n ≡ u (mod v), mọi số n − 2l chia hết 15 cho một số nguyên tố thuộc P . Nếu jx dần đến vô cùng hoặc tương
đương, tồn tại hệ (1.11) với n lớn tuỳ ý, thì với mỗi r tồn tại một cấp
số cộng mà không có phần tử nào của nó có dạng 2k + Qr, trong đó Qr
có không quá r ước nguyên tố. Chắc chắn mỗi n đủ lớn đều có dạng
2k + Qr, r < log log n nhưng người ta vẫn chưa chứng minh được điều
này. Như vậy, ta vẫn chưa biết được rằng: Tồn tại hay không vô hạn số
nguyên lẻ n sao cho n − 2u, 1 ≤ 2u ≤ n, không bao giờ là số Squarefree
(số không có ước chính phương khác 1)? Thậm chí có tồn tại số nguyên
nào thoả mãn tính chất đó không? 16 2.1. Số Ramsey Chương 2 được dành để trình bầy về số Ramsey và một số kết quả
mới về số Ramsey, cũng như nghiên cứu tập đơn sắc và các bài toán ứng
dụng. Tài liệu tham khảo chính được sử dụng trong chương này là các
tài liệu [2], [3], [6], [7]. 2.1.1. Định nghĩa Để đi đến định nghĩa số Ramsey ta xét bài toán sau đây. Bài toán 2.1 Trong mặt phẳng cho 6 điểm được nối với nhau từng đôi
một bởi các đoạn màu xanh hoặc màu đỏ. Chứng minh rằng luôn tìm
được 3 điểm sao cho các đoạn nối chúng có cùng một màu? Vấn đề đặt ra sau bài toán này là liệu số 6 trong bài toán trên đã
là số nhỏ nhất hay chưa để tìm được 3 điểm nối với nhau bằng các cạnh
được tô cùng màu. Nếu bài toán này thay vì cho 6 điểm ta cho 5 điểm
hoặc ít hơn nữa thì có tìm được 3 điểm được nối với nhau cùng màu hay
không? Câu trả lời là không thể và số 6 nêu trong bài toán trên là số
nhỏ nhất để tìm được 3 điểm được nối với nhau bằng các cạnh được tô
cùng màu. Mở rộng phạm vi bài toán hơn nữa thì để tìm được 4 điểm,
5 điểm, ..., nối với nhau bằng các cạnh được tô cùng màu thì số nhỏ
nhất phải cho ban đầu là bao nhiêu? Đây vẫn là câu hỏi khó trả lời khi
ta cho số điểm được nối với nhau bằng các cạnh được tô cùng màu tăng
lên. Một cách phát biểu khác của bài toán trên là: Trong số 6 người tại
một bàn tiệc luôn tìm được hoặc ba người đôi một quen nhau hoặc ba 17 người đôi một không quen nhau. Con số nhỏ nhất vừa nói đến trong các vấn đề vừa đặt ra được gọi là
các số Ramsey, mang tên nhà toán học người Anh đã chứng minh được
định lý nổi tiếng trong lý thuyết tập hợp là sự tổng quát hoá nguyên lý
Dirichlet. Để có thể phát biểu những kết quả tổng quát hơn chúng ta có
một số định nghĩa. Định nghĩa 2.1 Đồ thị Kn là bộ gồm hai tập V, E, trong đó V là tập
gồm n điểm còn E là tập các đoạn nối giữa tất cả các cặp điểm trong
V . Ta ký hiệu Kn = (V, E), gọi các phần tử của V là các đỉnh và V là
tập đỉnh của Kn. Mỗi đoạn nối hai đỉnh u, v ∈ V sẽ được gọi là một
cạnh của Kn và ký hiệu là (u, v) và tập E được gọi là tập cạnh của Kn. Khi đó ta có thể phát biểu lại bài toán 2.1 như sau: Giả sử mỗi
cạnh của K6 được tô bởi một trong hai màu xanh hoặc đỏ. Khi đó, K6
luôn chứa hoặc K3 với tất cả các cạnh được tô màu xanh hoặc được tô
màu đỏ. Để giải quyết bài toán trên Ramsey năm 1930 đã chứng minh
định lý sau: Định lý 2.1 Cho hai số nguyên m1, m2 ≥ 2. Khi đó luôn tồn tại một
số nguyên N = N (m1, m2) sao cho với mọi n ≥ N, nếu đồ thị Kn được
tô bởi 2 màu thì luôn tồn tại hoặc một đồ thị Km1 được tô bởi màu thứ
nhất hoặc Km2 được tô bởi màu thứ hai. Định nghĩa 2.2 Giả sử i và j là hai số nguyên dương sao cho i ≥ 2, j ≥
2. Số nguyên dương m được gọi là có tính chất (i, j)-Ramsey nếu trong
Km mỗi cạnh được tô bởi một trong hai màu xanh, đỏ thì Km luôn chứa
hoặc là Ki đỏ, hoặc Kj xanh. Ta có định nghĩa số Ramsey như sau. Định nghĩa 2.3 Số Ramsey R(i, j) là số nguyên dương nhỏ nhất có
tính chất (i, j)-Ramsey. Chẳng hạn, ta có R(3, 3) = 6, vì 6 có tính chất (3,3)- Ramsey và những số nguyên dương nhỏ hơn nó không có tính chất này. 2.1.2. Tính chất số Ramsey Dưới đây ta trình bày một số tính chất cơ bản sau đây của số Ramsey R(i, j). 18 a) Số Ramsey khi đổi chỗ m và n thì không thay đổi, tức là R(n, m) = R(m, n). b) R(2, m) = R(m, 2) = m.
Kết hợp với tính chất a), ta có R(2, m) = R(m, 2), nên suy ra R(2, m) = R(m, 2) = m. c) Nếu m có tính chất (i, j) - Ramsey thì mọi số n > m cũng có tính chất này.
Chứng minh. Số m có tính chất (i, j)-Ramsey có nghĩa là nếu tô màu đầy đủ đồ
thị Km bởi hai màu xanh hoặc đỏ thì Km chứa Ki được tô màu xanh,
hoặc Kj được tô màu xanh. Dễ thấy, khi đó đồ thị đầy đủ Kn, n > m
được tô bởi hai màu xanh và đỏ sẽ chứa ít nhất Ki đỉnh được tô màu
xanh hoặc Kj đỉnh được tô màu đỏ. Tương tự ta dễ dàng chứng minh
được hai tính chất sau: d) Nếu m không có tính chất (i, j)-Ramsey thì mọi số n < m cũng không có tính chất này. e) Nếu i1 ≥ i2 thì R(i1, j) ≥ R(i2, j). 2.1.3. Tiệm cận số Ramsey Hình 2.1: Đỏ màu đậm, xanh màu nhạt Từ kết quả ở mục trước ta thấy 6 có tính chất (3,3)- Ramsey. Nhưng
vấn đề là 6 có phải là số nhỏ nhất có tính chất này hay không? Giả sử
các cạnh của K5 được tô màu như chỉ ra trong hình vẽ dưới đây (đỏ
- đậm , xanh - nhạt). Rõ ràng không thể tìm được K3 đỏ (đậm) cũng
như không thể tìm được K3 xanh (nhạt). Như vậy số 5 không có tính
chất (3,3)- Ramsey. Dễ thấy rằng mọi số nguyên dương nhỏ hơn 5 cũng
không có tính chất (3,3)-Ramsey. Vậy 6 là số nhỏ nhất có tính chất này.
(Hình 2.1) 19 Ví dụ 2.1 Tìm R(2, 7) là số nguyên dương nhỏ nhất có tính chất (2,7)-
Ramsey. Lời giải.
Trước hết ta tìm số nguyên dương n sao cho với mọi cách tô các
cạnh của Kn bởi hai màu xanh, đỏ, luôn tìm được hoặc K2 đỏ hoặc K7
xanh. R(2, 7) là số nhỏ nhất có tính chất này. Xét một cách tô màu (tuỳ
ý) các cạnh của K7. Rõ ràng hoặc là tìm được ít nhất một cạnh của K7
được tô màu đỏ, hoặc là tất cả các cạnh của nó đều được tô bởi màu
xanh. Nếu có cạnh tô màu đỏ thì rõ ràng ta có K2 đỏ. Còn nếu tất cả
các cạnh đều tô bởi màu xanh thì ta có K7 xanh. Vậy số 7 có tính chất
(2,7)-Ramsey, và vì thế R(2, 7) ≤ 7. Nhưng R(2, 7) không thể nhỏ hơn 7, bởi vì nếu tô tất cả các cạnh
của K6 bởi màu xanh, ta sẽ không tìm được K2 đỏ và cũng không tìm
được K7 xanh. Vậy R(2, 7) = 7. Sử dụng lập luận trong ví dụ vừa trình bày, ta có thể chỉ ra rằng: R(2, k) = k, với mọi k ≥ 2. Việc xác định số Ramsey R(i, j) đòi hỏi chúng ta phải tìm số nguyên dương nhỏ nhất có tính chất (i, j)-Ramsey. Một câu hỏi đặt ra là: Liệu số này có tồn tại với mọi i ≥ 2, j ≥ 2 hay không? Bổ đề và định lý dưới đây sẽ trả lời câu hỏi đặt ra. Bổ đề 2.1 Nếu i ≥ 3 và j ≥ 3 thì R(i, j) ≤ R(i, j − 1) + R(i − 1, j). (2.1) Chứng minh. Giả sử m = R(i, j − 1) + R(i − 1, j), ta chứng minh rằng m có tính
chất (i, j)-Ramsey. Giả sử các cạnh của Km được tô bởi hai màu xanh,
đỏ và v là một đỉnh của Km, ta phân tập đỉnh Km thành hai tập: A - tập tất cả các đỉnh nối với v bởi cạnh đỏ.
B - tập tất cả các đỉnh nối với v bởi cạnh xanh.
Do | A | + | B |=| A ∪ B |= m − 1 = R(i, j − 1) + R(i − 1, j) − 1,
nên hoặc | A |≥ R(i − 1, j), hoặc | B |≥ R(i − 1, j). Thực vậy nếu trái
lại ta có | A |< R(i − 1, j) và | B |< R(i − 1, j), từ đó suy ra điều vô lý
sau: m − 1 =| A ∪ B |< R(i, j − 1) + R(i − 1, j) − 1 = m − 1. Xét trường hợp | A |≥ R(i − 1, j). Gọi K|A| là bộ gồm tập đỉnh A
và tập cạnh là các cạnh nối các đỉnh trong A của Km. Ta sẽ chỉ ra rằng
K|A| hoặc chứa Ki đỏ hoặc chứa Ki xanh. Do | A |≥ R(i − 1, j) nên K|A| 20 hoặc chứa Ki−1 đỏ hoặc chứa Kj xanh. Nếu K|A| chứa Ki−1 đỏ thì bổ
sung vào nó đỉnh v và các cạnh nối v với các đỉnh trong A ta thu được
Ki đỏ. Vậy Km luôn chứa Ki đỏ hoặc chứa Ki xanh. Trường hợp | B |≥ R(i, j − 1) được xét tương tự. Như vậy m có
tính chất (i, j) Ramsey, từ đó ta suy ra bất đẳng thức (2.1) được chứng
minh. Từ kết quả của bổ đề, sử dụng phép qui nạp toán học ta có thể
chứng minh kết quả sau đây: Định lý 2.2 Nếu i ≥ 2, j ≥ 2 là các số nguyên dương thì luôn tìm dược
số nguyên (dươnq) với tính chất (i, j)-Ramsey, từ đó suy ra số R(i, j) là
tồn tại. Chứng minh. Giả sử P (n) là mệnh đề: Nếu i + j = n thì luôn tìm được số nguyên với tính chất (i, j) -Ramsey.
Khi n = 4 ta có i = j = 2. Từ kết quả của (2.1), ta suy ra P (4) đúng. Giả
sử P (n) đúng, ta chứng minh P (n + 1) cũng đúng. Giả sử i + j = n + 1,
ta suy ra i + (j − 1) = n và (i − 1) + j = n. Theo giả thiết qui nạp, luôn
tìm được số nguyên có tính chất (i, j − 1)- Ramsey và số nguyên với tính
chất (i − 1, j)- Ramsey. Từ đó suy ra các số R(i, j − 1) và R(i − 1, j)
tồn tại. Từ đó và từ bất đẳng thức (2.1) suy ra số R(i, j) cũng tồn tại.
Vậy P (n + 1) đúng. Theo nguyên lý qui nạp P (n) đúng với mọi i ≥ 2, j ≥ 2. Từ đó suy
ra R(i, j) luôn tồn tại với mọi i ≥ 2, j ≥ 2. Chúng ta đã có các kết quả
sau: R(2, k) = R(k, 2) = k.
R(3, 3) = 6. Khi i ≥ 2, j ≥ 2, việc tìm các số R(i, j) càng khó khi i, j càng lớn. Hiện
nay mới chỉ biết rất ít các số Ramsey.
Bảng dưới đây cho ta những giá trị đã biết của R(i, j). 21 3 4 5 6 102-169 43-52
57-94
≥ 76
≥ 94 i \ j
2
3
4
5
6
7
8
9 2
2
3
4
5
6
7
8
9 6
9
14
18
23
28
36 18
25-27
34-43
≥ 49
≥ 53
≥ 69 Các số R(3, 3), R(4, 3), R(5, 3) và R(4, 4) được tìm thấy từ năm
1955 bởi A. M. Gleason và R. E. Gleenwood, R(6, 3) - J. G. Kalbfleisch
năm 1966, R(3, 3) - J. E. Graver, J. Yackel năm 1968, R(8, 3) - B. M
cKay và Z. Ke Min mới gần đây, R(9, 3) - C. M. Grinstead và S. M.
Robets năm 1982. Các định lý trên cho ta biết sự tồn tại của số Ramsey, tuy nhiên
các định lý này không cho ta biết cách tính số Ramsey. Nói chung không
có công thức tính số Ramsey, vì vậy người ta cố gắng đi tìm các công
thức đánh giá số Ramsey. Các đánh giá này hiện nay cũng chưa nhiều
và cho đến hiện nay chưa có một công thức chính xác nào để tính số
Ramsey. Trong mục này ta trình bày một số giá trị của số Ramsey và
một số công thức đánh giá số Ramsey. Định lý 2.3 Với mọi số nguyên p, q ≥ 2 ta có R(s, t) ≤ R(s, t − 1) +
R(s − 1, t). Chứng minh định lý này đã được cho ở mục trước. Ví dụ 2.2 : R(3, 4) ≤ R(3, 3) + R(2, 4) ≤ 6 + 4 = 10. mà R(3, 4) = 9, nên:
R(4, 4) ≤ R(3, 4) + R(4, 3) ≤ 9 + 9 = 18 và R(4, 4) = 18. Vậy chúng ta mới đánh giá được cận trên của số Ramsey, cận dưới
của nó là một bài toán khó. Erd˝os đã đưa ra giới hạn dưới của số Ramsey
với trường hợp i = j như sau: R(s, s) > 2(s−1)(cid:30)2. Sau đây ta chứng minh
khẳng định trên. 22 Xét đồ thị đầy đủ K được tô bởi 2 màu xanh và đỏ. Khi đó xác 1
2 xuất đỉnh x của đồ thị được tô màu đỏ là
. Vậy xác suất các đỉnh Ks
được tô màu đỏ là 2−s(s−1)/2. Do đó xác suất Ks đơn sắc là 21−s(s−1)/2.
Ta chọn n đủ lớn để tồn tại một cách tô màu các đỉnh Kn sao cho nó
là tập đơn sắc. Xác suất tồn tại một đồ thị con đơn sắc Ks trong Kn
s )21−s(s−1)/2. Chọn n đủ lớn để xác suất nhỏ hơn 1. Ta lấy
là: P (Ks) = (n
n = 2(s−1)/2. Khi đó ta có điều phải chứng minh. Sau đây ta đưa ra công thức đánh giá cận dưới của số Ramsey trong trường hợp đồ thị được tô bởi k màu. √ st)1/(s+t).((s + t)/e2).k(st−1)/(s+t) Định lý 2.4 Ta có: R(Ks,t; k) > (2π
với {k1, k2, k3, · · · · · · , kk} là tập hợp các màu được tô. Chứng minh Xác suất để đỉnh x (x ∈ Ks,t) được tô bởi màu k1 là: 1
k ). √ . Xác
suất để Ks,t được tô bởi màu k1 là: k−st. Xác suất để Ks,t đơn sắc
là: k.k−st = k1−st. Xác suất các đỉnh của ks,t mà được chọn từ Kn là:
s+t)(s+t
(n
s
Khi đó xác suất để tồn tại đồ thị đơn sắc trong Kn là: P (Ks,t) =
)k1−st. Chúng ta chọn n đủ lớn để xác suất bé hơn 1 khi đó ta
s+t)(s+t
(n
s
st)1/(s+t).((s + t)/e2).k(st−1)/(s+t) và có một màu được tô mà
có: n ≤ 2π
không có một đồ thị con đơn sắc nào tồn tại. Do dó ta có R(Ks,t; k) > n. 2.1.4. Số Ramsey cho trường hợp tổng quát Các số Ramsey giới thiệu trong mục trước chỉ là một trong họ các
số Ramsey. Trong mục này chúng ta sẽ xét một họ các số Ramsey tổng
quát hơn.
a) Trường hợp tổng quát hóa nhiều màu để tô cho các đỉnh của Kn. Chẳng hạn nếu ta tô màu các cạnh của Kn bởi ba màu xanh, đỏ,
tím, thì số n ít nhất phải là bao nhiêu để chắc chắn tìm được hoặc K3
đỏ, hoặc K3 xanh hoặc K3 tím? Số n nhỏ nhất có tính chất như vậy
được ký hiệu là R(3, 3, 3; 2). Con số 2 được viết như là một thành phần
của R(3, 3, 3; 2) bởi vì các cạnh (đối tượng được tô màu) được xác dịnh
bởi 2 đỉnh. Con số 2 này cũng có thể thay bởi một số nguyên dương bất
kỳ. Ba số 3 cũng có thể thay bởi các số nguyên dương tuỳ ý để có thể
thu được một họ mới các số Ramsey. 23 Ví dụ 2.3 . R(5, 4, 7; 2) là số nguyên dương nhỏ nhất n sao cho với mọi
cách tô màu các cạnh của Kn bởi 3 màu xanh, đỏ, tím thì trong Kn luôn
chứa hoặc K5 đỏ hoặc K4 xanh hoặc K7 tím hoặc các hoán vị khác của
các màu xanh, đỏ, tím cho K5, K4, K7 (vì các màu có vai trò như nhau). Định nghĩa 2.4 Giả sử i1, i2, · · · , in là các số nguyên dương, trong
đó ij ≥ 2, với mọi số j số nguyên dương m được gọi là có tính chất
(i1, i2, · · · , in; 2)-Ramsey nếu với mọi cách tô màu các cạnh của Kn bởi
n màu 1, 2, . . . , n luôn tìm được trong nó Kij màu ij với ít nhất một j
nào đó. Số nguyên dương nhỏ nhất với tính chất (i1, i2, ..., in; 2)-Ramsey
được gọi là số Ramsey R(i1, i2, ..., in; 2). Chú ý nếu n = 2, số Ramsey R(i1, i2, ..., in; 2) chính là số Ramsey
R(i1, i2) trong mục trước. Chúng ta biết rất ít về số Ramsey R(i1, i2, ..., in; 2) khi n ≥ 3.
Tuy nhiên nếu ij = 2 với mọi j thì người ta chứng minh được rằng:
R(2, ..., 2; 2) = 2. Khi mỗi ij ≥ 3, cho tới thời điểm hiện tại mới xác định
được giá trị R(3, 3, 3; 2) = 17 (bởi R. E. Greenwood A. M. Gleason). Định lý 2.5 Cho r là số tự nhiên, p1, p2, ..., pr, khi đó tồn tại số tự nhiên
nhỏ nhất R(p1, p2, ..., pr) chỉ phụ thuộc vào các số p1, p2, ..., pr sao cho
với mọi đồ thị đầy đủ n đỉnh, r màu, n ≥ R(p1, p2, ..., pr) luôn tồn tại
một đồ thị con đầy đủ p1 đỉnh mà tất cả các cạnh được tô màu k1, hoặc
p2 đỉnh mà tất cả các cạnh được tô màu k2, hoặc .... hoặc pr đỉnh mà
tất cả các cạnh được tô màu kr. Chứng minh. Ta sẽ chứng minh định lý trên bằng phương pháp qui nạp theo r.
Với r = 1, R(p1) = p1. Với r = 2, đây chính là Định lý Ramsey tô màu
đồ thị bằng 2 màu. Giả sử định lý đúng đến r − 1. Ta sẽ chứng minh định lý đúng đến
r . Theo giả thiết tồn tại q = R(p1, p2, · · · , pr − 1) sao cho mọi đồ thị
đầy đủ q đỉnh r − 1 màu luôn tồn tại một đồ thị con đầy đủ p1 đỉnh mà
tất cả các cạnh được tô bởi màu k1, hoặc p2 đỉnh mà tất cả các cạnh
được tô màu k2, ... hoặc pr − 1 đỉnh mà tất cả các cạnh được tô màu
kr − 1. Ta lấy kr là màu đỏ, còn các màu k1, k2, ..., kr − 1 là màu xanh.
Theo Định lý Ramsey cho trường hợp 2 màu, tồn tại số n = R(q, pr)
sao cho trong mọi đồ thị đầy đủ n đỉnh hai màu, luôn tồn tại một đồ
thị con đầy đủ q đỉnh mà tất cả các cạnh được tô màu xanh, hoặc pr
đỉnh mà tất cả các cạnh được tô màu đỏ. 24 Vậy luôn tồn tại số tự nhiên R(p1, p2, ..., pr), sao cho với mọi đồ thị
đầy đủ n đỉnh r màu, n ≥ R(p1, p2, ..., pr), luôn tồn tại một đồ thị con
đầy đủ p1 đỉnh, mà tất cả các cạnh được tô màu k1, hoặc p2 đỉnh mà tất
cả các cạnh được tô màu k2, ... hoặc pr đỉnh mà tất cả các cạnh được
tô màu kr. Hình 2.2: Đồ thị Clebsch Bài toán 2.2 Chứng minh R(3, 3, 3; 2) = 17. Ta thấy trên đồ thị Clebsch có 16 đỉnh các cạnh được tô bởi 3 màu
xanh, đỏ, vàng nhưng không có tam giác nào có 3 cạnh cùng màu. Suy
ra R(3, 3, 3; 2) > 16. Bây giờ ta xét một đồ thị đầy đủ 17 đỉnh. Các cạnh của đồ thị
được tô bởi một trong ba màu xanh, đỏ, vàng. Ta cần chứng minh trong
đồ thị tồn tại ba đỉnh mà các cạnh được nối với nhau bởi cùng một
màu. Kí hiệu một đỉnh là A. Vì A nối với 16 đỉnh còn lại bởi ba màu
nên theo nguyên tắc Dirichlet tồn tại 6 đỉnh nối với A bởi cùng một
màu. Giả sử sáu đỉnh là B, C, D, E, F, G nối với A bởi màu xanh. Nếu
trong sáu đỉnh có hai đỉnh nối với nhau bởi màu xanh, giả sử là B, C
thì ba đỉnh A, B, C được nối với nhau cùng một màu. Nếu trong sáu
đỉnh không có hai đỉnh nào nối với nhau bởi màu xanh. Suy ra trong
6 đỉnh B, C, D, E, F, G các cạnh được nối với nhau bởi hai màu đỏ và
vàng theo bài toán (2.1) tồn tại ba đỉnh mà các cạnh được nối với nhau
bởi một màu. Vậy trong 17 đỉnh luôn tồn tại ba đỉnh mà các cạnh được nối với nhau bởi cùng một màu. Suy ra R(3, 3, 3; 2) = 17. 25 b) Trường hợp chia Kn thành các họ. Trươc tiên, ta quay trở lại với trường hợp của đồ thị K6 với với tập
đỉnh V , ta xét tất cả các tập con 2 phần tử của V (tức là các cạnh của
K6) và chia các tập con này ra làm hai họ C1 và C2. Số 6 có tính chất
(3, 3)-Ramsey nếu và chỉ nếu một trong hai khả năng sau xảy ra: i) Tìm được tập con 3 phần tử của V sao cho mọi tập con 2 phần tử của nó đều thuộc vào C1. ii) Tìm được tập con 3 phần tử của V sao cho mọi tập con 2 phần tử của nó đều thuộc vào C2. Nếu coi C1 là tập các cạnh được tô màu đỏ và C2 là tập các cạnh
được tô màu xanh, thì rõ ràng ta có tam giác đỏ khi và chỉ khi điều kiện
i) được thực hiện và có tam giác xanh khi và chỉ khi điều kiện ii) được
thực hiện. Tuy nhiên ở đây chúng ta không cần dùng đến khái niệm
cạnh. Các tính chất này có thể được phát biểu trong ngôn ngữ tập hợp
và các tính chất của một họ các tập con của nó. Cách mô tả này cho
phép xét việc phân các tập con có kích thước r tùy ý (không phải chỉ
có 2) ra thành một số các họ con (không nhất thiết chỉ phân làm 2 họ
C1 và C2 như trong ví dụ vừa nêu). Ta đi đến định nghĩa tổng quát của
số Ramsey. Định nghĩa 2.5 Giả sử i1, i2, · · · , in, r là các số nguyên dương, trong
đó n ≥ 2 và ij ≥ r với mọi số j. Số nguyên dương m được gọi là có tính
chất (i1, i2, · · · , in; r)-Ramsey nếu mệnh đề sau đúng: Nếu S là tập m
phần tử và n họ C1, C2, · · · , Cn, là các tập con r phần tử, thì với một j
nào đó tìm đươc tập con của S có lực lượng ij sao cho mỗi tập con r phần
tử của nó đều thuộc vào Cj. Số nguyên dương nhỏ nhất có tính chất
(i1, i2, · · · , in; r)–Ramsey được gọi là số it Ramsey R(i1, i2, · · · , in; r). Định lý 2.6 (Định lý Ramsey 1930) Nếu i1, i2, · · · , in, r là các số
nguyên dương, trong đó n ≥ 2 và ij ≥ r với mọi số j thì số Ramsey
R(i1, i2, · · · , in; r) luôn tồn tại. Khi r = 1 số R(i1, i2, · · · , in; 1) có thể xác định khá dễ dàng, bởi vì
chúng ta chỉ phải xét các tập con một phần tử của S. Công thức tính
cụ thể trong trường hợp này được cho bởi định lý dưới đây: 26 Định lý 2.7 : R(i1, i2, · · · , in; 1) = i1 + i2 + · · · + in − (n − 1). Chứng minh. Đặt m = i1 + i2 + · · · + in − (n − 1). Trước hết ta chỉ ra rằng m
có tính chất (i1, i2, · · · , in; r) – Ramsey. Lấy S là tập m phần tử và chia
các tập con 1 phần tử của nó ra làm n lớp C1, C2, · · · , Cn. Trước hết
nhận thấy rằng phải tìm được chỉ số j0 sao cho | Cj0 |≥ ij0 (nếu trái
lại | Cj |< ij với mọi j, thì | Cj |≤ ij − 1). Suy ra: m =| C1 | + · · · + |
Cn |< (i1 − 1) + · · · + (in − 1) = i1 + i2 + · · · + in − n = m − 1. Nếu
ta lấy ij0 phần tử của Cj0 thì ta có tập con của S với lực lượng ij0 sao
cho mọi tập con 1 phần tử của nó đều thuộc Cj0. Điều đó chứng tỏ rằng
R(i1, i2, · · · , in; 1) ≤ i1 + i2 + · · · + in − (n − 1). Bây giờ ta sẽ chỉ ra rằng m − 1 = i1 + i2 + · · · + in − n không có tính
chất (i1, i2, · · · , in; r)-Ramsey. Lấy tập S gồm i1 + i2 + · · · + in − n phần
tử. Phân các tập con một phần tử của nó vào n lớp C1, C − 2, · · · , Cn
sao cho | Cj |= ij − 1. Rõ ràng với cách phân chia này không thể tìm
được tập con của S có lực lượng sao cho mọi tập con một phần tử của
nó thuộc cùng một lớp Cj. Khi i1 = i2 = · · · = in = 2, ta có R(2, 2, ..., 2; 1) = n + 1. c) Trường hợp tổng quát. Ở hai mục trên, ta đã thấy Định lý Ramsey có thể phát biểu trên
ngôn ngữ chia tập hợp thành hai lớp hoặc ngôn ngữ đồ thị hai màu. Có
thể đặt câu hỏi là: "Có thể tổng quát hóa Định lý Ramsey khi tập hợp
được chia thành nhiều lớp hoặc trên ngôn ngữ đồ thị nhiều màu hay
không?". Giả sử S là tập hợp gồm s phần tử, ký hiệu πr(S)là họ tất cả
các tập con của S mỗi tập có đúng r phần tử r ≥ 1. Ta nói họ πr(S)
được phân hoạch thành hai họ các tập hợp A và B nếu A và B khác
rỗng và thỏa mãn điều kiện: πr(S) = A ∪ B; A ∩ B = ∅. Định lý 2.8 (Định lý Ramsey tổng quát) Giả sử S là tập hợp gồm s
phần tử và πr(S) là họ tất cả các tập con gồm r phần tử của S, r ≥ 1. Giả
sử rằng chúng ta có cách phân hoạch tập hợp πr(S) = A1 ∪ A2 ∪ · · · ∪ An,
sao cho mọi lớp Ai khác rỗng và mỗi tập con r phần tử của S thuộc
vào chỉ một tập Ai(Ai ∩ Aj = ∅ với mọi i (cid:54)= j). Giả sử k1, k2, · · · , kn là
các số nguyên sao cho r ≤ ki ≤ s với mọi i = 1, 2, ..., n. Khi đó tồn tại
số nguyên R(k1, k2, ..., kn; r) chỉ phụ thuộc vào n, k1, k2, ..., kn và r, mà
không phụ thuộc vào tập S sao cho nếu s ≥ R(k1, k2, ..., kn; r) thì tồn tại
một tập con Pi gồm ki phần tử của S mà mọi tập con r phần tử của Pi 27 thuộc vào tập Ai với ít nhất một giá trị i, 1 ≤ i ≤ n. Chứng minh. 2.2. Tập đơn sắc Ta sẽ chứng minh theo qui nạp với n = 2 làm điểm xuất phát. Giả sử
định lý đã được chứng minh cho phép chia tập hợp πr(S) vào n − 1 hoặc
ít hơn các họ tập hợp. Xét phép chia: πr(S) = (A1 ∪A2 ∪· · ·∪An−1)∪An.
Giả sử ρ = R(k1, k2, ..., kn−1; r), s ≥ R(ρ, kn; r) và S là tập gồm s phần
tử. Khi ấy hoặc là S chứa tập con Pn gồm kn phần tử, mọi tập con r
phần tử của nó thuộc nA. Trong trường hợp này định lý được chứng
minh. Hoặc là S chứa tập con T gồm ρ phần tử, mọi tập con r phần tử
của nó thuộc tập A1 ∪ A2 ∪ · · · ∪ An−1. Theo cách chọn ρ và theo qui
nạp, tập T phải chứa ít nhất một tập con Pi gồm ki phần tử, mọi tập
con r phần tử của nó thuộc họ Ai với một giá trị i nào đó, 1 ≤ i ≤ n − 1.
Nhưng Pi cũng là tập con của tập S do đó trong mọi trường hợp S chứa
tập một tập con Pi gồm ki phần tử, mọi tập con r phần tử của nó thuộc
họ Ai với một giá trị i nào đó 1 ≤ i ≤ n. Định lý được chứng minh. 2.2.1. Định nghĩa Một tập con Y của tập X được gọi là đơn sắc trong một cách tô màu tập X nếu mọi phần tử của Y đều có cùng màu. Theo khái niệm trên và áp dụng Định lý Ramsey ta có: Giả sử
c : A(r) → {1, 2, ..., k} là một phép tô màu cho các tập con lực lượng
r(1 ≤ r < ∞) của một tập vô hạn A bằng k màu. Khi đó A chứa một
tập con đơn sắc vô hạn. Mở rộng hơn nữa theo Định lý Van der Waerden năm 1927: Cho
m, k ∈ N. Khi đó tồn tại một số nguyên N = N (m, k) sao cho với mọi
n ≥ N , nếu tập {1, 2, . . . , n} được tô bởi k màu thì luôn tồn tại một
cấp số cộng đơn sắc trong [n] có độ dài m. Vậy theo Định lý Ramsey và Định lý Van der Waerden thì chắc
chắn tìm được một tập đơn sắc bằng cách tô màu tập {1, 2, . . . , n} với
n đủ lớn bởi k màu. 28 2.2.2. Tập đơn sắc và các vấn đề liên quan Cũng theo hai Định lý Ramsey và Định lý Van der Waerden ở trên
thì muốn tìm được tập đơn sắc phải tìm đươc số Van der Waerden hoặc
số Ramsey. Ở đây ta phát biểu Định lý Van der Waerden mạnh hơn
như sau: "Cho m, k là các số tự nhiên. Khi đó tồn tại một số nguyên
dương N = N (m, k) sao cho với mọi n ≥ N nếu [n] được tô bởi k màu
thì luôn tồn tại một cấp số cộng độ dài m, sao cho mọi phần tử của
nó tạo thành một tập đơn sắc", có nghĩa là tồn tại a, d ∈ N sao cho
a, a + d, a + 2d, . . . , a + (m − 1)d có cùng một màu. Định lý trên hoàn toàn có thể chứng minh bằng phương pháp qui nạp toán học và trong Chương 1 ta đã có một cách chứng minh. Hệ quả 2.1 (Định lý Schur 1916) Cho k là số tự nhiên, khi đó tồn
tại một số nguyên dương N = N (k) sao cho với mọi n ≥ N để nếu [n]
được tô bởi k màu khác nhau thì luôn tồn tại x, y, z thuộc [n] được tô
cùng một màu, thỏa mãn x + y = z. Hệ quả trên có thể được chứng minh bởi Định lý Ramsey. Định nghĩa 2.6 Lấy (cid:96), r ∈ N. Một đường thẳng đơn sắc, hoặc đơn giản,
một đường thẳng trong [(cid:96)]r là một tật hợp L ∈ [(cid:96)]r sao cho đối với tập
hợp không rỗng nào đó I = {i1, i2, ..., it} và aj ∈ [(cid:96)]r nào đó sao cho mọi
j /∈ I, ta có: L = {x ∈ [(cid:96)]r : xj = aj, ∀j /∈ I, và xi1 = · · · = xit}. Cho (cid:96) ≥ 2 tập I là tập hợp các phần tử dương của L và aj j /∈ I là
tập hợp các phần tử âm của L. Lấy L− và L+ biểu thị các điểm của L
sao cho L− = 1 và L+ = (cid:96) với mọi i ∈ I. L− và L+ là các điểm cuối của
L, L− là các điểm đầu và L+ là các điểm cuối của L, ở đây chúng ta có
| L |= (cid:96). Ví dụ 2.4 Trong [3]2 , ví dụ các đường thẳng là: L = {(1, 3), (2, 3), (3, 3)}, I = {1};
L = {(2, 1), (2, 2), (2, 3)}, I = {2};
L = {(1, 1), (2, 2), (3, 3)}, I = {1, 2}. Chú ý rằng {(1, 3), (2, 2), (3, 3)} không là một đường thẳng (mặc dù nó xuất hiện một lần). Trong [5]3, một số các đường thẳng là:
L = {(4, 1, 1), (4, 2, 1), (4, 3, 1), (4, 4, 1), (4, 5, 1)}, I = {2};
L = {(1, 5, 1), (2, 5, 2), (3, 5, 3), (4, 5, 4), (5, 5, 5)}, I = {1, 3}; 29 L = {(1, 1, 1), (2, 2, 2), (3, 3, 3), (4, 4, 4), (5, 5, 5)}, I = {1, 2, 3}.
Trong các trường hợp khác, L− và L là phần tử đầu tiên và phần tử cuối cùng trong danh sách tương ứng của L. Định lý 2.9 (Định lý Hales - Jewett, 1963) Cho l, k là các số tự
nhiên, khi đó tồn tại một số tự nhiên N = N ((cid:96), k) sao cho với mọi
r ≥ N , nếu [(cid:96)]r được tô với k màu thì luôn tồn tại một đường tổ hợp
đơn sắc trong [(cid:96)]r. i }, Lj\{L+ Chứng minh. Chứng minh định lý này tương tự Định lý Van der Waerden. Lấy
một màu của [(cid:96)]r, chúng ta nói rằng L1, L2, ..., Ls hội tụ f ∈ [(cid:96)]r, nếu
i = f với mọi i. L1, L2, ..., Ls là màu hội tụ tại f nếu mọi Li\{L+
L+
i } là
đơn sắc và Li\{L+
j } có các màu khác nhau với mọi i khác j.
Chúng ta sử dụng phép qui nạp với (cid:96). Định lý đúng với (cid:96) = 1, bây giờ
với (cid:96) ≥ 2 và giả sử định lý đúng với (cid:96) − 1 với bất kỳ số lượng màu. Ta
chứng minh định lý đúng với (cid:96) với bất kỳ số lượng màu từ đó định lý
được chứng minh. Bổ đề 2.2 Với mọi 1 ≤ s ≤ k, tồn tại r = r((cid:96), s, k) sao cho nếu [(cid:96)]r bất
kỳ được tô bởi k màu thì tồn tại một đường đơn sắc trong [(cid:96)]r, hoặc tồn
tại s đường đơn sắc hội tụ trong [(cid:96)]r. Chứng minh bổ đề. Lấy s = k, chúng ta hoặc có một đường đơn sắc hoặc k đường đơn
sắc hội tụ. Điều đó cho chúng ta một đường đơn sắc, không quan tâm
màu hội tụ của k trên đường đó. Để chứng minh bổ đề. Chúng ta sử
dụng qui nạp s. . Bổ đề rõ ràng đúng với s = 1 khi [(cid:96)]N (cid:48) Với s = 1 bởi giả thiết qui nạp với (cid:96) khi đó tồn tại N (cid:48) = N (cid:48)((cid:96) − 1, k)
sao cho nếu [(cid:96) − 1]N (cid:48)
được tô bởi k màu thì đó là một đường thẳng đơn
sắc trong [(cid:96) − 1]N (cid:48)
được tô bởi k
màu và vì vậy chúng ta có thể lấy r = N (cid:48). Bây giờ lấy s ≥ 2 và giả sử
rằng bổ đề đúng với s − 1 tức là r(cid:48) = r(cid:48)((cid:96), s − 1, k) là giá trị cần tìm. Ta
chứng minh bổ đề đúng với s. Tồn tại N ” = N ”((cid:96) − 1, k(cid:96)r(cid:48)
) sao cho nếu
[(cid:96) − 1]N ” được tô bởi k(cid:96)r(cid:48)
màu thì f tồn tại một đường đơn sắc trong
[(cid:96) − 1]N ”. Chúng ta chỉ ra r = r(cid:48) + N ” là giá trị chấp nhận được cho s.
Thật vậy lấy k màu được tô của [(cid:96)]r = [(cid:96)]r(cid:48)+N ” chúng ta kết thúc nếu
[(cid:96)]r chứa một đường đơn sắc, chúng ta có [(cid:96)]r = [(cid:96)]r(cid:48)+N ” = [(cid:96)]r(cid:48)
× [(cid:96)]N ”.
Điều này có nghĩa rằng chúng ta có thể tưởng tượng [(cid:96)]r như [(cid:96)]N ” với 30 1 = · · · = L+ i , L−) véc tơ cuối (L+ được tô bởi k(cid:96)r(cid:48) màu, với mọi k(cid:96)r(cid:48) mọi véc tơ của [(cid:96)]N ” được thay thế bằng bản sao [(cid:96)]r(cid:48)
. Thực vậy chúng
ta có thể viết mọi véc tơ v ∈ [(cid:96)]r với dạng v = (v(cid:48), v”) trong đó v(cid:48) ∈ [(cid:96)]r(cid:48)
và v” ∈ [(cid:96)]N ”, do đó v” chứng tỏ rằng vị trí của bản sao của [(cid:96)]r(cid:48)
trong
. Có k(cid:96)r(cid:48)
[(cid:96)]N ” và v(cid:48) bao gồm tọa độ của v nằm trong bản sao của [(cid:96)]r(cid:48)
cách tô màu bản sao [(cid:96)]r(cid:48)
, chúng ta có thể tưởng tượng toàn bộ cấu trúc
[(cid:96)]r như một [(cid:96)]r(cid:48)
màu tương ứng với
một trạng thái của [(cid:96)]r(cid:48)
được tô bởi k màu. Bằng cách định nghĩa N ”
chúng ta có (cid:96)−1 bản sao được tô màu giống hệt nhau của [(cid:96)]r(cid:48)
trong [(cid:96)]r.
Vậy khi đó chúng được xác định với các vec tơ tương ứng của nó trong
[(cid:96)]N ”, các véc tơ trở thành L \ {L+} mặc dù một vài đường L ∈ [(cid:96)]N ”.
Lấy I là tập hợp các véc tơ của L có tọa độ dương, hơn nữa theo cách
định nghĩa r(cid:48) hoặc có một đường đơn sắc trong mỗi (cid:96) − 1 bản sao được
tô màu tương tự nhau của [(cid:96)]r(cid:48)
hoặc có s − 1 đường đơn sắc hội tụ trong
mỗi bản sao. Nếu vấn đề trước khi lấy L(cid:48) là đường đơn sắc trong bản
sao của [(cid:96)]r(cid:48)
tương ứng với L− với các tọa độ dương trong tập I (cid:48). Nhưng
sau đó, đường trong [(cid:96)]r, với các tọa độ dương I ∪ I (cid:48) và toàn bộ các véc
tơ đầu và véc tơ cuối là (L(cid:48)−, L−) và (L(cid:48)+, L+) là đơn sắc, một sự mâu
thuẫn. Vì vậy sự khẳng định cuối đúng. Lấy L1, ..., Ls−1 là các đường
đơn sắc có tọa độ dương I1, ..., Is−1 hội tụ tại f trong bản sao của [(cid:96)]r(cid:48)
tương ứng với L−, ví dụ f = L+
s−1. Chú ý rằng f có màu
khác với L1, ..., Ls−1, bây giờ với mọi 1 ≤ i ≤ s − 1 xét đường L(cid:48)
i trong
[(cid:96)]r với véc tơ đầu tiên (L−
i , L+ = (f, L+) và các
i là màu hội tụ tại (f, L+) hơn nữa đường
tọa độ dương I ∪ Ii. Vì vậy L(cid:48)
s trong [(cid:96)]r với véc tơ đầu và véc tơ cuối (f, L−), (f, L+) và các tọa độ
L(cid:48)
dương I. s \ {L(cid:48)+ s } là đơn sắc với các màu khác nhau từ L(cid:48) 1, ..., L(cid:48) i \ {L(cid:48)−
i }
với 1 ≤ i ≤ s − 1 vì vậy L(cid:48)
s là một tập hợp các đường đơn sắc hội
tụ trong [(cid:96)]r và hội tụ tại (f, L+). Bổ đề được chứng minh bởi qui nạp
theo s. Như vậy L(cid:48) Định nghĩa 2.7 Số nguyên lớn nhất N = N ((cid:96), k) thỏa mãn Định lý
Hales-Jewett được gọi là số Hales-Jewett, ký hiệu HJ((cid:96), k). Chứng minh Định lý Van der Waerden từ Định lý Hales- Jewett. Với m, k đã cho ta chứng minh N = m.HJ(m, k). Lấy n ≥ N khi đó
c : [n] −→ {1, ..., k} được tô bởi k màu cho trước xác định c(cid:48) : [m]n(cid:48)
−→
{1, ..., k} được tô bởi k màu với c(cid:48)((x1, ..., xn(cid:48))) = c(x1 + · · · + xn(cid:48)) khi
n(cid:48) = HJ(m, k) theo định lý (2.9), [m]n(cid:48)
chứa một đường đơn sắc L trong 31 cách tô màu C (cid:48). Đường L tương ứng tới một cấp số cộng đơn sắc có độ
dài m trong [n], trong cách tô màu c, ở đó mỗi phần tử là tổng của các
tọa độ của một véc tơ trong L (phần tử đầu tiên chứa tổng các tọa độ
của L−) và sự khác nhau thông thường là kích thước của tập hợp L chứa
các tọa độ dương. Một nghiên cứu khác về Định lý Hales- Jewett là chúng ta có thể
sử dụng nó để chứng minh Định lý Gallai một định lý có kết quả rất
hữu ích và chứng minh ngay được Định lý Van der Waerden. Trước khi
chúng ta phát biểu và chứng minh Định lý Gallai chúng ta có định nghĩa
sau: Định nghĩa 2.8 Lấy X = N hoặc X = R và S ⊂ X r với n ∈ N. Một
bản sao đồng dạng của S là một tập S(cid:48) ⊂ X r có dạng: S(cid:48) = aS + b =
{av + b : v ∈ S}, với a ∈ X, a (cid:54)= 0 và b ∈ X r. Định lý 2.10 (Định lý Gallai) Giả sử X = N hoặc X = R, r, k ∈ N
và S ⊂ X r là một tập hữu hạn. Khi đó nếu tập X r được tô bởi k màu
thì luôn tồn tại một bản sao đơn sắc đồng dạng của S trong X r. Định lý Gallai được biết đến như Định lý Grunwald hoặc Định
lý Gallai-Witt. Chúng ta coi Định lý Gallai là một trường hợp tổng
quát của Định lý Van der Waerden bằng cách lấy X = N, r = 1 và
S = {1, . . . , m} trong đó m là độ dài của cấp số cộng đơn sắc mà chúng
ta muốn tìm thấy trong Định lý Van der Waerden.
Chứng minh. j /∈I j /∈I s(aj), · · · , |I|s(m) + (cid:80) s(aj), |I|s(2) + (cid:80) Lấy S = {s(1), ..., s(m)} với m ∈ N và n = HJ(m, k) với c :
X r −→ {1, ..., k} được tô bởi k màu xác định c(cid:48) : [m]n −→ {1, ..., k} với
c(cid:48)(x) = c(s(x1)+· · ·+s(xn)) theo định lý (2.9) [m]n chứa một đường đơn
sắc trong việc tô màu c(cid:48). Nó dễ dàng để tìm thấy đường L tương ứng với
bản sao đơn sắc và đồng dạng của S trong X r , liên quan đến việc tô màu
c bởi k màu. Thực vậy nếu I là tập hợp các tọa độ dương của L và aj ∈
[m] , j /∈ I là các tọa độ còn lại của L. Khi đó liên quan đến việc tô màu
c, tập hợp: {|I|s(1) + (cid:80)
s(aj)}
j /∈I là một bản sao đồng dạng đơn sắc của S trong X r. Ví dụ sau đây cho ta thấy ứng dụng của Định lý Gallai và Định lý Van der Waerden trong giải toán. Ví dụ 2.5 Giả sử tập hợp các số thực được chia làm hai tập con không
giao nhau tùy ý. Khi đó, với mỗi cặp số nguyên dương (m, n) luôn tồn 32 tại ba số thực x, y, z cùng thuộc một tập con thỏa mãn x < y < z và
m(z − y) = n(y − x). Chúng ta có thể giải quyết bài toán này một cách đơn giản bằng
cách sử dụng Định lý Gallai. Chú ý rằng trong bài toán này tập số
ở đây là số thực còn theo định lý là số tự nhiên. Vì vậy chúng ta có
thể xem xét bài toán như việc giải quyết bài toán tô màu tập số tự
nhiên bởi 2 màu. Theo Định lý Gallai với X = N, r = 1, k = 2 và
S = {1, m + 1, m + n + 1}, có một lớp màu chứa một bản sao đồng dạng
của S đó là một tập hợp có dang {a + b, a(m + 1) + b, a(m + n + 1) + b}
với a, b là số nguyên và a lớn hơn hoặc bằng 1. Chúng ta kết thúc với
x = a + b, y = a(m + 1) + b và z = a(m + n + 1) + b khi đó chúng ta có
m(z − y) = amn và n(y − x) = amn. Suy ra điều phải chứng minh. Ngoài ra, ta có thể giải quyết bài toán trên bằng cách sử dụng Định
lý Van der Waerden. Theo Định lý này, ta có một lớp màu chứa một
cấp số cộng có độ dài m + n + 1 với phần tử đầu tiên a ∈ N và công sai
d là số tự nhiên. Sau phần tử a là a + md và a + (m + n)d đều thuộc cấp
số cộng số học. Vì vậy lấy x = a, y = a + md và z = a + (m + n)d khi
đó cho ta m(z − y) = dnm và n(y − x) = dmn. Suy ra điều phải chứng
minh. Ví dụ sau đây minh họa cho Định lý Van der Waerden trong trường hợp n = 9. Ví dụ 2.6 Với mỗi cách tô màu các số 1, 2, 3, 4, 5, 6, 7, 8 và 9 bởi hai
màu đỏ và xanh, thì tồn tại ba số được tô cùng màu lập thành cấp số
cộng. Hình 2.3 Lời giải.
Giả sử rằng việc tô màu dãy số trên không có cấp số cộng đơn sắc
nào có 3 phần tử và số 5 được tô màu đỏ. Khi đó, rõ ràng các số 3 và 7
không thể cùng được tô bởi màu đỏ. Giả sử rằng một trong hai số 3 và
7 là màu đỏ, khi đó theo tính đối xứng, chúng ta có thể giả sử rằng 3 là
đỏ khi đó 1, 4 và 7 là màu xanh (Hình 2.3). Chúng ta thu được một cấp
số cộng đơn sắc màu xanh (Hình 2.4). Mâu thuẫn với giả sử ở trên. 33 Hình 2.4 Vì vậy, chúng ta tô màu 3, 5 và 7 dưới dạng như Hình 2.5, tức là Hình 2.5 số 5 màu đỏ và hai số 3 và 7 là màu xanh. Hình 2.6 Khi đó các số 1, 5, 9 không thể được tô hết bởi màu đỏ. Do đó 1
hoặc 9 là màu xanh. Do tính đối xứng, chúng ta có thể giả sử rằng 1
là màu xanh. Trong Hình 2.6, ta thấy tất cả các khả năng xảy ra trong
trường hợp này. Ta thấy rằng, trong tất cả các trường hợp, ta đều có
một cấp số cộng đơn sắc với độ dài bằng 3. Vì vậy mâu thuẫn với giả
sử trên. Suy ra điều phải chứng minh. 34 Luận văn đã trình bày được một số vấn đề sau: 1. Trình bày về Định lý Van der Waerden và Định lý Szemerédi về cấp
số cộng và mật độ cấp số cộng trong tập các số tự nhiên liên tiếp. 2. Trình bày khái niệm hệ phủ đồng dư và ứng dụng của hệ phủ đồng dư trong giải toán. 3. Trình bày một số kết quả về số Ramsey và tập đơn sắc trong bài toán tô màu. 35 Tiếng Việt [1] Hoàng Đức Tân (2017), "Định lý Van der Waerden về cấp số cộng
và một số tổng quát hóa", dịch từ bài viết của M. A Lukomskaia,
Tạp chí Epsilon số 13, trang 205-208. [2] Ngô Đắc Tân (2003), Lý Thuyết tổ hợp và đồ thị, NXB Đại học Quốc gia HN. [3] Nguyễn Đức Nghĩa, Nguyễn Tô Thành (2009), Giáo trình Toán Rời Rạc, NXB Đại học Quốc gia HN. Tiếng Anh [4] P. Erd˝os (1980), "A survey of problems in combinatorial number theory", Annals of Discrete Mathemattics, 6, 89-115. [5] T. Ahmead (2013), "Some more Van der Waerden numbers", Jour- nal of Integer Sequences, Vol. 16, Article 13.4.4, 1-9. [6] H. Liu (2012), "Combinatorial Number Theory", available at http://www.cantab.net/users/henry.liu/comb nt.pdf. [7] B. A. Asaad, "Generalization of Ramsey Numbers Fur-
at available slides ther Research on Ramsey Theorem",
https://www.slideshare.net/AlAhmadgaidAsaad/f-28030794.Chương 2
Số Ramsey và tập đơn sắc
Kết luận
Tài liệu tham khảo
