bulgakov

36. На сколько областей n прямых делят плоскость

Прямые разрезают плоскость на области. Чтобы областей было как можно больше, любые две прямые должны пересекаться, и никакие три не должны проходить через одну точку. Тогда каждая новая прямая пересекает все прежние в разных точках, эти точки делят её на n+1n+1 часть, и каждая часть добавляет одну новую область: xn+1=xn+n+1x_{n+1}=x_n+n+1. Отсюда xn=1+n(n+1)2x_n=1+\dfrac{n(n+1)}2.

Что пригодится из прошлого: рекуррентные соотношения и формула для p=1p=1 — xn+1=a+∑f(k)x_{n+1}=a+\sum f(k); сумма 1+2+⋯+n1+2+\dots+n. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача

Задача. На какое наибольшее число областей можно разбить плоскость с помощью nn прямых?

Обозначим это наибольшее число через xnx_n. Посмотрим на малые случаи:

  • без прямых плоскость — одна область: x0=1x_0=1;
  • одна прямая делит плоскость на две полуплоскости: x1=2x_1=2;
  • две пересекающиеся прямые образуют «крест» с четырьмя областями: x2=4x_2=4;
  • три прямые, попарно пересекающиеся и не проходящие через одну точку, образуют в середине треугольник и всего семь областей: x3=7x_3=7.

Вот эти случаи на рисунке (цифрами отмечены области):

одна прямая — 2 области:
       │
   1   │   2
       │

две пересекающиеся прямые —
4 области:
     1  │  2
 ───────┼───────
     3  │  4

три прямые в общем положении —
7 областей (● — пересечения):
             ╲ 1 ╱
               ●
     2       ╱ 4 ╲       3
           ╱       ╲
─────────●───────────●─────────
       ╱               ╲
  5  ╱         6         ╲  7
   ╱                       ╲

Как можно разрезать плоскость хуже. Три прямые через одну точку дают только 66 областей (как шесть кусочков пиццы). Три параллельные прямые — 44 области. Две параллельные и одна пересекающая обе — 66 областей.

Когда областей больше всего

Количество областей будет наибольшим, если:

  1. любые две прямые пересекаются (нет параллельных), и
  2. никакие три прямые не проходят через одну точку.

Такое расположение прямых называют общим положением.

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

Рекуррентное соотношение

Допустим, уже проведены nn прямых, которые разбивают плоскость на xnx_n областей. Проведём (n+1)(n+1)-ю прямую. Она пересекает каждую из nn прежних прямых, причём все точки пересечения различны (никакие три прямые не сходятся в одной точке). Эти nn точек делят новую прямую на n+1n+1 частей: два луча и n−1n-1 отрезков между соседними точками (при n=0n=0 точек нет, и прямая состоит из одной части).

n = 4 прежние прямые, новая
прямая пересекает их в 4 точках:

 ─────●─────●─────●─────●─────
   1     2     3     4     5
 5 частей = n + 1

Каждая из этих частей целиком лежит в одной прежней области и разрезает её на две (область выпукла: вместе с любыми двумя своими точками она содержит весь отрезок между ними — ведь это общая часть нескольких полуплоскостей. Поэтому прямая, проходящая через область, пересекает её по одному отрезку и разрезает ровно на две части). Значит, каждая часть добавляет ровно одну новую область, а всего добавляется n+1n+1. Больше добавить нельзя: новая прямая пересекает каждую прежнюю не более чем в одной точке, то есть делится не более чем на n+1n+1 часть.

Почему это именно наибольшее число. Возьмём любое расположение n+1n+1 прямых и уберём последнюю: оставшиеся nn прямых дают не более xnx_n областей, а возвращённая прямая добавляет не более n+1n+1. Значит, больше xn+n+1x_n+n+1 областей не получится. А достичь этого числа можно на каждом шаге: выберем направление, которого нет среди направлений прежних прямых, и сдвинем новую прямую так, чтобы она не прошла ни через одну из прежних точек пересечения (каждая такая точка запрещает лишь одно положение при сдвиге). Тогда новая прямая пересекает все прежние, и все её точки пересечения различны.

