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 2 trên 5: Đưa về một đẳng thức chẵn lẻ của ba điểm
Phân tích chi tiết
Theo cách tô, q và r cùng màu khi và chỉ khi n(p,q)+n(p,r) chẵn. Vì vậy chỉ cần chứng minh với ba điểm phân biệt p,q,r rằng n(p,q)+n(p,r)+n(q,r) là lẻ.