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 3 trên 5: Loại các đường không đi qua đỉnh tam giác
Phân tích chi tiết
Vẽ tam giác pqr và bảy miền của nó. Mọi đường trong L không đi qua p,q,r đều cắt các cạnh tam giác một số chẵn lần, nên đóng góp của nó vào tổng ba số ngăn cách là chẵn. Chỉ các đường qua một trong ba đỉnh và một điểm ở bảy miền mới cần xét.