Định Lý Ramsey Và Các Bài Toán Liên Quan

by Thầy Đông · January 8, 2026

Rate this post

Trong toán học, có những định lý kinh điển mang tính nền tảng, giải quyết những vấn đề tưởng chừng đơn giản nhưng lại chứa đựng sự phức tạp và vẻ đẹp sâu sắc. Định lý Ramsey là một trong số đó, khẳng định rằng trong một hệ thống đủ lớn, sự hỗn loạn “tự động” tạo ra trật tự. Bài viết này sẽ đi sâu vào khám phá định lý Ramsey, các khái niệm liên quan và cách áp dụng nó thông qua các bài toán cụ thể.

Đề Bài

Khẳng định gốc được trình bày trong tài liệu là:
“Trong sáu người bất kỳ luôn tồn tại ba người sao cho hoặc là họ quen nhau từng đôi một hoặc họ không quen nhau từng đôi một.”

Khẳng định này được viết lại một cách ngắn gọn bằng ký hiệu như sau:
K6 → K3, K3

với ý nghĩa:

K6: Đại diện cho một tập hợp gồm 6 đối tượng, và tất cả các cặp không thứ tự giữa chúng đều thể hiện một mối quan hệ (quen hoặc lạ). Trong lý thuyết đồ thị, đây là đồ thị đầy đủ với 6 đỉnh.
K3, K3: Đại diện cho hai trường hợp: “Ba đối tượng quen nhau từng đôi một” (một tam giác đơn sắc màu xanh) hoặc “Ba đối tượng không quen nhau từng đôi một” (một tam giác đơn sắc màu đỏ).

Một bài tập đi kèm là:
“Hãy chứng minh rằng trong 9 người luôn có 3 người đôi một quen nhau hoặc 4 người đôi một không quen nhau.”

Phân Tích Yêu Cầu

Bài toán cốt lõi và các bài tập đi kèm yêu cầu chúng ta chứng minh sự tồn tại của một cấu trúc nhất định (cụ thể là một tập hợp con gồm 3 hoặc 4 người với mối quan hệ đồng nhất về quen biết hoặc không quen biết) trong một tập hợp lớn hơn (6 hoặc 9 người). Điều này ngụ ý rằng không cần phải chỉ ra cụ thể nhóm người đó là ai, mà chỉ cần chứng minh sự tồn tại của họ là điều tất yếu.

Mấu chốt của bài toán nằm ở việc xem xét các mối quan hệ giữa các đối tượng dưới dạng tô màu các cạnh của một đồ thị. “Quen nhau” có thể được biểu diễn bằng một màu (ví dụ: xanh), và “không quen nhau” bằng màu còn lại (ví dụ: đỏ). Yêu cầu bài toán trở thành việc chứng minh rằng trong đồ thị đầy đủ K6 (hoặc K9), luôn tồn tại một đồ thị con K3 với tất cả các cạnh cùng màu (hoặc K3 đỏ, hoặc K3 xanh, hoặc K4 đỏ, hoặc K4 xanh).

Kiến Thức/Nền Tảng Cần Dùng

Để hiểu và giải quyết các bài toán liên quan đến định lý Ramsey, chúng ta cần nắm vững một số khái niệm cơ bản trong lý thuyết đồ thị:

Đồ thị đầy đủ Kn: Là một đồ thị có n đỉnh, trong đó mọi cặp đỉnh phân biệt đều được nối với nhau bởi đúng một cạnh.
Ví dụ: K3 là một tam giác với 3 đỉnh và 3 cạnh. K6 có 6 đỉnh và (6 5) / 2 = 15 cạnh.
Tô màu cạnh (Edge Coloring): Gán một màu cho mỗi cạnh của đồ thị. Trong bối cảnh định lý Ramsey, chúng ta thường chỉ sử dụng hai màu (ví dụ: xanh và đỏ) để biểu diễn hai loại mối quan hệ khác nhau.
Đồ thị con đơn sắc (Monochromatic Subgraph): Là một đồ thị con mà tất cả các cạnh của nó đều có cùng một màu. Ví dụ, một K3 đỏ là một tam giác mà cả ba cạnh đều được tô màu đỏ.
Ký hiệu Ramsey: K_p → K_m, K_n đọc là “Nếu mọi cạnh của đồ thị đầy đủ Kp được tô bởi hai màu (ví dụ: đỏ và xanh), thì luôn tồn tại một đồ thị con Km với tất cả các cạnh màu đỏ, HOẶC một đồ thị con Kn với tất cả các cạnh màu xanh.”

