Разбиение единицы

48

Разбение единцы

О. Т. ИЖБОЛДИН, Л. Д. КУРЛЯНДЧИК

Существует много задач, связанных с суммами чисел, обратных натуральным. Неоднократно обращался к этой теме и наш журнал: в прошлом году в «Задачике «Кванта» были помещены две такие задачи — М989 и М1010 (в «Кванте» № 6 и № 10). Решение первой из них было опубликовано (см. «Кванте» № 10 за 1986 г.); решению второй и ещё несколько близких задачам посвязывана эта заметка. Напомним формулировку задачи.

Послеовательность $r_1, r_2, r_3, \dots$ определяется условиями

$$r_1 = 2, r_{n+1} = r_1 r_2 \dots r_n + 1,$$

так что $r_2 = 3, r_3 = 7, r_4 = 43, \dots$

a) Докажите, что при любом $n$

$$\frac{1}{r_1} + \frac{1}{r_2} + \dots + \frac{1}{r_n} < 1.$$

6)* Пусть $n$ натуральных чисел таковые, что сумма их обратных величины 1. Докажите, что эта сумма не больше

$$\frac{1}{r_1} + \frac{1}{r_2} + \dots + \frac{1}{r_n}.$$

По существу здесь требуется найти лучшее приближение единцы сизу суммами дробей вида $1/n$ (кстати, такие числа носят название аликвотных, или египетских, дробей). Эта задача принадлежит американскому математике Келлогу. В 1915 году профессор Кармайк, который сообщил о ней, приведел ее в своей книге «Диофантов анализ». В 1922 году она была решена американским математиком Кертисом. Мы приведем другое, горячое более короткое решение. (Говоря об истории задачи, упомянем и том, что она была опубликована под номером 70 в сборнике «400 избранных задач», выпущенном издательством «Мир» в 1977 г., но фактически без решения.)

Послеовательность
2, 3, 7, 42, 1807, 3263443, …

Равенство, определяющее послеовательность $r_n$ в условиям задачи, можно переписать в виде

$$r_{n+1} = (r_n - 1) r_n + 1$$

*) В задаче был и третий пункт — lemma к решению задачи 6). Мы приведем его позже.

49

или
$$\frac{1}{r_{n+1}-1} = \frac{1}{(r_n-1)r_n} = \frac{1}{r_n-1} - \frac{1}{r_n}.$$
Следовательно,
$$\frac{1}{r_1} + \frac{1}{r_2} + \dots + \frac{1}{r_n} = \left( \frac{1}{r_1-1} - \frac{1}{r_2-1} \right) + \left( \frac{1}{r_2-1} - \frac{1}{r_3-1} \right) + \dots + \left( \frac{1}{r_n-1} - \frac{1}{r_{n+1}-1} \right) = 1 - \frac{1}{r_{n+1}-1} < 1$$
(поскольку $r_1-1=1$). Тем самым доказано утверждение a) нашей задачи. Попутно мы доказали, что $1/r_{n+1}$ — наиболее низкое значение $r_n$ натуральным, которое можно добавить к сумме $1/r_1+...+1/r_n$ так, чтобы она осталась меньше 1 (добавив $1/(r_{n+1}-1)$, мы получили бы ужеровно 1). Таким образом, при построении последовательности $1/r_n$ нужно каждой раз «откусивать наиболее возможный возможный кусок».

Отметим, кстати, что числа $r_n$ появляются в другой задаче, внешнее оценка далекой от нашей: «описать все наборы из $n$ натуральных чисел, таких, что произведение любых $n-1$ из них в сумме с единицей делится на остальные». Проверьте самостояльно, что числа $r_1, ..., r_n$ удовлетворяют этому условию. Полное решение этой задачи неизвестно; подробности обсуждались в статье A. Гейна «На пути к решению» (Квант, 1978, № 7, с. 9).

Не вернемся к задаче M1010 и обязываем,

Почему последовательность $1/r_n$ наиболее точным?

