Сколько прямых можно провести через 3 точки

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

Как нас учат в школе на уроках геометрии, через две различные точки можно провести ровно одну прямую. Можно сказать, что пара точек определяет единственную прямую. Но если точек больше, то количество определяемых ими прямых может быть разным. Например, три точки в зависимости от своего расположения могут определять три прямые (если эти точки — вершины невырожденного треугольника) или одну прямую (если эти точки коллинеарны, то есть лежат на одной прямой). Если точек еще больше, то разных возможностей их взаимного расположения становится больше, поэтому и вариантов ответа на вопрос «сколько прямых определяют эти 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(n) ≥ n 2 . Используя первый факт, получим верхнюю оценку: N(n) ≤ n 2 (n 2 − 1)/2 — это число прямых, определяемых n 2 точками общего положения.

Это значит, что если существует формула 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 2 точками можно вычислять по формуле:

\[ N(n)=2(N_0+N_1)+4\sum\limits_^\sum\limits_^N\left(\frac ab\right), \]

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

Показать комментарии (24)
Свернуть комментарии (24)

Олег Чечулин 27.07.2018 09:19 Ответить

По-хорошему, то, что приведено в послесловии, и должно быть в решении случая «а», а то, что приведено в решении случая «а» — это простой подсчёт на уровне первоклассника (если он, конечно, умеет пользоваться линейкой); думаю, мало кто пошёл по такому малоинтересному пути.

Nik 27.07.2018 09:54 Ответить

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

Олег Чечулин 28.07.2018 15:04 Ответить

Нарисовал прямую — увеличь счётчик. Когда не можешь больше рисовать — огласи результат.

Nik 28.07.2018 18:21 Ответить

Согласен, для малых квадратов это естественный подход! А что делать с большими квадратами? Например, для квадрата со 100 точками. Теоретически, да, можно, а практически — не получится, всё сливается! А предложенный способ разбиения на классы параллельных прямых — работает!

Олег Чечулин 29.07.2018 14:23 Ответить

А вот для больших квадратов как раз и нужно то, что написано в послесловии.

Nik 29.07.2018 15:51 Ответить

Для больших квадратов на помощь я привлекал компьютер, который делает тоже самое, что человек для малых квадратов, заставив его, как Вы написали «Нарисовал прямую — увеличь счётчик. Когда не можешь больше рисовать — огласи результат». Всё верно!

Олег Чечулин 29.07.2018 17:36 Ответить

Тогда зачем эти заморочки с классами? ��

Nik 29.07.2018 20:41 Ответить

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

Олег Чечулин 30.07.2018 07:28 Ответить

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

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

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

Nik 30.07.2018 11:17 Ответить

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

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

Мы с Вами действительно говорим о разных алгоритма подсчета прямых. Ваш «Нарисовал — посчитал» и мой «Подсчет в классах параллельных». Согласен, времязатратные сравнения были бы интересны.

Angl 27.07.2018 11:45 Ответить

Именно поэтому я, например, бросил решать задачу. Только у меня был немного другой подход. Сначала посчитать количество уникальных пар точек — n*(n-1)/2=630. Теперь нужно посчитать количество прямых, содержащих 6, 5, 4, 3 точки, и уменьшить исходное число пар на количество дублей в каждой такой прямой (например, прямых длиной 6 — 14 штук, для каждой лишних пар 5+4+3+2=14), то есть вычитаем 288 и так далее.

Nik 29.07.2018 21:58 Ответить

Тоже интересный подход! Надо довести до победы!

erwins 27.07.2018 10:33 Ответить

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

Nik 27.07.2018 11:33 Ответить

Неплохо было бы ее найти!

erwins 27.07.2018 12:18 Ответить

количество k суммируем все числа от 1 до N
Если разложение числа p_1^n_1*p_2^n_p. тогда
p_1^(n_1-1)*p_2^(n_2-1). *(p_1-1)*(p_2-1)

Nik 29.07.2018 22:05 Ответить

