Задача

[snyders]

Даны N точек на плоскости (не все на одной прямой) двух цветов RED, WHITE (не все одного цвета). Показать, что существует прямая, проходящая только через две (или более) монохроматические точки.

Comments

[jama-dharma.livejournal.com]

Любая комбинация из N точек может быть получена из трех точек последовательным добавлением точек. Рассмотрим начальную комбинацию из трех точек. Одна точка одного цвета(для определенности красная) и две другого(белые). Такая начальная комбинация при данных условиях гарантирует проведнеие монохроматической прямой. Добавление новой точки не способно изменить возможность проведения монохроматической прямой. Так как если добавлена белая точка, то это очевидно, а если красная, то если она добавлена на линию, на которой стоят две белые точки, то можно провести красную линию, в противном случае можно провести и белую и красную.
Дальше по индукции строим все N точек.

Решение таких задач очень сложно привести без листика бумаги:) Нет, если есть совсем строгое доказательство, то, конечно, можно. Но, по-моему, это не тот случай.