Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 1.2 ЗАДАЧА О РАЗРЕЗАНИИ ПИЦЦЫВторая выбранная нами задача имеет более ощутимый геометрический привкус: сколько кусков пиццы можно получить, делая Снова начнем с рассмотрения крайних случаев, памятуя, что начинать надо с самого крайнего. Плоскость без прямых — это одна область, с одной прямой — две области, а с двумя прямыми — четыре области:
(Каждая прямая неограниченно продолжается в обоих направлениях.) Вы наверняка думаете, что
Таким образом, А по некотором размышлении на ум приходит и подходящее обобщение. Новая
Более того, легко показать по индукции, что в этой формуле можно достичь равенства. Мы просто проводим
Уже известные значения Теперь нам нужно решение в замкнутой форме. Мы могли бы снова сыграть в «угадайку», но Зачастую можно разобраться в рекуррентности, «развертывая» или «разматывая» ее всю до конца следующим образом:
Другими словами, Поскольку величина
Эти числа называются также треугольными числами, поскольку Для вычисления
Мы просто складываем
Ну вот мы и получили требуемое решение:
Как специалисты, мы могли бы удовлетвориться этим выводом и рассматривать его в качестве доказательства, даже если слегка отмахивались от выполнения „развертывания" и „обращения! Но изучающие математику должны уметь действовать в соответствии с более строгими стандартами — вот хороший повод для строгого доказательства по индукции. Решительный индуктивный шаг —
и теперь можно не сомневаться в справедливости замкнутой формы (1.6). Между прочим, мы разглагольствуем о „замкнутых формах" без точного определения, что мы под этим понимаем. Обычно это и так достаточно очевидно. Рекуррентности типа (1.1) и (1.4) представлены в незамкнутой форме, ибо они выражают некоторую величину через самое себя, но их решения типа (1.2) и Общее число простых замкнутых форм ограничено, так что существуют рекуррентности, которые не представимы в простых замкнутых формах. Но если такие рекуррентности возникают постоянно, демонстрируя свою важность, — мы пополняем свой репертуар новыми операциями; это может существенно расширить диапазон задач, решаемых в „простой" замкнутой форме. К примеру, произведение первых А теперь небольшая вариация на тему прямых на плоскости: предположим, что вместо прямых линий мы используем ломаные линии, каждая из которых представлена одним „зигом" Каково максимальное число
Из этих частных случаев, немного подумав, мы заключаем, что ломаная линия подобна двум прямым с тем лишь отличием, что области сливаются, если „две“ прямые не продолжать после их пересечения:
Области 2, 3 и 4, которые были бы раздельны при наличии двух прямых, превращаются в единую область в случае одной ломаной линии, т. е. мы теряем две области. Однако если привести все в надлежащий порядок — точка излома должна лежать «по ту сторону» пересечений с другими линиями, — то окажется, что это все, что мы теряем; т. е. мы теряем только две области на одну линию. Таким образом,
Сравнивая решения в замкнутой форме (1.6) и (1.7), мы приходим к выводу, что при большом
так что ломаные линии дают примерно в четыре раза больше областей, чем прямые. (В последующих главах мы обсудим, как анализировать приближенное поведение целочисленных функций при большом
|
1 |
Оглавление
|