Непонятно! Это что за формула?

erwins 30.07.2018 13:01 Ответить

В общем подсчитал количество несократимых дробей
m/n 0

1 3 5 9 11 17 21 27 31 41 45 57 63 71 79 95 101 119 127 139 149 171 179 199 211 229 241 269 277 307 323 343 359 383 395 431 447 471 487 527 539 581 601 625 647 693 709 751 771 803 827 879 897 937 961 997 1025 1083 1099 1159 1189 1225 1257 1305 1325 1391 1423 1447 1471 1541 1565 1637 1655 1695 1731 1791 1815 1893 1925 1979 2019 2101 2125 2189 2231 2317

оценить при большом количество можно так
n*n*(1-1/2*1/2)*(1-1/3*2/3)*(1-1/5*4/5).

MaksimD 29.07.2018 03:43 Ответить

Решал методом разбиения на подобные классы, но ответы не сошлись.
В поле 6 на 6 получилось 266. В решении последний член в скобках «9», к какому угловому коэффициенту относится?
8 на 8 получилось 1002 варианта.

Nik 29.07.2018 09:45 Ответить

Подобные классы чего? Проверяйте свои решения. Ответы правильные, но слагаемое «9» похоже лишнее. В послесловии есть ссылка на последовательность под номером A018808, можно посмотреть.

MaksimD 29.07.2018 15:30 Ответить

Нашел ошибку у себя, теперь при 36 точках сходится ответ.
Разбивал параллельные прямые на классы, заданные диагональю прямоугольника.
Если n- количество точек на стороне поля, a и b — ширина и высота прямоугольника, то всего прямоугольник может занять k различных позиций,
по ширине может быть n-a различных вариантов, по высоте n-b, всего
k=(n-a)(n-b)
Классы, где a=0 или b=0 описывают прямые, параллельные сторонам поля.
А если a=b, то параллельные диагонали поля.
Заметим, что каждый класс включает две группы параллельных прямых, т.к. есть две диагонали в прямоугольниках, их задающих. За исключением классов с a=0 или b=0 конечно.
Для учета накладывающихся прямых пользуемся следующей логикой:
1. Если несколько положений прямоугольника со сторонами a,b задают одну и ту же прямую, то эта же прямая задаётся прямоугольником большего размера, со сторонами , кратными 2 к исходному.
2. Прямоугольник с размерами, кратными a,b , не может задать прямую, не включенную в класс a,b.
3. Если поле вмещает прямоугольники с размерами a,b и 2a,2b, то количество уникальных прямых равно разнице между количествами прямых в классах a,b- 2a,2b.
4. Все остальные классы, кратные a,b не учитываем, т.к. они не задают никаких новых прямых.

Рассмотрим пример, при поле n=4
Если не убирать симметричные классы, то всего получается 15 классов ( исключаем класс 0,0)
Получается следующая таблица. По горизонтали значения параметра «a» класса, по вертикали параметр «b», размеры классов «k» считаю по формуле (n-a)(n-b):
__0 __I__ II__ III
________________
0 | -__12_ 8__ 4
_I |12 _9_ 6__ 3
II | 8__ 6 _4 __2
III | 4 _3__ 2_ 1

Можно заметить что классы 0I , 0II, 0III и ему симметричный I0,II0,II0 описывают прямые, параллельные границам поля, а I I, II II, III III — их диагонали.
Воспользуемся описанной логикой для учета совпадающих прямых:
__0 ___I__II__ III
________________
0 | -_ _12_ -8__ 0
I _| 12_ 9 __6 __3
II | -8__ 6 _-4 __2
III | 0__ 3__ 2__ 0

Сложим значения классов при «а»=0 или «b»=0 в одну сумму S1 , все остальные классы в другую сумму S2. Умножим S2 на 2, т.к. каждый включенный класс описывает две прямые.
Итого получим: (12-8+0+12-8+0)+2*(9+6+3+6-4+2+3+2+0)=8+2*27=62

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

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

