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 4 trên 5: Đếm bảy miền
Phân tích chi tiết
Gọi n_i là số điểm của S trong miền i, không kể p,q,r, theo cách đánh số bảy miền quanh tam giác pqr. Các đường qua p ngăn cách q,r tương ứng với các miền 1,4,7; tương tự cho q và r là 2,5,7 và 3,6,7. Tổng của chúng đếm mỗi điểm ngoài p,q,r đúng một lần, bằng 2001 nên lẻ.