Định lý Ramsey (Dạng đơn giản)

Với hai số nguyên m ≥ 2 và n ≥ 2, luôn tồn tại một số nguyên dương p sao cho Kp → Km, Kn.
Điều này có nghĩa là, cho trước hai số nguyên m và n, luôn có một số nguyên dương p đủ lớn để nếu tô màu bất kỳ các cạnh của đồ thị đầy đủ Kp bằng hai màu đỏ và xanh, ta sẽ luôn tìm thấy hoặc một Km với tất cả các cạnh màu đỏ, hoặc một Kn với tất cả các cạnh màu xanh.

Số Ramsey `r(m, n)`

Số nguyên dương p nhỏ nhất thỏa mãn Kp → Km, Kn được gọi là số Ramsey và ký hiệu là r(m, n).

Ví dụ: r(3, 3) = 6 có nghĩa là K6 → K3, K3 là đúng, nhưng K5 → K3, K3 là sai (tức là có cách tô màu 5 đỉnh của K5 bằng 2 màu mà không tạo ra K3 đỏ hay K3 xanh).

Hướng Dẫn Giải Chi Tiết

Chúng ta sẽ chứng minh khẳng định gốc: K6 → K3, K3.

Bước 1: Phân tích đối tượng và mối quan hệ

Xét 6 người (hoặc 6 đỉnh của K6). Mối quan hệ giữa hai người bất kỳ có thể là “quen nhau” (tô cạnh màu xanh) hoặc “không quen nhau” (tô cạnh màu đỏ). Chúng ta cần chứng minh rằng luôn tồn tại một nhóm 3 người mà cả ba cặp trong nhóm đó đều có cùng một mối quan hệ (hoặc cả ba cặp đều quen nhau, hoặc cả ba cặp đều không quen nhau).

Bước 2: Chọn một đỉnh và xét các cạnh kề

Chọn một người bất kỳ, gọi là p. Có 5 mối quan hệ giữa p và 5 người còn lại. Theo nguyên lý Dirichlet (nguyên lý chuồng bồ câu), trong 5 mối quan hệ này, phải có ít nhất ⌈5/2⌉ = 3 mối quan hệ cùng màu.
Giả sử 3 mối quan hệ này có màu đỏ. Điều này có nghĩa là người p quen biết (hoặc không quen biết, tùy theo cách gán màu) 3 người khác, gọi là a, b, và c, với cùng một mối quan hệ màu đỏ.

(Lưu ý: Ở đây, ta giả sử màu đỏ biểu thị “quen nhau” và màu xanh biểu thị “không quen nhau”. Nếu ngược lại, lập luận vẫn tương tự.)

Bước 3: Xét mối quan hệ giữa các đỉnh còn lại

Bây giờ, chúng ta xem xét 3 người a, b, c mà p có cùng mối quan hệ màu đỏ với họ. Chúng ta cần xem xét các mối quan hệ giữa a, b, và c với nhau. Có ba cặp có thể tồn tại: (a, b), (a, c), và (b, c).

Trường hợp 1: Tồn tại một cặp có màu đỏ.
Giả sử cặp (a, b) có quan hệ màu đỏ (tức là a và b quen nhau). Vì p quen a (cạnh đỏ) và p quen b (cạnh đỏ), và bây giờ a quen b (cạnh đỏ), chúng ta đã tìm thấy một nhóm 3 người (p, a, b) mà cả ba cặp đều quen nhau. Đây là một K3 đỏ.
Trường hợp 2: Mọi cặp còn lại đều có màu xanh.
Nếu không có cặp nào trong (a, b), (a, c), (b, c) có màu đỏ, điều đó có nghĩa là tất cả các cặp này đều có màu xanh. Tức là: a không quen b, a không quen c, và b không quen c.
Khi đó, chúng ta có một nhóm 3 người (a, b, c) mà cả ba cặp đều không quen nhau. Đây là một K3 xanh.

Trong cả hai trường hợp, chúng ta đều tìm thấy một K3 đơn sắc (hoặc đỏ hoặc xanh). Điều này chứng minh K6 → K3, K3.

