Меню

Сколько точек достаточно чтобы построить прямую

Сколько нужно точек, чтобы провести прямую?

Сколько нужно точек, чтобы провести прямую?

Прямую можно провести и без точек, и с одной точкой и с двумя. Например, через одну точку можно провести множество прямых, а через две точки получиться только одна прямая. Вообще, прямую лучше провести без точки, но с линейкой.

Прямая сама по себе состоит из бесконечного числа точек, чтобы провести прямую не нужно точек. Другое дело, если есть условие, то достаточно одной точки, но это будет прямая без направления, потому что ее можно провести в любую сторону пространства. Если же нужна прямая с направлением, то необходимо минимум 2 точки, они задают одно единственное положение прямой в пространстве.

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

Для этого необходимо как минимум две точки, то есть двух точек вполне достаточно для того, чтобы провести прямую линию. Одной точки не хватит для прямой линии, она так и останется точкой, но если есть ещ и вторая точка, то соединив их по прямой можно получить прямую линию.

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

Для этой нехитрой процедуры, думаю хватит и двух точек. А уж если поставить вопрос наоборот, сколько точек находится в прямой, то можно с уверенностью заявить, что число их бесконечно, ведб у прямой по идее, как и у палки нет ни начала ни конца.

Чтобы провести прямую, не нужно точек. Нужна только линейка и карандаш. Если же поставить условие, что пользоваться можно только точками, то потребуется бесконечное множество точек. Причм мощности континуума, то есть алеф-1.

Чтобы провести прямую, достаточно и одной точки (для привязки этой прямой в пространстве). Это является не необходимым, но достаточным условием. Причем через одну точку можно провести бесконечное число прямых. Другое дело, что через 2 точки можно провести только одну прямую.

Можно и без точек обойтись. Это же не отрезок или луч?

Источник

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

Задача

Как нас учат в школе на уроках геометрии, через две различные точки можно провести ровно одну прямую. Можно сказать, что пара точек определяет единственную прямую. Но если точек больше, то количество определяемых ими прямых может быть разным. Например, три точки в зависимости от своего расположения могут определять три прямые (если эти точки — вершины невырожденного треугольника) или одну прямую (если эти точки коллинеарны, то есть лежат на одной прямой). Если точек еще больше, то разных возможностей их взаимного расположения становится больше, поэтому и вариантов ответа на вопрос «сколько прямых определяют эти n точек?» будет много. Но в этой задаче предлагается разобраться с конкретными конфигурациями точек, а некоторые общие вопросы обсудим потом.

Читайте также:  Как построить яхту книга

а) На клетчатой бумаге возьмем квадрат со стороной пять клеток и отметим все точки внутри него и на его границе — получится 36 точек в виде квадратной решетки 6×6 (рис. 1). Сколько прямых определяют эти точки? А если точек 64 (в виде решетки 8×8)?

б) Длина ребер правильного тетраэдра равна 4. На каждом из них отмечены по три точки, разбивающие ребро на единичные отрезки. Вершины тетраэдра тоже отмечены. Сколько прямых определяют все отмеченные точки?

Подсказка

Попробуйте посчитать прямые, определяемые меньшим числом точек — 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 2 − 18m + 9 прямых. В нашей задаче m = 4, поэтому ответ — 177 прямых.

Читайте также:  Построй координатный луч и отметь все натуральные числа

Послесловие

Если применить рассуждения, которые мы использовали при ответе на первый вопрос задачи, то можно найти ответы и для других квадратов из n 2 точек. Вот они для 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, — а это самый, наверное, простой вид формулы, — то этот многочлен может иметь только 2, 3 или 4 степень. Используя приведенные выше первые несколько значений N, методом неопределенных коэффициентов можно показать, что не существует формулы в виде такого многочлена.

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

Так как любая прямая на плоскости однозначно задается угловым коэффициентом и одной точкой, то для каждого класса с k = a/b в точечном квадрате выделим те точки, которые определяют все прямые этого класса. При этом возможны два случая:
1) если b 2 точками можно вычислять по формуле:

где N = n — число горизонтальных прямых, N1 = 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 прямых, но вместо этого они определяют только одну прямую, содержащую ребро. Значит, все их нужно вычесть из общего числа и прибавить число прямых, содержащих ребра. Получится

Я формулу видел. Вопрос только в том, почему она приведена не в решении, а в послесловии.

Но я, всё-таки, не понял, как именно Вы программировали компьютер. В одном комментарии Вы пишете, что просто считали все прямые подряд, до тех пор, пока возможно рисовать новую прямую. А в другом пишете, что использовали формулу по классам параллельных.

По идее, это два разных алгоритма. И, кстати, было бы интересно сравнить временные затраты на вычисление по обоим алгоритмам в зависимости от N.

Уважаемый Олег Чечулин!
Формула приведена в послесловии, потому что она приводится для общего случая, а основной задачей является частный случай а) для квадратной решетки 6х6 и 8х8, и в решении демонстрируется прием, на основе которого выводится формула в общем случае. Этот прием положен в основу программы для подсчета прямых в решетке nxn, по редактор посчитал, что её лучше не приводить и опустил её.

Действительно, я привлекал компьютер для счета прямых, и не планировал после публикации на «Элементах» обнародовать свою программу, поэтому в одном из своих комментариев подстроился под Ваш вариант, чтобы подтвердить правильность Вашего подхода. Мой же, теперь Вы знаете, отличается от Вашего.

Для оптимизации счета можно отдельно убрать классы, описывающие прямые параллельные полю и диагоналям поля, и считать их по формуле
6*(n-1).
Учитывая симметрию классов, уменьшаем их в два раза, соответственно увеличим коэффициент до 4.

Учитывая вышеизложенное решение поля 6 на 6 клеток принимает следующих вид:

Источник

Adblock
detector