Решение задачи 343

Условие:

Вова Брагин утверждает, что любые 100 точек на плоскости можно разбить на две группы так, чтобы никакая прямая не отделяла одну группу от другой. Прав ли Вова?

Решение:

Если среди этих ста точек найдутся три, лежащие на одной прямой, покрасим среднюю из них в белый цвет, а две другие в черный цвет. Тогда нетрудно видеть, что никакая прямая не отделит одну группу точек от другой даже среди этих трех, не говоря уже о всех ста. Пусть никакие три точки не лежат на одной прямой, тогда возьмем любые четыре и построим на них выпуклую оболочку. Если получился четырехугольник, то покрасим пару противоположных вершин в белый цвет, другую пару -- в черный. Тогда снова никакая прямая не отделит одну группу от другой (вне зависимсти от того, как красить остальные 96 точек). Если же получился треугольник, то покрасим его вершины в белый цвет, а точку, которая внутри него -- в черный. В этой ситуации опять никакая прямая не отделит одну группу от другой.

Ответ: Прав.