___I__ II__ III __IV
V _5 __4 __3 __2
IV 10_ -8 __6
III 15 __12
II _20

MaksimD 29.07.2018 15:50 Ответить

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

Nik 29.07.2018 15:59 Ответить

MaksimD, похоже Ваша программа считает некоторые прямые дважды! Прочитав Ваш комментарий, я понял, что нас похожие подходы к построению программы.
Если Вам интересно, то могу выложить мою программу, которая считает прямые для больших квадратов и их число совпадает с A018808.

MaksimD 29.07.2018 16:59 Ответить

Будет интересно посмотреть на Вашу программу

Nik 29.07.2018 17:50 Ответить

Формулу N(n) приведенную в послесловии, можно алгоритмизировать. Ниже приведена программа, написанная лет 20 назад на языке программирования Turbo Basic:

rem Число прямых
cls:
for n=2 to 100
s=0
for b=2 to n-1
for a=1 to b-1
x=a: y=b
1 if x=y then 2
if x>y then x=x-y else y=y-x
goto 1
2 if x<>1 then goto 3
if n>2*b then k=(a+b)*n-3*a*b
if ns=s+k
3 next a,b
p=6*(n-1)+4*s
print «n=»n,»N=»p
next n
end

Тест по стереометрии для учащихся 10 класса
тест по геометрии (10 класс)

1. Сколько прямых можно провести через одну точку пространства?

1) Ни одной. 2) Одну. 3) Две . 4) Бесконечно много.

2. Сколько плоскостей можно провести через одну точку пространства?

1) Ни одной. 2) Одну . 3) Две. 4) Бесконечно много.

3. Сколько прямых можно провести через две точки пространства?

1) Ни одной. 2) Одну. 3) Две. 4) Бесконечно много.

4. Сколько плоскостей можно провести через две точки пространства?

1) Ни одной. 2) Одну. 3) Две. 4) Бесконечно много.

5. Сколько прямых можно провести через различные пары из трех точек пространства, не принадлежащих одной прямой?

1) Ни одной. 2) Три. 3) Шесть. 4) Бесконечно много.

6. Сколько плоскостей можно провести через три точки пространства, не принадлежащие одной прямой?

1) Ни одной. 2) Одну. 3) Три. 4) Бесконечно много.

7. Сколько плоскостей можно провести через три точки пространства, принадлежащие одной прямой?

1) Ни одной. 2) Одну. 3) Три. 4) Бесконечно много.

8. Сколько общих точек имеют две пересекающиеся плоскости?

1) Одну. 2) Две. 3) Три. 4) Бесконечно много.

9. В каком случае центры трех шаров принадлежат одной плоскости?

1) Радиусы шаров совпадают.

2) Центры шаров принадлежат одной прямой.

10. Сколько плоскостей можно провести через три вершины куба?

1) Одну. 2) Три. 3) Шесть. 4) Бесконечно много.

11. Какое наибольшее число прямых можно провести через различные пары четырех точек пространства?

1) Четыре. 2) Пять. 3) Шесть. 4) Восемь.

12. Какое наибольшее число прямых можно провести через различные пары из пяти точек пространства?

1) 5. 2) 10. 3) 15. 4) 25.

13. Найдите число диагоналей прямоугольного параллелепипеда.

1) 2. 2) 4. 3) 6. 4) 8.

14. Найдите число диагоналей 6-угольной призмы.

1) 6. 2) 12 . 3) 9. 4) 18.

15. Какой многоугольник лежит в основании пирамиды, имеющей 12 ребер?

16. Какой многоугольник лежит в основании призмы, имеющей 36 ребер?

17. Призма имеет 18 вершин. Какой многоугольник лежит в ее основании?

18. Пирамида имеет 10 вершин. Какой многоугольник лежит в ее основании?

19. Призма имеет 18 диагоналей. Определите ее вид.

20. Сколько диагоналей имеет 7-угольная пирамида?