Поэтому наибольшее число областей подчиняется соотношению:

xn+1=xn+n+1,n=0,1,2,…,x0=1.\boxed{x_{n+1}=x_n+n+1,\qquad n=0,1,2,\dots,\qquad x_0=1}.

Решение

Это рекуррентное соотношение вида xn+1=xn+f(n)x_{n+1}=x_n+f(n) с f(n)=n+1f(n)=n+1 и a=x0=1a=x_0=1. По формуле (2) из прошлой главы (для p=1p=1: xn+1=a+∑k=0nf(k)x_{n+1}=a+\sum_{k=0}^{n}f(k))

xn+1=1+∑k=0n(k+1)=1+(1+2+⋯+(n+1))=1+(n+1)(n+2)2.x_{n+1}=1+\sum_{k=0}^{n}(k+1)=1+(1+2+\dots+(n+1))=1+\frac{(n+1)(n+2)}2.

Заменим n+1n+1 на nn:

xn=1+n(n+1)2.\boxed{x_n=1+\frac{n(n+1)}2}.
nn xnx_n xn−xn−1x_n-x_{n-1}
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

Каждая строка таблицы — новая прямая, она добавляет столько областей, каков её номер nn: x3=4+3=7x_3=4+3=7, x4=7+4=11x_4=7+4=11 и так далее.

То же через сочетания ((nk)\dbinom nk — число способов выбрать kk из nn, см. сочетания). 1+n(n+1)2=1+n+n(n−1)2=(n0)+(n1)+(n2)1+\dfrac{n(n+1)}2=1+n+\dfrac{n(n-1)}2=\dbinom n0+\dbinom n1+\dbinom n2: одна область есть «с самого начала» (вся плоскость), по одной добавляется за каждую прямую и ещё по одной — за каждую пару прямых (за точку их пересечения).

Частые ошибки

  • Забыть условия общего положения. Если прямые параллельны или несколько проходят через одну точку, областей меньше.
  • Считать, что новая прямая даёт nn новых областей. Точек пересечения nn, а частей n+1n+1: отрезков между точками n−1n-1, да ещё два луча.
  • Потерять область при n=0n=0. Без прямых плоскость — одна область.
  • Не заменить n+1n+1 на nn в конце. Формула (2) даёт xn+1x_{n+1}.

Проверь себя

1. Найдите наибольшее число областей, на которые 55 прямых делят плоскость.

Решение

x5=1+5⋅62=16x_5=1+\dfrac{5\cdot6}2=16.

2. Сколько областей добавит восьмая прямая?

Решение

Восьмая прямая пересекает 77 прежних в 77 точках, которые делят её на 88 частей: 88 новых областей. Проверка по таблице: 37−29=837-29=8.

3. Какое наибольшее число областей получится с помощью 1010 прямых?

Решение

x10=1+10⋅112=56x_{10}=1+\dfrac{10\cdot11}2=56.

4. Две прямые параллельны, третья пересекает обе. На сколько областей разбита плоскость?

Решение

Две параллельные прямые делят плоскость на 33 области. Третья пересекает обе в двух точках и состоит из 33 частей, поэтому добавляет 33 области: 3+3=63+3=6. Это меньше наибольшего значения x3=7x_3=7: нарушено условие «никакие две прямые не параллельны».

Итог

  • Наибольшее число областей достигается, когда любые две прямые пересекаются, а три через одну точку не проходят.
  • (n+1)(n+1)-я прямая делится nn точками на n+1n+1 частей, каждая добавляет одну область: xn+1=xn+n+1x_{n+1}=x_n+n+1, x0=1x_0=1.
  • Решение: xn=1+n(n+1)2=(n0)+(n1)+(n2)x_n=1+\dfrac{n(n+1)}2=\dbinom n0+\dbinom n1+\dbinom n2; первые значения 1,2,4,7,11,16,22,…1,2,4,7,11,16,22,\dots
ПрактикаЗагружаем тест…