17. Комбинаторные задачи геометрического содержания.

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

1. На плоскости проведено прямых, причем никакие две из них не параллельны и никакие три не пересекаются в одной точке. Сколько точек пересечения имеют эти прямые?

Каждая точка пересечения однозначно определяется парой проходящих через нее прямых. При этом порядок прямых роли не играет. Поэтому искомое число точек пересечения равно числу сочетаний из по два, т. е.

2. Найти число точек пересечения диагоналей, лежащих внутри выпуклого -угольника, если никакие три из них не пересекаются в одной точке,

Рис. 8

Если взять любые четыре вершины многоугольника, то через них можно провести четыре диагонали (рис. 8), имеющие две точки пересечения (кроме вершин). Из этих точек лишь одна лежит внутри многоугольника. Значит, любая внутренняя точка пересечения диагоналей однозначно определяется выбором четверки вершин, причем порядок вершин роли не играет. Итак, число таких четверок (а тем самым и внутренних точек пересечения диагоналей) равно

3. На одной из параллельных прямых линий отмечено 10 точек, а на другой — 7 точек. Каждая точка одной прямой соединена с каждой точкой другой прямой. Найдите число точек пересечения полученных отрезков, если никакие три отрезка не имеют общей точки (общие точки на концах отрезков не считаются).

Сделав рисунок, мы убеждаемся, что любая точка пересечения определяется однозначно, если задать пару точек на одной прямой и пару точек на второй прямой. При этом порядок точек на прямых роли не играет. Поэтому в обоих случаях речь идет о выборе подмножеств. Но из -множества можно выбрать -подмножеств, а из -множества — -подмножеств. По правилу произведения получаем, что общее число точек пересечения равно , т. е. 945.