Bài 6

Một tập hợp các đường thẳng trong mặt phẳng ở vị trí tổng quát nếu không có hai đường nào song song và không có ba đường nào đồng quy. Một tập hợp đường thẳng ở vị trí tổng quát chia mặt phẳng thành các miền, một số miền có diện tích hữu hạn; gọi đó là các miền hữu hạn. Chứng minh rằng với mọi

n

đủ lớn, trong bất kỳ tập hợp

n

đường thẳng ở vị trí tổng quát nào, luôn có thể tô màu xanh ít nhất

\sqrt{n}

đường thẳng sao cho không có miền hữu hạn nào có toàn bộ biên là màu xanh.

Bước 1 trên 6: Thiết lập: điểm, điểm lân cận, và miền hữu hạn như đa giác

Bước trước Bước tiếp

\binom{n}{2} \text{ intersection points; each line carries } n-1 \text{ of them}

Phân tích chi tiết

Gọi $\binom{n}{2}$ giao điểm từng cặp là các điểm; mỗi đường trong $n$ đường mang $n-1$ điểm như vậy. Hai điểm trên cùng một đường là lân cận nếu không có điểm nào khác của đường đó nằm nghiêm ngặt giữa chúng. Mỗi miền hữu hạn khi đó là một đa giác lồi mà các đỉnh liên tiếp dọc theo mỗi đường biên đều là lân cận.