Пусть сумма $1/a_1+...+1/a_n$, где $a_1, ..., a_n$ — натуральные числа, $a_1 \leqslant a_2 \leqslant ... \leqslant a_n$, — наиболее точным приближение к единицей; существование такого приближения для каждой натурального $n>1$ было доказано в решении задачи M989, в) (см. «Квант» № 10, 1986 г., с. 36). Положим $\alpha_k=1/a_k$ при $k=1, 2, ..., n-1$, $\alpha_n=1-\alpha_1-\alpha_2-...-\alpha_{n-1}$. Мы показем, что набор чисел $a_1, ..., a_n$ удовлетворяет следующим условиям:
$$\alpha_1 \geqslant \alpha_2 \geqslant ... \geqslant \alpha_n \geqslant 0,$$
$$\alpha_1+\alpha_2+...+\alpha_n=1,$$
$$\alpha_1...\alpha_k \leqslant \alpha_{k+1}+...+\alpha_n$$
при $k=1, 2, ..., n-1$. (3)

Это условия леммы, составляющей пункт в) задачи M1010. Согласно этой лемме, которая доказана ниже, число $a_n$, т. е. погрешность нашего приближения единицы, не меньше $1/(r_n-1)$, причем $a_n=1/(r_n-1)$ только для набора $a_k=1/r_k$, $k=1, ..., n-1$. Следовательно, $a_k=r_k$, что эквивалентно утверждению пункта 6).

Итак, проверим условия (1)—(3) для $a_1, ..., a_n$. Условие (2) оченьindo; ясно также, что $a_1 \geqslant a_2 \geqslant ... \geqslant a_{n-1}$. Покажем, что $a_{n-1} \geqslant a_n$. Поскольку рассматриваем приближение единицы сначала наилучше,

$$\frac{1}{a_1} + ... + \frac{1}{a_{n-1}} + \frac{1}{a_{n-1}-1} \geqslant 1.$$
Следовательно,
$$a_{k+1} + ... + a_n = 1-\alpha_1-...-\alpha_k =$$
$$= 1-\frac{1}{a_1}-...-\frac{1}{a_k} = \frac{N}{a_1...a_k} =$$
$$= N \cdot \alpha_1 \cdot ... \cdot \alpha_k,$$
где $N$ — некоторое натуральное число, и поэтому последнее выражение не меньше $a_1...a_k$.

Доказательство леммы

Мы должны доказать, что тот из набора ($\alpha_1, ..., a_n$), удовлетворяющих условиям (1)—(3), для которого $a_n$ минимально, совпадает с набором $(1/r_1, ..., 1/r_{n-1}, 1/(r_n-1))$.

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

Итак, пусть $\beta=(\beta_1, ..., \beta_n)$ — тот из набора, удовлетворяющих условиям (1)—(3), для которого произведение $\beta_1...\beta_n$ минимально (вопрос о том, почему такой набор вообществует, мы обсудим позже). Заметим сразу, что $\beta_n>0$, и следовательно, в силу (2) $\beta_1<1$. (Если $\beta_n=0$, то из неравенства (3) последовательно получим: при $k=n-1$ — что $\beta_n=0$, при $k=n-2$ — что $\beta_{n-2}=0$ и т. д.; но все числа $\beta_i$ не могут равнять 0, так как они в сумме дают 1.).

Доказем теперь, что для набора $\beta$ все неравенства (3) обращаются в равенства.

При $n=2$ из (1)—(3) мы сразу получаем, что $\beta_1 \geqslant \beta_2 \geqslant 0$, $\beta_1+\beta_2=1$ и $\beta_1 \leqslant \beta_2$, т. е. $\beta_1=\beta_2=1/2$. Пусть $n>2$.

51

