54-я Международная Математическая OлимпиадаКолумбия, Санта Марта, 2013 год

Будем называть колумбийской конфигурацией точек набор из 4027 точек на плоскости, никакие три из которых не лежат на одной прямой, при этом 2013 из них покрашены в красный цвет, а остальные 2014 — в синий. Рассмотрим набор прямых, делящих плоскость на несколько областей. Назовем этот набор хорошим для данной колумбийской конфигурации точек, если выполнены следующие два условия:
а) никакая прямая не проходит ни через одну из точек конфигурации;
б) никакая область разбиения не содержит точек обоих цветов.
Найдите наименьшее $k$ такое, что для любой колумбийской конфигурации из 4027 точек найдется хороший набор из $k$ прямых.

Комментарий/решение

Ответ: 2013.

Поскольку любые 2 красные точки лежащие на одной прямой, можно зажать между двумя прямыми, поскольку положение ближней синей точки постоянно, а прямую мы можем "сузить", то любые 2 точки можно зажать за 2 прямые.

Тогда, после распределения 2012 прямых, у нас останется 2013 точка. Рассмотрим три случая:

(i) Если выпуклая оболочка содержит в себе красную точку, то тогда очевидно, мы можем

отрезать эту точку от синих одной прямой.

(ii) Иначе если выпуклая оболочка содержит более 3 точек и все точки синие, сначала разобьем красные точки на треугольники так, что не в одном не лежит другая красная точка. Очевидно, это возможно, для любого треугольника если это не так будем брать точку внутри треугольника. Далее от 2 точек строить новые. Очевидно точки на выпуклой оболочке не влияют на треугольники внутри, тогда по Дирихле найдется треугольник без точек внутри их можно ограничить тремя прямыми.

(iii) Если у нас три синие точки на выпуклой оболочке, то поступим немного иначе, аналогично зажиму красных точек, будем зажимать синие точки, предварительно отрезав 2 точки на выпуклой оболочке 1 прямой, и оставшиеся 2012 синих точек ограничим 2012-ю прямыми.

Мы доказали достаточность, теперь приведем контр-пример для 2012:

Итак, выберем на окружности, с конечным радиусом поочередно синие и красные точки

причем найдутся две подряд идущие синие точки, соединим все соседние точки, кроме двух подряд идущих синих, получим 4026 отрезков, любая прямая будет пересекать не более чем 2 отрезка, следовательно 2012 не хватает для данной позиции.