Гармонические числа и … игральные карты.

В статье [1] речь шла о так называемых “гармонических числах” (напомним, что гармоническим числом называют сумму при целом n ≥ 1).

Отмечалось, что такая сумма так часто встречается в анализе алгоритмов, что специалистам понадобилось для нее специальное обозначение — Нn. Буква Н в этом обозначении происходит от слова “harmonic”, так что Н_n — это гармоническое число. Оно названо так потому, что k-я гармоника, извлекаемая из скрипичной струны, — это основной тон, производимый струной, длина которой равна 1/k от длины основной струны [2].

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

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

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

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

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

Надо также вспомнить уроки физики. Из них читателю, очевидно, известно, что центр тяжести k предметов, которые имеют веса w₁, w₂, …, w_k и центры тяжести которых находятся соответственно в точках p₁, p₂, …, p_k (см. рис. 2), расположен в точке p = (w₁p₁ + w₂p₂ + … + w_kp_k)/(w₁ + w₂ + … + w_k). Это означает, что для двух карт можем записать:

Рис. 2

Заметим, что d₁ = 0. В общем случае нужно положить d_{k + 1} равным центру тяжести k первых карт:

при 1≤k≤n.

А эту рекуррентную зависимость1 можно переписать в двух эквивалентных формах:

kd_{k + 1} = k + d₁ + d₂ + … + d_{k – 1} + d_k, k≥0;

(k – 1)d_k = k – 1 + d₁ + d₂ + … + d_{k – 1}, k≥l.

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

kd_{k + 1} – (k – 1)d_k = 1 + d_k, k≥l;

следовательно, d_{k + 1} = d_{k + 1}/k. Это означает, что вторая карта будет сдвинута на половину единицы длины относительно третьей карты, которая сдвинута на треть единицы длины относительно четвертой карты, и т.д. Отсюда по индукции вытекает общая формула

 

А если положить k = n, то получим d_{n + 1} = Н_n — т.е. полная величина выступа, когда n карт уложены так, как описано выше, равна гармоническому числу “степени” n.

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

при 1≤k≤n.

К тому же d₁ = 0. Отсюда по индукции следует, что d_k+1≤H_k.

Задания для самостоятельной работы

1. Определите, каким будет выступ в случае использования колоды из:

— 52 карт;

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

Программу для расчета значения гармонических чисел разработайте самостоятельно (или см. [1]).

2. Установите, при каком минимальном числе карт величина выступа будет превышать длину одной карты, которая равна двум единицам.

Ответы (можно на отдельные задания) присылайте в редакцию. Лучшие ответы мы поощрим.

Литература

1. Гармонические числа. / “В мир информатики” № 96 (“Информатика” № 20/2007).

2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.