55-я Международная Математическая OлимпиадаЮжно-Африканская Республика, Кейптаун, 2014 год

Будем говорить, что прямые на плоскости являются прямыми общего положения, если никакие две из них не параллельны и никакие три из них не проходят через одну точку. Любые несколько прямых общего положения разбивают плоскость на части; ограниченными частями разбиения будем называть те из частей, которые имеют конечную площадь. Докажите, что для всех достаточно больших $n$ верно следующее утверждение: в каждом множестве из $n$ прямых общего положения можно покрасить не менее $\sqrt{n}$ прямых в синий цвет так, чтобы граница любой из ограниченных частей разбиения не оказалась полностью синей.
Замечание: за доказательство утверждения задачи, в котором $\sqrt{n}$ заменено на $c\sqrt{n}$, будут начисляться баллы, в зависимости от константы $c$.

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

Допустим это неверно. Но по условию это надо доказать, что значит, что это является верным утверждением. А значит это противоречие предположению. Поэтому это верно => доказано