Problem 2

A configuration of

4027

points in the plane is called Colombian if it consists of

2013

red points and

2014

blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is good for a Colombian configuration if the following two conditions are satisfied: (1) no line passes through any point of the configuration; (2) no region contains points of both colours. Find the least value of

k

such that for any Colombian configuration of

4027

points, there is a good arrangement of

k

lines.

Step 5 of 5: Conclusion

Previous step Next step

In plain words

The lower and upper bounds agree.

k_{\min}=2013

Detailed analysis

The alternating convex-polygon example gives $k\ge2013$ , and the hull-and-strip construction gives $k\le2013$ . Hence the least value is $k=2013$ .