Комбинаторная задача о числе точек пересечения прямых

1.

Комбинаторная задача
о числе точек пересечения
прямых

2.

Известная комбинаторная задача
1) Виленкин Н.Я., Виленкин А.Н.,
Виленкин П.А. Комбинаторика.
– М.: МЦНМО, 2006.
2) Смирнова И.М., Смирнов
В.А. Комбинаторные задачи по геометрии
(Библиотечка "Первого сентября".
Математика. Вып. 5 (11)).
– М.: Чистые пруды, 2006.

3.

Задача о количестве точек
пересечения n прямых
На плоскости проведены n прямых, среди
которых нет ни одной пары параллельных
прямых и ни одной тройки прямых,
пересекающихся в одной точке. Найти число
точек пересечения таких прямых.
Пример.
n=5,
10 точек
пересечения

4.

Цели работы
1) обобщить одну из известных
комбинаторных задач по геометрии и
получить полное решение новых задач;
2) показать возможность применения
метода рекуррентных соотношений для
решения комбинаторных задач по
геометрии.

5.

Задача 1. Наличие параллельных прямых
На плоскости провели n прямых, среди
которых k параллельных прямых и никакие три
прямые не проходят через одну точку. Сколько
точек пересечения прямых получилось?
Пример 1. n=8, k=3
25 точек пересечения
Пример 2. n=8, k=4
22 точки пересечения

6.

О методе рекуррентных соотношений
Метод сведения комбинаторной задачи к
аналогичной задаче для меньшего числа
предметов с помощью некоторого соотношения
называется методом рекуррентных соотношений.
Пользуясь рекуррентным соотношением,
задачу с n предметами можно свести к задаче с n–1
предметом, потом к задаче с n–2 предметами и т.д.
Во многих случаях из рекуррентного
соотношения удается получить явную формулу для
решения комбинаторной задачи.

7.

Решение задачи №1
1) Наглядное нахождение закономерностей
2) Нахождение формулы, позволяющей
найти количество точек пересечения по
любым значениям n и k

8.

Нахождение числа
точек пересечения
m=4
m=3
m=2
k 2
k 3
k 4

9.

Таблица и рекуррентные соотношения
k
Прямые
общего
положения
m
1
2
3
4
5
Параллельные прямые
2
3
4
5
2
3
4
5
5
7
9
11
9
12
15
18
14
18
22
26
20
25
30
35
Обозначим: x ( m; k ) – число точек пересечения
m прямых общего положения и k параллельных
прямых

10.

Рекуррентные соотношения
1)
При
добавлении одной
(новой)
параллельной прямой количество точек
пересечения увеличится на m. Получаем:
x ( m; k 1) x ( m; k ) m
2) При добавлении одной (новой) прямой
общего положения количество точек
пересечения увеличится на k m . Получаем:
x ( m 1; k ) x ( m; k ) m k

11.

Нахождение формулы
x ( 2; k ) x (1; k ) 1 k
x (3; k ) x ( 2; k ) 2 k
x ( 4; k ) x (3; k ) 3 k
x ( m; k ) x ( m 1; k ) m 1 k
x ( m; k ) x (1; k ) 1 2 (m 1) k ( m 1)
1 ( m 1)
( m 1) k ( m 1).
2
m(m 1)
x(m; k )
m k .
2

12.

Задача 2. Наличие пар параллельных
прямых
На плоскости провели n прямых, среди
которых k пар параллельных прямых (прямые в
разных парах непараллельные) и никакие три
прямые не проходят через одну точку. Сколько
точек пересечения прямых получилось?
Пример 1. n=5, k=2
19 точек пересечения
Пример 2. n=6, k=3
33 точки пересечения

13.

Решение задачи №2
1) Наглядное нахождение закономерностей
2) Нахождение формулы, позволяющей
найти количество точек пересечения по
любым значениям n и k

14.

Нахождение числа
точек пересечения
m=4
m=3
m=2
k 2
k 3
k 4

15.

Таблица и рекуррентные соотношения
k
Прямые
общего
положения
m
1
2
3
4
5
Пары параллельных прямых
2
3
4
5
2
8
18
32
5
13
25
41
9
19
33
51
14
26
42
62
20
34
52
74
Обозначим: x ( m; k ) – число точек пересечения
m прямых общего положения
параллельных прямых
и
k
пар

16.

Рекуррентные соотношения
1) При добавлении одной (новой) пары
параллельных прямых количество точек
пересечения
увеличится
на
2m 2k 2k 2(m 2k ) . Получаем:
x(m; k 1) x(m; k ) 2(m 2k ) .
2) При добавлении одной (новой) прямой
общего
положения
количество
точек
пересечения увеличится на m 2k . Получаем:
x(m 1; k ) x(m; k ) m 2k .

17.

Нахождение формулы
x(2, k ) x(1, k ) 1 2k
x(3, k ) x(2, k ) 2 2k
x(m, k ) x(m 1, k ) m 1 2k
x(m; k ) x(1; k ) 1 2 (m 1) 2k (m 1)
1 (m 1)
(m 1) 2k (m 1).
2
m( m 1)
x ( m; k )
2km 2k ( k 1)
2

18.

Выводы
Мы рассмотрели два варианта обобщения
известной комбинаторной задачи.
В первом варианте мы нашли количество
точек пересечения n прямых, среди которых k
параллельных прямых.
Количество
точек
пересечения
определяется по формуле:
m( m 1)
x ( m; k )
m k ,
2
где m – число прямых общего положения и k –
число параллельных прямых (общее число
прямых n m k ).

19.

Выводы
Во втором варианте рассматривались
пары параллельных прямых, и было найдено
количество точек пресечения n прямых среди
которых k пар параллельных прямых.
Количество
точек
пересечения
определяется по формуле:
m(m 1)
x(m; k )
2km 2k (k 1) ,
2
где m – число прямых общего положения и k
– число пар параллельных прямых (общее
число прямых n m 2k ).

20.

СПАСИБО ЗА
ВНИМАНИЕ!