1.2 ЗАДАЧА О РАЗРЕЗАНИИ ПИЦЦЫ

Вторая выбранная нами задача имеет более ощутимый геометрический привкус: сколько кусков пиццы можно получить, делая прямолинейных разрезов ножом? Или более академично: каково максимальное число областей, на которые плоскость делится прямыми? Впервые эта задача была решена в 1826 г. швейцарским математиком Якобом Штейнером [356].

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

(Каждая прямая неограниченно продолжается в обоих направлениях.)

Вы наверняка думаете, что Добавление новой прямой попросту удваивает число областей. К сожалению, это неверно. Мы могли бы достигнуть удвоения, если бы новая прямая рассекала каждую старую область на две части; разумеется, она может рассекать старую область в лучшем случае на две части, поскольку каждая из старых областей выпукла. (Прямой линией можно рассечь выпуклую область самое большее на две новые части, которые также будут выпуклы.) Но когда добавляется третья прямая — жирная линия на нижнем рисунке — мы быстро обнаруживаем, что она может рассекать самое большее три старые области вне зависимости от того, как расположены первые две прямые:

Таким образом, — самое большее, что можно сделать.

А по некотором размышлении на ум приходит и подходящее обобщение. Новая прямая (при ) увеличивает число областей на к тогда и только тогда, когда рассекает к старых областей, а рассекает она к старых областей тогда и только тогда, когда пересекает прежние прямые в различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать старых прямых не более чем в различных точках, и мы должны иметь к . Нами установлена верхняя граница

Более того, легко показать по индукции, что в этой формуле можно достичь равенства. Мы просто проводим прямую так, чтобы она не была параллельна никакой другой (следовательно, она пересекает каждую из них) и так, чтобы она не проходила ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах). Поэтому искомое рекуррентное соотношение имеет вид

Уже известные значения превосходно согласуются с этим соотношением, так что мы его берем.

Теперь нам нужно решение в замкнутой форме. Мы могли бы снова сыграть в «угадайку», но не напоминает ничего знакомого: поэтому попробуем применить другой подход.

Зачастую можно разобраться в рекуррентности, «развертывая» или «разматывая» ее всю до конца следующим образом:

Другими словами, на единицу больше суммы первых положительных целых чисел.

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

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

Для вычисления можно воспользоваться уловкой, до которой, как утверждается, Гаусс додумался в когда ему было девять лет от роду [96] (см. также Эйлер [378, часть 1, §415]):

Мы просто складываем с самой собой, записанной в обратном порядке, так что сумма в каждой из колонок справа равна После упрощения имеем

Ну вот мы и получили требуемое решение:

Как специалисты, мы могли бы удовлетвориться этим выводом и рассматривать его в качестве доказательства, даже если слегка отмахивались от выполнения „развертывания" и „обращения! Но изучающие математику должны уметь действовать в соответствии с более строгими стандартами — вот хороший повод

для строгого доказательства по индукции. Решительный индуктивный шаг —

и теперь можно не сомневаться в справедливости замкнутой формы (1.6).

Между прочим, мы разглагольствуем о „замкнутых формах" без точного определения, что мы под этим понимаем. Обычно это и так достаточно очевидно. Рекуррентности типа (1.1) и (1.4) представлены в незамкнутой форме, ибо они выражают некоторую величину через самое себя, но их решения типа (1.2) и замкнутой форме. Суммы вида записаны не в замкнутой форме, поскольку они грешат наличием но выражения вида представлены в замкнутой форме. Можно дать некое грубое определение типа следующего: выражение для величины представлено в замкнутой форме, если ее можно вычислить с помощью некоторого фиксированного числа «известных» стандартных операций, независимо от Например, выражения представлены в замкнутой форме, поскольку они включают в себя только сложение, умножение, деление и возведение в степень в явном виде.

Общее число простых замкнутых форм ограничено, так что существуют рекуррентности, которые не представимы в простых замкнутых формах. Но если такие рекуррентности возникают постоянно, демонстрируя свою важность, — мы пополняем свой репертуар новыми операциями; это может существенно расширить диапазон задач, решаемых в „простой" замкнутой форме. К примеру, произведение первых целых чисел, факториал, оказалось настолько важным, что теперь все мы рассматриваем его как основную операцию. Поэтому формула записана в замкнутой форме, хотя эквивалентное ей выражение — нет.

А теперь небольшая вариация на тему прямых на плоскости: предположим, что вместо прямых линий мы используем ломаные линии, каждая из которых представлена одним „зигом" Каково максимальное число областей, на которые плоскость делится такими ломанными линиями? Можно ожидать, что будет примерно вдвое или, быть может, втрое больше, чем Но давайте посмотрим:

Из этих частных случаев, немного подумав, мы заключаем, что ломаная линия подобна двум прямым с тем лишь отличием,

что области сливаются, если „две“ прямые не продолжать после их пересечения:

Области 2, 3 и 4, которые были бы раздельны при наличии двух прямых, превращаются в единую область в случае одной ломаной линии, т. е. мы теряем две области. Однако если привести все в надлежащий порядок — точка излома должна лежать «по ту сторону» пересечений с другими линиями, — то окажется, что это все, что мы теряем; т. е. мы теряем только две области на одну линию. Таким образом,

Сравнивая решения в замкнутой форме (1.6) и (1.7), мы приходим к выводу, что при большом

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