1) Ни одной. 2) 6. 3) 7. 4) 14.

Сколько прямых можно провести через 3 точки

§ 1. Прямая. Луч. Отрезок. Ломаная линия.

1. 1) Через произвольно взятую точку провести различные прямые. Сколько прямых можно провести через одну точку?

2) Через две данные точки провести прямую. Сколько прямых можно провести через две точки? Сколько кривых линий можно провести через две точки?

3) Через две данные точки проведены две различные линии. Могут ли обе линии быть прямыми? Почему?

2. 1) Даны три точки, не лежащие на одной прямой. Через каждые две из них провести прямые. Сколько таких прямых можно провести?

2) На чертеже 1 даны четыре точки. Через каждую пару точек провести прямые. Сколько всего будет проведено прямых?

3. 1) Сколько общих точек имеют две пересекающиеся прямые? 2) Могут ли две различные прямые иметь две общие точки? Почему?

4. 1) Из одной точки провести три различных луча. Сколько лучей можно провести, начало которых находится в данной точке?

2) Назвать все лучи, образовавшиеся при пересечении двух прямых АВ и CD (точку пересечения прямых обозначить буквой О).

5. Сколько всего отрезков изображено на чертеже 2? Назвать их.

6. На чертеже 3 изображены две ломаные линии. Из скольких отрезков состоит каждая ломаная линия? Назвать их.

7. Сравнить на глаз отрезки а и b, данные на чертеже 4, и проверить результат при помощи циркуля или масштабной линейки.

Урок 10. Подготовка к контрольной работе. 1. Сколько прямых можно провести через 2 точки? 2. Сколько общих точек могут иметь 2 прямые? 3. Что такое отрезок? — презентация

Презентация по предмету «Математика» на тему: «Урок 10. Подготовка к контрольной работе. 1. Сколько прямых можно провести через 2 точки? 2. Сколько общих точек могут иметь 2 прямые? 3. Что такое отрезок?». Скачать бесплатно и без регистрации. — Транскрипт:

1 Урок 10. Подготовка к контрольной работе. 1. Сколько прямых можно провести через 2 точки? 2. Сколько общих точек могут иметь 2 прямые? 3. Что такое отрезок? 4. Что такое луч? Как обозначаются лучи? 5. Какая фигура называется углом? Что такое вершина и стороны угла? 6. Какой угол называется развернутым? 7. Какие фигуры называются равными? 8. Как сравнить 2 отрезка? 9. Какая точка называется серединой отрезка? 10. Как сравнить 2 угла? 11. Какой луч называется биссектрисой угла? 12. Точка С делит отрезок АВ на 2 отрезка. Как найти длину отрезка АВ? 13. Какими инструментами пользуются для измерения расстояний? 14. Луч ОС делит угол АОВ на 2 угла. Как найти градусную меру угла АОВ? 15. Какой угол называется острым, прямым, тупым? 16. Какие углы называются смежными, их свойство? 17. Какие углы называются вертикальными, их свойство? 18. Какие прямые называются перпендикулярными?

2 Решение задач. Устная работа. Задача 1. а с Угол 1 = 29 градусов. Найти остальные углы. Задача 2. Прямые АВ, CD и КМ пересекаются в точке О, причем угол АОМ=47 градусов, угол АОС=32 градуса. Найти углы СОК, КОВ, BOD, DOM. A B C D K M O

3 Решение задач. Задача 3. Через точку О проведены три прямые так, что угол АОС=142 градуса, угол АОВ=91 градус. Найти углы 1, 2, 3, 4. С В А О

4 Решение задач. 1. Точки А, В, С лежат на одной прямой. Найдите длину отрезка ВС, если АВ=2,7 м, АС=3,2 м. Сколько решений имеет задача? 2. Найдите углы, которые получаются при пересечении двух прямых, если сумма трех из этих углов равна 270 градусов. 3. Найдите угол между биссектрисой и продолжением одной и сторон данного угла, равного 50 градусам. АО В С D