Bài 3
Cho S là một tập gồm 2004 điểm trên mặt phẳng, không có ba điểm thẳng hàng, và L là tập mọi đường thẳng xác định bởi từng cặp điểm của S. Một đường thẳng ngăn cách hai điểm nếu chúng nằm ở hai phía đối nhau và không điểm nào nằm trên đường thẳng đó. Chứng minh rằng có thể tô S bằng không quá hai màu sao cho hai điểm cùng màu khi và chỉ khi có một số lẻ đường thẳng trong L ngăn cách chúng.
Bước 1 trên 5: Định nghĩa tính chẵn lẻ của sự ngăn cách
Phân tích chi tiết
Với hai điểm x,y, gọi n(x,y) là số đường thẳng trong L ngăn cách chúng, xét theo modulo 2. Chọn p thuộc S và tô p màu xanh; tô q màu xanh khi n(p,q) lẻ, màu đỏ khi n(p,q) chẵn.