Прямые на плоскости

Рассмотрите несколько случаев для небольших \(n\), посчитайте число частей в каждом случае и постарайтесь найти закономерность.

Заметим, что число частей плоскости, на которые прямые делят плоскость, совершенно не зависит от прямых, которые провела Лена, так как они параллельны, а \(n\) параллельных прямых разбивают плоскость всегда на \(n+1\) часть. Поскольку мы ищем наибольшее число частей, то никакие две из Мишиных прямых не должны быть параллельны и никакие три прямые не должны проходить через одну точку. Нарисуем картинки для \(n\) = 1, 2, 3, 4 и посчитаем число получившихся при этом частей \(k(n)\) = 4, 10, 19, 31, соответственно (рис. 1).

Рис. 1.

Понятно, что с добавлением прямых число частей разбиения плоскости увеличивается, но как? Давайте выясним. Заметим, что добавление \((n+1)\)-й параллельной прямой увеличивает число частей на \(n+1\), потому что она пересекает каждую из \(n\) непараллельных прямых. А добавление \((n+1)\)-й непараллельной прямой увеличивает число частей на \(2n+2\) части, потому что эта прямая пересекает \(n+1\) параллельных прямых и \(n\) непараллельных прямых, то есть пересекает \(2n+1\) прямую. Значит, число частей плоскости при добавлении одной параллельной и одной непараллельной прямой увеличивается на \((n+1)+(2n+2)=3n+3\). Такое поведение похоже на одну известную последовательность — треугольные числа, которые, напомню, растут со «скоростью» \(n\) (то есть разность между \(n\)-м и предыдущим треугольными числами равна \(n\)). Для треугольных чисел, как известно, имеется явная формула: \(T_n=\frac12n(n+1)\). Значит, и для \(k(n)\) формула будет квадратичной.

Чтобы ее найти, можно воспользоваться методом неопределенных коэффициентов. Положим \(k(n)=an^2+bn+c\). Параметры \(a\), \(b\), \(c\) вычислим с помощью найденных выше значений \(k(1)=4\), \(k(2)=10\), \(k(3)=19\), благодаря которым можно составить систему из трех уравнений с тремя неизвестными:

Ее решением является тройка чисел \(a=\frac32\), \(b=\frac32\), \(c=1\), поэтому формула для вычисления числа частей плоскости такова: \(k(n)=\frac32n^2+\frac32n+1=\frac32n(n+1)+1\). Непосредственной проверкой убеждаемся, что формула работает при других значениях \(n\).

Если предложенное решение показалось вам малоубедительным, то можно проверить полученную формулу методом математической индукции. Докажем, что если мы знаем, что когда Лена и Миша провели по \(n\) прямых, получится \(k(n)=\frac32n(n+1)+1\) частей плоскости, то из этого следует, что когда они проведут по \(n+1\) прямой, получится \(k(n+1)=\frac32(n+1)(n+2)+1\) частей.

В самом деле, база индукции выполняется — это легко проверить вручную, что было проделано выше. Покажем, что верен и индукционный переход. Опять же, выше мы видели, что переходе от \(n\) к \(n+1\) число частей плоскости меняется на \(3n+3\). Значит, \(k(n+1)=k(n)+3n+3=\frac32n(n+1)+1+3n+3\). После упрощения последнее выражение и правда превращается в \(\frac32(n+1)(n+2)+1\).

Можно предложить еще один вывод формулы \(k(n)\), основанный на результате задачи из книги американского математика венгерского происхождения Д. Пойа «Математика и правдоподобные рассуждения»: На сколько частей разбивают плоскость \(n\) прямых общего положения?

Уточним, что прямые общего положения — это множество прямых, среди которых нет параллельных и никакие три не проходят через одну точку. Например, слева на рис. 2 синим цветом изображены \(n\) прямых общего положения. В решении задачи показано, что число частей плоскости в этом случае можно посчитать по формуле \(a(n)=\frac12n(n+1)+1\). Добавим к ним еще \(n\) параллельных прямых, каждая из которых по отношению к ранее проведенным является прямой общего положения (рис. 2, в центре). Каждая их этих \(n\) параллельных прямых пересекается с непараллельными прямыми в \(n\) точках, которые разбивают их на \(n+1\) интервалов. Значит, проведение одной прямой увеличивает число частей плоскости на \(n+1\), а проведение \(n\) параллельных прямых увеличивает число частей на \(n(n+1)\), значит, \(k(n)=a(n)+n(n+1)=\frac12n(n+1)+1+n(n+1)\) (рис. 2, справа). После упрощения получим все ту же формулу \(k(n)=\frac32n(n+1)+1\).

Рис. 2.

Для подсчета числа частей в нашей задаче можно поступить совсем просто. Лена провела \(n\) параллельных прямых, которые разбили плоскость на \(n+1\) часть. Первая прямая, проведенная Мишей, делит плоскость на \(2(n+1)\) частей, то есть увеличивает число частей на \((n+1)\). Вторая прямая, проведенная Мишей, увеличивает число частей на \((n+2)\), третья прямая — на \((n+3)\), и так далее, ... \(n\)-я прямая — на \((n+n)\). Поэтому общее число частей равно сумме \(k(n)=(n+1)+(n+1)+(n+2)+...+(n+n)\). Все слагаемые, кроме первого, образуют арифметическую прогрессию, поэтому, применяя формулу суммы арифметической прогрессии, получим снова ту же формулу: \(k(n)=(n+1)+\frac{(n+1)(n+n)}{2}\cdot n=\frac32n(n+1)+1\).

