Математикадан 54-ші халықаралық олимпиада, 2013 жыл, Санта Марта

Егер жазықтықта 2013 нүкте қызыл мен 2014 нүкте көк болса, және осы 4027 нүктелер арасында кез келген үш нүкте бір түзудің бойында болмаса, онда осындай конфигурацияны Колумбиялық конфигурация деп атаймыз. Кейбір түзулерін салып жазықтық бірнеше аймақтарға бөлінеді. Келесі үш шарт орындалса, онда түзулердің орналыстыруы Колумбиялық конфигурациясы үшін жақсы болады:
1) конфигурацияның нүкте арқылы сызылған түзуі табылмайды;
2) әрбір аймақтың ішінде екі түстен нүктелер табылмайды.
Кез келген 4027 нүктелерден тұратын Колумбиялық конфигурациясы үшін $k$ түзулердің жақсы орналыстыруы міндетті табылатынын $k$-ның минималды мәнін анықтаңдар.

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

Ответ: 2013.

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

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

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

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

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

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

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

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

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