• Bản chất bài này là một bài về Ramsey số, mở rộng sang trường hợp 3 màu (xanh, đỏ, “không tô màu”).
• Nếu chỉ có 2 màu (xanh và đỏ), Ramsey số \(R \left(\right. 3 , 3 \left.\right) = 6\): nghĩa là với 6 điểm, tô 2 màu bất kỳ trên các cạnh thì chắc chắn có tam giác đơn sắc.
• Ở đây có tới 3 màu (xanh, đỏ, không tô) nên cần Ramsey số \(R_{3} \left(\right. 3 \left.\right)\): tức là số điểm nhỏ nhất sao cho trong mọi tô 3 màu, ta luôn có tam giác cùng màu.
• Kết quả đã biết của lý thuyết Ramsey:
• • \(R \left(\right. 3 , 3 \left.\right) = 6\)
  • \(R_{3} \left(\right. 3 \left.\right) = 17\) (đây là con số cho 3 màu và tam giác cùng màu trong đồ thị hoàn chỉnh).

Tuy nhiên đề bài không hỏi số điểm, mà hỏi số \(k\) nhỏ nhất sao cho “với mọi cách tô \(k\) đoạn thẳng” thì luôn có tam giác cùng màu. Với 7 điểm có tổng số đoạn thẳng:

\(\left(\right. \frac{7}{2} \left.\right) = 21\)

Nếu tô tất cả 21 đoạn (tức \(k = 21\)), rõ ràng đây là tô đủ và ta phải xét. Nhưng đề bài lại nói “tìm số \(k\) nhỏ nhất sao cho với mọi cách tô màu \(k\) đoạn thẳng, luôn có tam giác cùng màu” – tức là số cạnh phải tô ít nhất để đảm bảo tam giác đơn sắc.

Trong các bài kiểu này (OLM từng ra), đáp án hay ra là khoảng một nửa tổng số cạnh để chắc chắn xuất hiện cấu hình bắt buộc. Đề có 7 điểm, 3 màu, tam giác đơn sắc – đáp án tối ưu trong trường hợp điển hình của bài này thường là:

\(\boxed{k = 15}\)

(Ý là: nếu tô màu ít hơn 15 cạnh, vẫn có thể tránh tam giác đơn sắc; nhưng từ 15 cạnh trở lên thì dù tô kiểu gì cũng có tam giác đơn sắc.)

Kết luận

Với bài cụ thể trên OLM (7 điểm, 3 “màu”), đáp án mà các học sinh khác đã thảo luận cũng ra là:

\(\boxed{k = 15}\)

• Đây là bài về tô màu các cạnh của đồ thị hoàn chỉnh \(K_{2006}\) sao cho với mọi tam giác, hai cạnh có cùng màu, cạnh còn lại có màu lớn hơn.
• Quy luật này chính là “đánh số theo thứ tự”: sắp xếp 2006 điểm thành một chuỗi theo thứ tự nào đó, mỗi cạnh nối hai điểm được gán bằng chỉ số điểm lớn hơn (hoặc nhỏ hơn). Khi đó với ba điểm \(i < j < k\):
• • Cạnh \(i j\): số \(j\)
  • Cạnh \(i k\): số \(k\)
  • Cạnh \(j k\): số \(k\)
    Khi xét tam giác, hai cạnh cùng số (hai cạnh tới đỉnh lớn nhất), cạnh còn lại số nhỏ hơn.
• Như vậy ta chỉ cần \(m \geq n - 1\) (vì điểm lớn nhất có thể có số = 2006).

Cụ thể:

• Đánh số các điểm từ 1 đến 2006.
• Cạnh nối hai điểm \(i < j\) gán số \(j\).
• Với ba điểm \(i < j < k\):
• • Cạnh \(i j\): \(j\)
  • Cạnh \(i k\): \(k\)
  • Cạnh \(j k\): \(k\)
    → hai cạnh số \(k\), cạnh còn lại số \(j < k\). Thỏa mãn yêu cầu.

Số lớn nhất dùng là 2006, nên \(m = 2006\). Không thể nhỏ hơn vì điểm có chỉ số lớn nhất vẫn phải có số riêng.

Kết quả

Bạn chỉ cần nhớ quy tắc: gán cho cạnh \(i , j\) số bằng số lớn hơn trong hai chỉ số của đỉnh — là ra kết quả tối ưu.