Эта задача задает последовательность, каждый член которой равен максимальному числу частей, на которые \(n\) параллельных и \(n\) непараллельных прямых делят плоскость. Вот десять ее первых членов: 4, 10, 19, 31, 46, 64, 85, 109, 136, 166.

Оказывается, что, если к этой последовательности добавить первым членом число 1, то получим последовательность так называемых центрированных треугольных чисел. Числа этой последовательности можно красиво интерпретировать графически (рис. 3): число точек в каждой фигуре равно соответствующему члену последовательности.

Рис. 3.

На рис. 4 показано, как устроены эти точечные фигуры. Цветом выделены треугольники, на периметре которых расположены 3, 6, 9, 12, ... точек, то есть арифметическая последовательность с разностью 3. И это не случайно, ведь \(k(n+1)-k(n)=3(n+1)\), то есть на периметре каждого следующего треугольника на 3 точки больше.

Рис. 4.

Если к последовательности чисел, кратных 3, впереди поставить число 1, то получим последовательность 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, ... , частичные суммы которой полностью совпадают с последовательностью \(\{k(n)\}\) из нашей задачи:

Это наблюдение позволяет придумывать новые не менее красивые графические интерпретации для членов последовательности \(\{k(n)\}\), а значит — и для числа частей плоскости, получающихся при делении плоскости \(2n\) прямыми. Например, на рис. 5 в каждой фигуре столько треугольников, сколько частей получается при делении плоскости для \(n=1,\ 2,\ldots,\ 5\), соответственно.

Рис. 5.

А что, если мы попробуем вычислить частичные суммы для нашей последовательности \(\{k(n)\}\)? Здесь нас ждет сюрприз! Итак:

Оказывается, начиная с третьего члена каждая частичная сумма равна магической константе магического квадрата \(n\times n\), где \(n\ge3\) (магического квадрата \(2\times2\) не существует). Это заметил Амарнат Мурти (Amarnath Murthy), математик из Индии.

Как это доказать? Во-первых, константа магического квадрата \(n\times n\) равна \(\frac{1+2+\ldots+n^2}{n}=\frac12n(n^2+1). Во-вторых, найдем сумму \(n\) первых членов последовательности \(\{k(n)\}\). Поскольку мы добавили единицу первым членом, то в формуле \(k(n)=\frac32n(n+1)+1\) произойдет смещение (то есть \(n\) заменится на \(n-1\)) и формула расширенной последовательности \(\{K(n)\}\) после упрощения выглядит так: \(K(n)=\frac32n^2-\frac32n+1\).

Выпишем первые \(n\) членов последовательности \(K(n)\):

Сложим почленно эти равенства и сгруппируем, выделив сумму первых \(n\) натуральных чисел и сумму их квадратов:

Используя известные формулы для этих сумм, получим:

После упрощения это выражение превращается в \(S=\frac12n(n^2+1)\), что и требовалось. Удивительная связь между двумя последовательностями, одна из которых родом из геометрии, вторая — из теории чисел.

Можно алгоритмизировать построение \(2n\) прямых, удовлетворяющих условию задачи. Я придумал такую конструкцию, основанную на том факте, что через каждую точку плоскости, лежащую вне окружности, проходят ровно две касательные к этой окружности. Для этого выполним следующие шаги:
    1) построим \(n\) параллельных прямых;
    2) отметим на каждой из этих прямых по точке так, чтобы они были коллинеарными (на рис. 6 это точки \(A\), \(B\), \(C\) и \(D\));
    3) построим окружность с центром \(O\), не пересекающую параллельные прямые;
    4) через каждую их отмеченных точек проведем касательную к окружности.

Полученная таким образом конструкция из \(2n\) прямых полностью удовлетворяет условию задачи и делит плоскость на \(k(n)=\frac32n(n+1)+1\) частей. В самом деле, среди наклонных прямых нет параллельных, и нет точек «тройного» пересечения, так как все наклонные являются касательными к окружности, потому что из любой точки можно провести только две касательные к окружности.

Рис. 6.

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

Обосновать это легко. Применим индукцию по общему числу прямых. Для одной прямой утверждение очевидно. Предположим теперь, что плоскость, разбитую на части \(n\) прямыми, можно раскрасить «шахматным» порядком (рис. 7, слева). Покажем, что плоскость, разбитую \(n+1\) прямой тоже можно раскрасить в «шахматном» порядке.

Рис. 7.

Проведем \((n+1)\)-ю прямую (красного цвета на рис. 7). Она разбивает плоскость на две полуплоскости. Раскраску верхней полуплоскости оставим без изменения, а части нижней полуплоскости перекрасим в противоположный цвет (рис. 7, справа). Получили раскраску плоскости в «шахматном» порядке, что и завершает доказательство по индукции.