Точки и прямые

Попробуйте посчитать прямые, определяемые меньшим числом точек — 4, 9 или 16 точками. Если ответы получатся 6, 20 и 62 прямых, то вы на правильном пути.

Главная трудность в том, что некоторые прямые проходят только через две отмеченные точки, а некоторые — через три и более отмеченных точек. При решении задачи важно организовать систему подсчета прямых.

Все прямые разделим на непересекающиеся классы параллельных прямых. В каждый класс попадают прямые с одним угловым коэффициентом k.

Рис. 2. Некоторые из классов параллельных прямых

На рис. 2 указаны некоторые классы прямых. Их угловые коэффициенты, кроме 0 и 1, — это всевозможные правильные несократимые дроби, знаменатель которых не больше 5. Чтобы получить вообще все классы, нужно учитывать симметрию картинки. Так что при подсчете, — а полученные числа осталось просто сложить, — количество прямых в классах с k = 0 и k = 1 нужно увеличить в два раза, а в остальных классах — в четыре раза. В итоге получится 2×(6 + 9) + 4×(5 + 4 + 3 + 2 + 10 + 6 + 15 + 12 + 12) = 306 прямых.

Аналогичный подсчет для 64 точек даст 938 прямых.

Теперь разберемся с тетраэдром. Эту задачу можно сразу рассмотреть в общем виде. Пусть каркас тетраэдра с ребром длины m разделен точками на единичные отрезки. Сколько разных прямых определяют эти точки и вершины самого тетраэдра?

У тетраэдра 4 вершины и 6 ребер. Вместе с вершинами и точками деления на каркасе тетраэдра отмечено 4 + 6(m − 1) = 6m − 2 точки. Если бы все эти точки были в общем положении (то есть ни какие три из них не лежали бы на одной прямой), то они определили бы (6m − 2)(6m − 3)/2 = (3m − 1)(6m − 3) прямые (потому что если точки находятся в общем положении, то любые две из них определяют свою собственную прямую). Теперь надо учесть, что на каждом ребре тетраэдра отмечено по m + 1 точке не общего положения. Будь эти точки в общем положении, они бы определяли m(m + 1)/2 прямых. Но все эти прямые совпадают — это прямая, содержащая данное ребро тетраэдра. Значит, общее число прямых, определяемых указанными точками, равно (3m − 1)(6m − 3) − 6·m(m + 1)/2 + 6. После упрощения получим 15m² − 18m + 9 прямых. В нашей задаче m = 4, поэтому ответ — 177 прямых.

Если применить рассуждения, которые мы использовали при ответе на первый вопрос задачи, то можно найти ответы и для других квадратов из n² точек. Вот они для n от 2 до 10: 6, 20, 62, 140, 306, 536, 938, 1492, 2306. Эта последовательность входит в Онлайн-энциклопедию целочисленных последовательностей под номером A018808.

А есть ли сравнительно простая формула, которая бы позволила выразить число N таких прямых для произвольного n? Попробуем ее поискать.

Воспользуемся двумя известными фактами из геометрии инцидентности.

    1) Если на плоскости отметить k точек общего положения (напомним, что это означает, что никакие три из этих точек не лежат на одной прямой), то число различных прямых, определяемых этими точками, равно k(k − 1)/2.

Этим утверждением мы пользовались в решении, и оно легко доказывается по индукции.

    2) Если на плоскости отметить k точек, не лежащих на одной прямой, то они определяют не менее k разных прямых.

Второе утверждение звучит совсем очевидно, однако оно впервые было доказано только в середине ХХ века и известно сейчас, как теорема де Брёйна — Эрдёша.

Опираясь на эти два свойства можно сделать оценки числа N(n). Используя второй факт, получим нижнюю оценку: N(n) ≥ n². Используя первый факт, получим верхнюю оценку: N(n) ≤ n²(n² − 1)/2 — это число прямых, определяемых n² точками общего положения.

Это значит, что если существует формула N(n) в виде многочлена от n, — а это самый, наверное, простой вид формулы, — то этот многочлен может иметь только 2, 3 или 4 степень. Используя приведенные выше первые несколько значений N, методом неопределенных коэффициентов можно показать, что не существует формулы в виде такого многочлена.

Попробуем другой подход и обобщим прием подсчета прямых разбиением на классы параллельных. В каждый класс входят все параллельные прямые с угловым коэффициентом k = a/b (здесь и далее дроби — правильные несократимые).

Так как любая прямая на плоскости однозначно задается угловым коэффициентом и одной точкой, то для каждого класса с k = a/b в точечном квадрате выделим те точки, которые определяют все прямые этого класса. При этом возможны два случая:
    1) если b < n/2, то точки, определяющие все прямые с угловым коэффициентом a/b, расположены внутри голубого и зеленого прямоугольников, показанных слева на рис. 3, и их b·(n − a) + a·(n − 2b) = n·(a + b) − 3ab;
    2) если b ≥ n/2, то точки, определяющие все прямые с угловым коэффициентом a/b, расположены внутри голубого прямоугольника, показанного справа на рис. 3, и их (n − a) (n − b).

Рис. 3. Точки, при помощи которых можно задать все прямые из данного класса в квадрате из 100 точек. Слева пример для k = 2/3, справа — для k = 2/7

Число N(a/b) прямых в классе c k = a/b равно числу выделенных точек, и вычисляется по найденным выше формулам.

Поэтому, число N(n) всех прямых, заданных n² точками можно вычислять по формуле:

где N₀ = n — число горизонтальных прямых, N₁ = 2n — 3 — число прямых, параллельных диагонали квадрата. Эту формулу несложно запрограммировать и проверить, что результаты совпадают.

Можно получить и рекуррентные соотношения на число прямых, определяемых точечными квадратами, однако они тоже получаются довольно громоздкими. За подробностями отсылаем к статье S. Mustonen, 2009. On lines and their intersection points in a rectangular grid of points.

Рассуждения, которые в решении были приведены для правильного тетраэдра, работают для любого выпуклого многогранника, у которого все ребра равны между собой. В самом деле, там нигде не использовались никакие специфичные для тетраэдра свойства, учитывалось лишь количество его вершин и ребер. Так что рассуждения повторяются почти дословно.

Пусть у многогранника B вершин и P ребер. Вместе с вершинами и точками деления на каркасе многогранника отмечено В + Р(m − 1) точек. Если бы все эти точки были в общем положении, то они определили бы \(\frac12(B+P(m-1))(B+P(m-1)-1)\) прямых. Но на каждом ребре многогранника отмечено по (m + 1) точке, которые, будь они в общем положении, определяли бы m(m + 1)/2 прямых, но вместо этого они определяют только одну прямую, содержащую ребро. Значит, все их нужно вычесть из общего числа и прибавить число прямых, содержащих ребра. Получится