Bài 2
Một cấu hình điểm trong mặt phẳng được gọi là Colombia nếu nó gồm điểm đỏ và điểm xanh, và không có ba điểm nào của cấu hình thẳng hàng. Bằng cách vẽ một số đường thẳng, mặt phẳng được chia thành nhiều miền. Một cách vẽ đường thẳng được gọi là tốt đối với một cấu hình Colombia nếu hai điều kiện sau được thỏa mãn: (1) không đường thẳng nào đi qua điểm nào của cấu hình; (2) không miền nào chứa điểm của cả hai màu. Tìm giá trị nhỏ nhất của sao cho với mọi cấu hình Colombia gồm điểm, luôn tồn tại một cách vẽ tốt gồm đường thẳng.
Bước 1 trên 5: Cận dưới từ đa giác lồi xen kẽ màu
Hiểu nôm na
Mỗi khoảng biên đỏ–xanh phải bị cắt, còn một đường thẳng chỉ cắt biên đa giác nhiều nhất hai lần.
Phân tích chi tiết
Đặt 2013 điểm đỏ và 2013 điểm xanh xen kẽ trên một đa giác lồi 4026 đỉnh, rồi đặt điểm xanh còn lại ở vị trí tổng quát bên ngoài. 4026 cạnh biên có hai đầu khác màu, nên mọi cách vẽ tốt phải cắt từng cạnh. Một đường thẳng cắt biên đa giác nhiều nhất hai lần, do đó .