36. На сколько областей n прямых делят плоскость
Прямые разрезают плоскость на области. Чтобы областей было как можно больше, любые две прямые должны пересекаться, и никакие три не должны проходить через одну точку. Тогда каждая новая прямая пересекает все прежние в разных точках, эти точки делят её на часть, и каждая часть добавляет одну новую область: . Отсюда .
Что пригодится из прошлого: рекуррентные соотношения и формула для — ; сумма . Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача
Задача. На какое наибольшее число областей можно разбить плоскость с помощью прямых?
Обозначим это наибольшее число через . Посмотрим на малые случаи:
- без прямых плоскость — одна область: ;
- одна прямая делит плоскость на две полуплоскости: ;
- две пересекающиеся прямые образуют «крест» с четырьмя областями: ;
- три прямые, попарно пересекающиеся и не проходящие через одну точку, образуют в середине треугольник и всего семь областей: .
Вот эти случаи на рисунке (цифрами отмечены области):
одна прямая — 2 области:
│
1 │ 2
│
две пересекающиеся прямые —
4 области:
1 │ 2
───────┼───────
3 │ 4
три прямые в общем положении —
7 областей (● — пересечения):
╲ 1 ╱
●
2 ╱ 4 ╲ 3
╱ ╲
─────────●───────────●─────────
╱ ╲
5 ╱ 6 ╲ 7
╱ ╲
Как можно разрезать плоскость хуже. Три прямые через одну точку дают только областей (как шесть кусочков пиццы). Три параллельные прямые — области. Две параллельные и одна пересекающая обе — областей.
Когда областей больше всего
Количество областей будет наибольшим, если:
- любые две прямые пересекаются (нет параллельных), и
- никакие три прямые не проходят через одну точку.
Такое расположение прямых называют общим положением.
Пояснение: когда мы добавляем новую прямую, она делится точками пересечения со старыми на части, и каждая часть разрезает одну область. Чем больше различных точек пересечения, тем больше частей. Параллельные прямые не пересекаются, а три прямые через одну точку дают на новой прямой лишь одну точку вместо двух.
Рекуррентное соотношение
Допустим, уже проведены прямых, которые разбивают плоскость на областей. Проведём -ю прямую. Она пересекает каждую из прежних прямых, причём все точки пересечения различны (никакие три прямые не сходятся в одной точке). Эти точек делят новую прямую на частей: два луча и отрезков между соседними точками (при точек нет, и прямая состоит из одной части).
n = 4 прежние прямые, новая
прямая пересекает их в 4 точках:
─────●─────●─────●─────●─────
1 2 3 4 5
5 частей = n + 1
Каждая из этих частей целиком лежит в одной прежней области и разрезает её на две (область выпукла: вместе с любыми двумя своими точками она содержит весь отрезок между ними — ведь это общая часть нескольких полуплоскостей. Поэтому прямая, проходящая через область, пересекает её по одному отрезку и разрезает ровно на две части). Значит, каждая часть добавляет ровно одну новую область, а всего добавляется . Больше добавить нельзя: новая прямая пересекает каждую прежнюю не более чем в одной точке, то есть делится не более чем на часть.
Почему это именно наибольшее число. Возьмём любое расположение прямых и уберём последнюю: оставшиеся прямых дают не более областей, а возвращённая прямая добавляет не более . Значит, больше областей не получится. А достичь этого числа можно на каждом шаге: выберем направление, которого нет среди направлений прежних прямых, и сдвинем новую прямую так, чтобы она не прошла ни через одну из прежних точек пересечения (каждая такая точка запрещает лишь одно положение при сдвиге). Тогда новая прямая пересекает все прежние, и все её точки пересечения различны.
Поэтому наибольшее число областей подчиняется соотношению:
Решение
Это рекуррентное соотношение вида с и . По формуле (2) из прошлой главы (для : )
Заменим на :
| 0 | 1 | — |
| 1 | 2 | 1 |
| 2 | 4 | 2 |
| 3 | 7 | 3 |
| 4 | 11 | 4 |
| 5 | 16 | 5 |
| 6 | 22 | 6 |
| 7 | 29 | 7 |
| 8 | 37 | 8 |
| 9 | 46 | 9 |
| 10 | 56 | 10 |
Каждая строка таблицы — новая прямая, она добавляет столько областей, каков её номер : , и так далее.
То же через сочетания ( — число способов выбрать из , см. сочетания). : одна область есть «с самого начала» (вся плоскость), по одной добавляется за каждую прямую и ещё по одной — за каждую пару прямых (за точку их пересечения).
Частые ошибки
- Забыть условия общего положения. Если прямые параллельны или несколько проходят через одну точку, областей меньше.
- Считать, что новая прямая даёт новых областей. Точек пересечения , а частей : отрезков между точками , да ещё два луча.
- Потерять область при . Без прямых плоскость — одна область.
- Не заменить на в конце. Формула (2) даёт .
Проверь себя
1. Найдите наибольшее число областей, на которые прямых делят плоскость.
Решение
.
2. Сколько областей добавит восьмая прямая?
Решение
Восьмая прямая пересекает прежних в точках, которые делят её на частей: новых областей. Проверка по таблице: .
3. Какое наибольшее число областей получится с помощью прямых?
Решение
.
4. Две прямые параллельны, третья пересекает обе. На сколько областей разбита плоскость?
Решение
Две параллельные прямые делят плоскость на области. Третья пересекает обе в двух точках и состоит из частей, поэтому добавляет области: . Это меньше наибольшего значения : нарушено условие «никакие две прямые не параллельны».
Итог
- Наибольшее число областей достигается, когда любые две прямые пересекаются, а три через одну точку не проходят.
- -я прямая делится точками на частей, каждая добавляет одну область: , .
- Решение: ; первые значения