Mẹo kiểm tra

Để kiểm tra một bài toán liên quan đến Ramsey, hãy hình dung các đối tượng là các điểm và các mối quan hệ là các đường nối giữa chúng. Sau đó, hãy thử tô màu các đường theo hai loại quan hệ và xem liệu có thể “né tránh” việc tạo ra một nhóm con có cùng mối quan hệ hoàn toàn hay không. Nếu không thể né tránh, thì khẳng định là đúng.

Lỗi hay gặp

Nhầm lẫn giữa Kp → Km, Kn và Kp → Kn, Km: Thứ tự của Km và Kn không quan trọng vì r(m, n) = r(n, m).
Quên mất trường hợp màu còn lại: Khi giả sử có 3 cạnh đỏ từ p, ta phải xem xét kỹ lưỡng cả 3 cạnh còn lại có màu xanh hoặc đỏ.
Không áp dụng đúng nguyên lý Dirichlet: Đảm bảo số lượng cạnh (mối quan hệ) đủ lớn so với số màu để áp dụng nguyên lý.

Đáp Án/Kết Quả

Khẳng định định lý Ramsey cho trường hợp K6 → K3, K3 là đúng. Bất kỳ cách tô màu nào cho 15 cạnh của đồ thị K6 bằng hai màu đỏ và xanh sẽ luôn tạo ra ít nhất một tam giác đơn sắc K3 (hoặc tất cả các cạnh có màu đỏ, hoặc tất cả các cạnh có màu xanh).

Đối với bài tập “Trong 9 người luôn có 3 người đôi một quen nhau hoặc 4 người đôi một không quen nhau”, điều này tương đương với K9 → K3, K4. Chúng ta biết rằng r(3, 4) = 9. Chứng minh cho r(3, 4) = 9 sẽ phức tạp hơn một chút, đòi hỏi bước quy nạp hoặc sử dụng công thức cận trên r(m, n) ≤ r(m-1, n) + r(m, n-1). Dựa trên định lý Ramsey tổng quát, khẳng định này là đúng.

Khái Quát Về Số Ramsey và Các Trường Hợp Mở Rộng

Số Ramsey r(m, n) là con số nhỏ nhất p sao cho Kp → Km, Kn. Giá trị của r(m, n) thường khó tính toán và chỉ biết giá trị cho một số ít cặp (m, n).
Một vài ví dụ về số Ramsey:

r(3, 3) = 6
r(2, n) = n
r(3, 4) = r(4, 3) = 9
r(3, 5) = r(5, 3) = 14
r(4, 4) = 18

Định lý Ramsey có thể được mở rộng cho nhiều hơn hai màu và cho các đồ thị con lớn hơn. Ví dụ, với ba màu và ba số nguyên n1, n2, n3 ≥ 2, luôn tồn tại số p sao cho Kp khi tô màu bởi ba màu sẽ chứa hoặc một Kn1 màu thứ nhất, hoặc một Kn2 màu thứ hai, hoặc một Kn3 màu thứ ba. Trường hợp nổi tiếng là r(3, 3, 3) = 17.

Định lý Ramsey là một ví dụ điển hình cho thấy trong sự phức tạp ngẫu nhiên, luôn tồn tại những cấu trúc có trật tự nhất định. Nó có ứng dụng quan trọng trong khoa học máy tính lý thuyết, logic toán học và các lĩnh vực khác yêu cầu phân tích cấu trúc tổ hợp.

Ngày chỉnh sửa nội dung mới nhất January 8, 2026 by Thầy Đông

Thầy Đông

Thầy Đông – Giảng viên Đại học Công nghiệp Hà Nội, giáo viên luyện thi THPT
Thầy Đông bắt đầu sự nghiệp tại một trường THPT ở quê nhà, sau đó trúng tuyển giảng viên Đại học Công nghiệp Hà Nội nhờ chuyên môn vững và kinh nghiệm giảng dạy thực tế. Với nhiều năm đồng hành cùng học sinh, thầy được biết đến bởi phong cách giảng dạy rõ ràng, dễ hiểu và gần gũi. Hiện thầy giảng dạy tại dehocsinhgioi, tiếp tục truyền cảm hứng học tập cho học sinh cấp 3 thông qua các bài giảng súc tích, thực tiễn và giàu nhiệt huyết.