Олимпиадная задача: 9 точек и прямые — комбинаторная геометрия, 6-8 класс

Пример показан на рисунке. Докажем, что среди любых 6 из этих точек найдутся 3, лежащие на одной прямой. Будем называть важной прямую, на которой лежат 3 отмеченные точки. Докажем, что какие бы три точки из 9 мы ни выкинули, найдется важная прямая, из которой мы не выкинули ни одной точки. Будем рассуждать от противного. Предположим, что можно выкинуть 3 точки из 9 отмеченных так, чтобы из каждой важной прямой пропала хотя бы одна точка. Точка O лежит на наибольшем количестве важных прямых "– на 4. Если бы мы точку O не выкинули, то нам надо было бы выкинуть какую-то другую точку из каждой из этих прямых, то есть выкинуть хотя бы 4 точки. А мы можем выкинуть только три. Противоречие. Значит, нам надо выкинуть точку O . Тогда остается такая картинка (рис.). Остается 5 важных прямых, и каждая точка лежит не более чем на двух из них. Следовательно, после удаления еще двух точек останется хотя бы одна важная прямая, из которой не выкинуто ни одной точки.

Примечания.

1. Придумать этот пример можно следующим образом. Сначала расположим 9 точек в виде квадрата3x3. Этот пример не годится, так как можно взять 6 точек, обведенных кружочком (рис.). Проблема в том, что есть несколько "малополезных" точек, которые лежат только на 2 важных прямых. Попробуем передвинуть одну из них на место получше. Получим правильный пример.

2. Есть и другие примеры. В них может быть как 9, так и 8 важных прямых (рис). Не для всех из них проходит доказательство, аналогичное указанному выше, но все их можно доказать, не делая перебора всех шестерок точек. Отметим, что для некоторых примеров неочевидно, что они вообще реализуются (т.е. что их можно нарисовать) на плоскости. Это можно доказать, либо явно предъявив алгоритм построения, либо из соображений непрерывности.

Ответ задачи отсутствует