IMO 2013 problem 2

Đề bài:
Một tập hợp gồm đúng 4027 điểm trên mặt phẳng được gọi là tập Colombia nếu không có ba  điểm nào trong các điểm đó thẳng hàng, đồng thời có 2013 điểm được tô màu đỏ và 2014 điểm còn lại được tô màu xanh. Mặt phẳng được phân chia thành các miền khi ta kẻ một số đường thẳng. Một cách kẻ một số đường thẳng được gọi là cách kẻ tốt đối với tập Colombia cho trước nếu hai điều kiện sau được thỏa mãn: 
1. Không đường thẳng nào đi qua dù chỉ một điểm thuộc tập hợp đó; 
2. Không miền nào chứa cả điểm màu đỏ và điểm màu xanh. 
Tìm số $k$ nhỏ nhất sao cho với tập Colombia tùy ý gồm đúng 4027 điểm, tồn tại một cách kẻ $k$ đường thẳng là cách kẻ tốt.

Lời giải:
Xét đa giác đều 4027 cạnh $A_1A_2\ldots A_{4027}$ nội tiếp đường tròn $(O)$ nào đó.
Giả sử rằng các đỉnh $A_{2k},k=\overline{1;2013}$ màu đỏ và các đỉnh $A_{2k+1},k=\overline{0;2013}$ màu xanh.
Nhận xét: Vì các điểm $A_i;A_{i+1},i=\overline{1;4026}$ khác màu nhau nên $A_i;A_{i+1}$ nằm về 2 phía của 1 đường thẳng nào đó trong số $N$ đường thẳng đã cho, hay tồn tại 1 đường thẳng cắt cung nhỏ $A_iA_{i+1}$.
Có tất cả 4026 cung mà mỗi đường thẳng chỉ cắt tối đa 2 cung nên cần ít nhất 2013 đường thẳng để thực hiện cách phân chia thỏa mãn.
Ta chứng minh: với 4027 điểm bất kỳ thì chỉ cần 2013 đường thẳng để có 1 cách phân chia thỏa mãn.
Gọi $X_1X_2\ldots X_k$ là bao lồi của 4027 điểm trên.
Trường hợp 1: Giả sử tồn tại $i$ sao cho $X_i$ màu đỏ.
Không mất tính tổng quát, giả sử điểm đó là $X_1$.
Khi đó, tồn tại đường thẳng $\Delta$ chia mặt phẳng ra làm 2 miền trong đó 1 miền chỉ chứa duy nhất điểm $X_1$.
Xét 2012 điểm màu đỏ còn lại $A_1;A_2;\ldots;A_{2012}$.
Với mỗi $i=\overline{1;1006}$, tồn tại 2 đường thẳng $x_i;y_i$ song song với nhau và song song với $A_{2i-1}A_{2i}$ sao cho miền mặt phẳng nằm giữa $x_i,y_i$ chỉ chứa 2 điểm $A_{2i-1},A_{2i}$.
Khi đó, 2013 đường thẳng $\Delta, x_1, y_1, x_2, y_2, \ldots, x_{1006}, y_{1006}$ thỏa mãn bài toán.
Trường hợp 2: Tất cả các điểm $X_1, X_2, \ldots ,X_k$ đều màu xanh.
Khi đó, tồn tại đường thẳng $\Delta$ song song với $X_1X_2$ chia mặt phẳng ra làm 2 miền trong đó 1 miền chỉ chứa 2 điểm $X_1, X_2$.
Xét 2012 điểm màu xanh còn lại $B_1;B_2;\ldots;B_{2012}$.
Với mỗi $i=\overline{1;1006}$, tồn tại 2 đường thẳng $x_i;y_i$ song song với nhau và song song với $B_{2i-1}B_{2i}$ sao cho miền mặt phẳng nằm giữa $x_i,y_i$ chỉ chứa 2 điểm $B_{2i-1},B_{2i}$.
Khi đó, 2013 đường thẳng $\Delta, x_1, y_1, x_2, y_2, \ldots, x_{1006}, y_{1006}$ thỏa mãn bài toán.
Vậy cần ít nhất 2013 đường thẳng để thực hiện cách phân chia thỏa mãn.