6.3 ГАРМОНИЧЕСКИЕ ЧИСЛА

Теперь пришло время вплотную заняться гармоническими числами, с которыми мы впервые встретились еще в гл. 2:

Эти числа так часто возникают в анализе алгоритмов, что специалистам понадобилось для них специальное обозначение. Мы же воспользуемся обозначением — буква происходит от слова „harmonic" при этом тон с длиной волны называется гармоникой тона, длина волны которого равна 1. Несколько первых значений выглядят так:

Упражнение 21 показывает, что при числа никогда не являются целыми.

Вот один карточный фокус, основанный на идее Р. Т. Шарпа [351], который демонстрирует, насколько „гармонично" возникают гармонические числа уже в простых ситуациях. Положив на стол карт и сдвигая их относительно друг друга, нам хотелось бы образовать как можно больший выступ над краем стола с учетом действия силы тяжести:

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

Для одной карты максимальная величина выступа получается тогда, когда ее центр тяжести находится ровно над краем стола. А поскольку центр тяжести находится в центре карты, то мы можем образовать выступ длиной в половину карты, т. е. длиной в 1 единицу.

Для двух карт нетрудно убедиться, что максимальная величина выступа получается тогда, когда центр тяжести верхней карты находится ровно над краем второй карты, а общий центр тяжести обеих карт — ровно над краем стола. А поскольку общий центр тяжести двух карт будет находиться посередине их совмещенных

частей, то мы в состоянии увеличить величину выступа еще на пол-единицы.

Подобные обстоятельства подсказывают общий метод, в соответствии с которым карты помещаются так, чтобы центр тяжести к верхних карт находился ровно над краем к 1-й карты (которая положена под эти к верхних карт). Стол же играет роль 1-й карты. Для того чтобы выразить это условие алгебраически, можно обозначить через расстояние от выступающего края самой верхней карты до соответствующего края сверху карты. Тогда и нам нужно положить равным центру тяжести к первых карт:

(Центр тяжести к предметов, которые имеют веса и центры тяжести которых находятся соответственно в точках находится в точке ) А эту рекуррентность можно переписать в двух эквивалентных формах:

Вычитание одного уравнения из другого показывает, что

следовательно, Вторая карта будет сдвинута на половину единицы длины относительно третьей карты, которая сдвинута на треть единицы длины относительно четвертой карты, и т. д. Отсюда по индукции вытекает общая формула

А если положить то получим — полную величину выступа, когда карт уложены так, как описано выше.

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

К тому же Отсюда по индукции следует, что Заметим, что для того чтобы верхняя карта полностью выступала за край стола, вовсе не нужно очень много карт. Нам нужно ровно столько карт, чтобы величина выступа немного превышала длину одной карты, которая равна 2 единицам. А поскольку

первым таким числом, которое превышает 2, является то достаточно всего лишь четырех карт.

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

Еще одна занятная задачка, называемая „задачей о червяке на резинке“, демонстрирует гармонические числа в ином облике. Червяк медленно, но верно двигается от одного конца полоски резины метровой длины к другому, проползая по одному сантиметру в минуту. По прошествии каждой минуты столь же уверенно держащий полоску некто К — единственная цель жизни которого состоит в расстройстве планов — растягивает ее еще на один метр. Таким образом, проползав одну минуту, находится в 1 сантиметре от начала и в 99 сантиметрах от конца резинки, после чего К растягивает полоску на один метр. Процесс растягивания не изменяет относительного местонахождения (находящегося в длины резинки от начала и в 99% от конца) так что теперь находится в 2 см от начала см от цели. Спустя еще минуту на счету 3 пройденных сантиметра и 197 впереди — но К растягивает резинку, и эти сантиметры превращаются в 4.5 и 295.5. И так далее... Достигает ли когда-нибудь червяк финиша? Чем дальше он двигается, тем больше удаляется от него цель. (Предполагаются безграничное терпение у К и беспредельная растяжимость резинки и бесконечная крохотность червяка.)

