Giữa sáu người lạ luôn có một tam giác: 2^15 trường hợp cần kiểm chứng

R(3,3) = 6; mười lăm cặp cho 32 768 cách tô màu và mỗi cách giấu một tam giác.

Thống kê và dữ liệu · Mức độ: Kết quả kinh điển · Cập nhật ngày 2026-11-10

Tô đỏ hoặc xanh mỗi vạch nối sáu điểm. Ở đâu đó trong kết quả có một tam giác mà cả ba cạnh cùng màu, và sáu là số điểm nhỏ nhất bảo đảm điều đó. Chứng minh là lập luận tiệc tùng: chọn một người, người ấy có năm quan hệ và theo nguyên lý chuồng bồ câu ít nhất ba trong số đó cùng loại; nếu hai trong ba người ấy quen nhau thì bạn có tam giác, nếu không ai quen ai thì ba người ấy là đôi bên xa lạ và tam giác kia thuộc về bạn. Sáu người tạo 6 × 5/2 = 15 cặp (liên kết thứ hai), tức một cỗ máy có thể vét cạn 2^15 = 32 768 trường hợp (liên kết thứ nhất) — nhỏ tới mức không ai có cớ để không làm; còn độ sắc của cận được kiểm chứng bằng chu trình năm, một ngũ giác đỏ chứa một ngôi sao xanh bên trong, tránh cả hai loại tam giác trên năm điểm.

Số chéo kế tiếp R(4,4) = 18 tốn 2^153 cách tô màu: giữa mười tám điểm có 18 × 17/2 = 153 cặp (liên kết thứ ba) và 2^153 là 1.1417981541648⋅10+46 (thứ tư), một con số không thể bàn bằng cách đếm. Greenwood và Gleason năm 1955 đạt được 18 bằng một hỗn hợp phỏng đoán và các trường hợp kiểm chứng tay; cùng câu hỏi đó ở một bước xa hơn, R(5,5), vẫn mở từ đó, chỉ biết nó nằm trong một dải hẹp đã dịch chút ít trong bảy mươi năm. Bản thân định lý Ramsey, từ 1930, nói về cơ chế logic bên dưới tất cả những điều này và được chứng minh vì cần cho một câu hỏi triết học toán học — bảo đảm rằng bất kỳ cấu trúc nào đủ lớn cũng chứa một phần lớn và có trật tự của chính nó.

Đáp án

32768

Cách đọc

2^15 trên bàn làm việc: mọi cách tô hai màu cho mười lăm cặp của sáu người. Liên kết thứ hai là chính mười lăm cặp đó.

Nguồn

Frank P. Ramsey, 'On a Problem of Formal Logic', 1930; R(3,3) = 6 is the party theorem, R(4,4) = 18 was proved by Greenwood and Gleason in 1955, and R(5,5) is still unknown

Giải trong máy tính

Các liên kết này mở đúng máy tính với các con số của bài toán đã nhập sẵn. Dòng bên trên là những gì màn hình phải hiện — hãy tự kiểm tra.

Đây là một trang công cụ độc lập của bên thứ ba. Trang không liên kết, được tài trợ hay ủy quyền bởi Casio, Texas Instruments hoặc các nhà phân phối của họ. Tên model và sản phẩm là nhãn hiệu của các chủ sở hữu tương ứng và chỉ được dùng ở đây để nhận diện thiết bị.

Các chuỗi phím trong những hướng dẫn này được viết dựa trên dữ liệu bố cục riêng của trang — chính là dữ liệu mà máy tính trực tuyến sử dụng — cùng với thông tin sản phẩm công khai. Thông số kỹ thuật và cấu hình theo khu vực được kiểm chứng trên thiết bị thật và tài liệu mới nhất của nhà sản xuất.