Xét một điểm A bất kỳ, nối với 2005 điểm còn lại. Ta tô màu các đoạn thẳng này bằng các số từ 1 đến 2005.

Với mỗi điểm B khác A, xét các đoạn thẳng nối B với các điểm còn lại. Ta tô màu các đoạn thẳng này sao cho thỏa mãn điều kiện của bài toán.

Sử dụng quy nạp, ta có thể chứng minh rằng số tốt nhỏ nhất là 1003.

Lý do: Với mỗi điểm, có 2005 đoạn thẳng nối với các điểm khác. Ta chia các đoạn thẳng này thành 1003 cặp và một đoạn thẳng đơn. Tô màu các cặp đoạn thẳng bằng các số từ 1 đến 1003, và đoạn thẳng đơn bằng số 1003.

Khi đó, mỗi tam giác sẽ có hai cạnh được gán bởi hai số bằng nhau và cạnh còn lại được gán bởi số lớn hơn hai số đó.

Vậy số tốt nhỏ nhất là 1003.