Поясним эту теорему на примере нашей функции $f$ и множества $A$. Во-первых, ясно, что функция $f$ не перерывна, т. е. ее значения для двух наборов, соответствующие элементы которых достаточно мало отличаться друг от друга, будут сколько угодно близки. Во-вторых, множество $A$ ограничено, т. е. элементы $\alpha_i$ любого входящего в него набора по абсолотной величины не превыходит некоторого фиксированного числа; у нас $|\alpha_i| \leq 1$. Наконец, множество $A$ замыкнут; это означает, что если произвольная последовательность наборов из множества $A$ состоит из $\alpha = (\alpha_1, \dots, \alpha_n)$ (т. е. первые элементы этих наборов образуют последовательность, схожися к $\alpha_1$, вторые — к $\alpha_2$ и т. д.), то и набор $\alpha$ принадлежит множество $A$. Замкнутость множества $A$ обеспечивает тем, что все неравенства в условиях (1)—(3) несторические.

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

В знаменатель — арифметическая прогрессия

Обсуждим еще две задачи о представлениях целых чисел суммии чисел, обратных натуральными числам $a_1, a_2, \dots, a_n$ образуют арифметический прогрессию с неуполевой разностью?

Начнем с наиболее простого случая, когда разность прогрессии равна 1. Итак, может ли число быть представлено в виде суммы $1/a_1 + 1/a_2 + \dots + 1/a_n$, где натуральные числа $a_1, a_2, \dots, a_n$ образуют арифметический прогрессию с неуполевой разностью?

Начнем с наиболее простого случая, когда разность прогрессии равна 1. Итак, может ли число быть представлено в виде суммы $1/a_1 + 1/a_2 + \dots + 1/a_n$, где натуральные числа $a_1, a_2, \dots, a_n$ образуют арифметический прогрессию с неуполевой разностью?

Задача 2. Из любой ли арифметической прогрессии натуральных чисел можно выбрать несколько различных чисел $a_1, a_2, \dots, a_n$ таких, что $1/a_1 + \dots + 1/a_n = 1$?

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

52

Проще всего придумать нужное разложение единиц для прогрессии четырех чисел 2, 4, 6…; например:

$$1 = \frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \frac{1}{12}.$$

Неколько сложнее обстоит дело с нечетными числами: одно из возможных разложений —

$$1 = \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{9} + \frac{1}{11} + \frac{1}{15} + \frac{1}{21} + \frac{1}{35} + \frac{1}{231}.$$

И еще одна конструкция более общого характера — для произвольной прогрессии с разностью 1: $a, a+1, a+2, \dots$. Пусть $k$ — такое натуральное число, что $2^k > a$. Если записать числители дробей в правой части равенства

$$1 = \frac{1}{2^k} + \frac{3}{3 \cdot 2^k} + \dots + \frac{2^{k+1}-1}{(2^{k+1}-1)2^k}.$$

в виде сумм различных степеней двоек: $2^{l+1}-1=1+2+\dots+2^l$, мы получим представление единиц сумм

Туннельный микрокопп

(Начало см. на c. 19)

Пример такой карты поверхности кристалла кремния, полученной американским ученым, приводится на рисунке справа. Отчетливо видны положения отдельных atomов кремния в периодической кристалической структуре.

Сканирующий туннельный микрокопп построен и в нашей стране. Он отличается огромной, в атомном масштабе, область сканирования — 10×10 мкм и возможность работы в жидкой непроводящей среде. Второе важное поточему. Объчно при экспериментах на туннельном микрокоппе исследуемый образец, ради числовых поверхностей, помещается в высокий вакуум. Однако для достижения той же целей может оказаться выгодной и плотная среда. Так, жидкий углеводород, который используется в советском туннельном микрокоппе, предохраняет поверхность об–>

«Топографическая карта» участка поверхности кремния размером 175×115 A. Светлее места соответствует положения atomов кристалической решетки.

Сканирующий туннельный микрокопп в настоящее время представляется не только средством исследования поверхности, но и инструментом для воздействия на нее. Предполагается, что острем туннельного микрокоппа можно «рисовать» на поверхности микрокопм с размерами в сотни и даже десятиatomных. Не исключаено, что скоро мы станем свидетельми нового этапа микроминтиоризация электроники. И поможет в этом сканирующий туннельный микрокопп.

А. П. Володин