Выпишем несколько формул. Когда К растягивает резиновую полоску, та ее часть, которую прополз остается одной и той же. Таким образом, за первую минуту он проползает 1/100 ее часть, за вторую —1/200 ее часть, за третью —1/300 ее часть и т. д. Часть резинки, которую он прополз за минут, равна

Итак, червяк достигает цели, как только превысит 100.

Вскоре мы узнаем, как оценивать при большом а пока просто проверим наш анализ, выяснив, как будет вести себя в такой же ситуации гусеница. В отличие от червяка за минуту гусеница способна проползти 50 см, так что в соответствии с только что приведенным рассуждением за минут она проползет длины резинки. Если наше рассуждение правильно, то гусеница должна будет добраться до цели, прежде чем достигнет 4, поскольку . И это так: простой подсчет показывает, что по истечении трех минут гусенице останется преодолеть всего лишь 33 см — она финиширует через 3 минуты и 40 секунд ровно.

Гармонические числа появляются и в треугольнике Стирлинга. Попробуем выразить в замкнутой форме — число перестановок

объектов, которые содержат ровно два цикла. Рекуррентность (6.8) показывает, что

а достойным кандидатом для разрешения этой рекуррентности служит метод суммирующего множителя из гл. 2:

Развертывание этой рекуррентности показывает, что следовательно

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

По-видимому, самый простой способ показать, что это сгруппировать члены ряда в соответствии со степенями 2. Поместим один член в 1-ю группу, два члена — во 2-ю группу, четыре члена — в 3-ю группу, восемь членов — в 4-ю группу и т.

Поскольку оба члена 2-й группы находятся между и то сумма членов этой группы лежит между Поскольку все четыре члена 3-й группы лежат между и то их сумма также располагается между и 1. И вообще, каждый из членов группы располагается между следовательно, сумма членов каждой отдельной группы находится между и 1.

Подобная процедура группировки показывает, что если член принадлежит группе, то должно быть к

(доказывается индукцией по k). Таким образом, а в действительности

Итак, мы выяснили величину с точностью до множителя 2. Хотя гармонические числа и стремятся к бесконечности, они стремятся к ней всего лишь логарифмически — т. е. крайне медленно.

Приложив чуть больше усилий и добавив малую толику вычислений, можно получить более точные границы. Как мы выяснили в гл. 2, величина служит дискретным аналогом непрерывной функции . А поскольку натуральный логарифм определяется как площадь области под некоторой кривой, то напрашивается следующее геометрическое сравнение:

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

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

Итак, мы выяснили величину с ошибкой, не превосходящей 1.

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

Аналогично определяются гармонические числа порядка путем суммирования степеней натуральных чисел:

Если то при эти числа стремятся к некоторому пределу; в упр. 2.31 отмечалось, что этот предел обыкновенно называют дзета-функцией Римана:

Эйлер [367] обнаружил изящный способ использования обобщенных гармонических чисел для приближения ими обычных гармонических чисел Рассмотрим бесконечный ряд

который сходится при . Левая часть — это ; поэтому при суммировании обеих частей по 2 к левая сумма телескопируется и мы получаем

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

При правая часть стремится к предельному значению

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

Итак, эйлерово рассуждение позволяет установить предельное соотношение

таким образом, на приходится примерно 58% длины между обеими границами из — мы постепенно приблизились к его истинному значению.

Как будет видно в гл. 9, возможны дальнейшие уточнения. Например, там будет доказано, что

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

Помимо всего прочего, это означает, что стопка из миллиона карт может выступать над краем стола на длину более чем семи карт.

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

В действительности, в упр. 9.49 доказывается, что переломное значение есть либо либо Можно представить себе ликование червяка к большой досаде К, когда он, наконец, пересечет финишную черту, начав свой долгий путь около 287 децильонов (287 с 33 нулями. - Перев.) веков назад. (А резинка окажется растянутой в длину на более чем световых лет — ее атомы будут значительно удалены друг от друга.)