На пути к решению

10

1. Повторение

• А разве ты не видишь?
• Нет.
• И я тоже!

Изагровора Иа·Иас Винни Пухом*)

С чего же начать? Прежде всего — с ответов в школьных вариантах задачи (n=2, 3, 4). Выпишем эти ответы в таблицу:

| n = 2 | (1, 1) | (1, 2) | (2, 3) | |
| :— | :— | :— | :— | :— |
| n = 3 | (1, 1, 1) | (1, 1, 2) | (1, 2, 3) | (2, 3, 7) |
| n = 4 | (1, 1, 1, 1) | (1, 1, 1, 2) | (1, 1, 2, 3) | (2, 3, 7, 43) |

Не правда ли, решение для различных n оцень похожи? Они образуют вертикальные серии и получаются добавлением единиц. Это наблюдение распространяется на всевозможные n с помощью следующей оцененной леммы:

Лемма 1. Пусть набор чисел (x₁, x₂, …, xₙ) является решением задачи для n=k. Тогда набор чисел (x₁, x₂, …, xₙ, 1) — решение задачи для n=k+1. И набором: если среди k+1 чисел, являющихся решением задачи для n=k+1, имеется единица, мо, убрав ее из набора, получим решение задачи для n=k.

А какрождаются новые серии: (2, 3), (2, 3, 7), …?

Пусть (x₁, …, xₙ) — решение задачи для n=k. По условию задачи, если (x₁, …, xₙ, xₙ+1) — решение задачи для n=k+1, то x₁ … xₙ+1 + 1 = Cxₙ+1, где C — неокоторое натуральное число. Попробуем положить C равным единице (так получаются числа 3=2+1, 7=2·3+1, 43=2·3·7+1). Докажем такую лемму:

Лемма 2. Если набор чисел (x₁, …, xₙ) — решение задачи для n=k, то набор (x₁, …, xₙ, xₙ+1) — решение задачи для n=k+1.

*) Все эпиграфы взяты из сказки Милна «Винни Пух и Все, Все, Все».

При помощи лемм 1 и 2 из каждой решения задачи для n=k могут быть получены два решения задачи для n=k+1. На рисунке 1 показано, как из решения задачи для n=2 при помощи леммы 1 (красные стрелки) и при помощи леммы 2 (синные стрелки) таким способом получаются решения задачи сначала для n=3, а затем — для n=4.

Ниоткуда не следует, что таким путем мы получим все решения. Впрочем, легко доказать, что набора, указанным на рисунке 1, исчерпываются все решения нашей задачи для n=2, 3, 4. К сожалению, из решения для n=4 таким способом получаются не все решения для n=5; кроме решения (2, 3, 7, 43, 1807), получающегося по решетту леммы 2, есть еще такое: (2, 3, 7, 47, 395).

2. Сведения к уравнению

Далее неиможечко,чайная ложечка,— это уже хорошо.

Винни Пух

Лемма 1 позволяет здесь и далее не рассматривать решения, содержащих 1,— с ними все ясно. Тогда, если набор (x₁, …, xₙ) — решение задачи для n=k, то все числа xᵢ различны (подумайте, почему).

11

Рис. 1.

Аналізируя ответы задачи при $n = 2, 3$ и 4, мы можем создать гипотезы лишь о строении этих ответов, а отнюдь не о том, как решать задачу. Посмотрим теперь, как эти ответы получаются для $n = 3$.

Пусть $(x, y, z)$ — некоторое решение задачи с треем числами. Тогда должны выполнять равенства

$$\begin{cases} xy + 1 = k_1z, \\ xz + 1 = k_2y, \\ yz + 1 = k_3x, \end{cases}$$

где $k_1, k_2, k_3$ — какие-то натуральные числа.

Перемножив эти соотношения, получим

$$xyz (xyz + x + y + z) + xy + xz + yz + 1 = k_1k_2k_3xyz.$$

Отсюда вытекает, что $xy + xz + yz + 1$ делится на $xyz$, то есть

$$xy + xz + yz + 1 = Axyz,$$

где $A$ — натуральное число. Разделив обе части этого равенства на $xyz$, получим

$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = A. \quad (1)$$

Итак, любое решение задачи для $n = 3$ удовлетворяет уравнению (1). Осовобидшись от значенателя, легко увидеть, что и обратно: если $x, y, z$ — натуральные числа, удовлетворяющие — при некотором натуральном $A$ — уравнению (1), то $(x, y, z)$ — решение задачи для $n = 3$.

Левая часть (1) принимает наиболее значение при наименьших значениях $x, y, z$; если $2 \leq x < y < z$, то

$$A \leq \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{27}{24} < 2.$$

Следовательно, $A = 1$ и $x, y, z$ удовлетворяют уравнению

$$\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1.$$

Ну что же, первый шаг очень естественный. Воспользовавшись определением делимости, мы от несколько неопределенных слов — одно число делится на конкретным и знакомным нам объektам. Правда, появились новые неизвестные $k_1, k_2, k_3$, которые раньше не были, но это — общная расплата за «некоторую определению». И второй шаг вполне понятен — желание избавиться от «лишних» неизвестных (за счет перехода от системы к одному уравнению).

Проделав аналогичную операцию для произвольного $n$, мы снова получим уравнение вида

$$\frac{1}{x_1} + \frac{1}{x_2} + \dots + \frac{1}{x_n} + \frac{1}{x_1 \dots x_n} = A, \quad (2)$$

где $A$ — натуральное число. Снова легко проверяется обратное утверждение:

если $x_1, x_2, \dots, x_n$ — натуральные числа, удовлетворяющие — при некотором натуральном $A$ — уравнению (2), то набор $(x_1, x_2, \dots, x_n)$ является решением нашей задачи.

Итак, исходная задача эквивалентна задаче нахождения решения уравнения (2) в наименьших числах при всевозможных натуральных $A$. Продвижение, конечно, необольное, но «далясе немножечко … это уже хорошо!».

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

12

(2) $A = 1$. Поскольку можно считать, что $2 \leqslant x_1 < x_2 < \dots < x_n$, для $A$ получаем оценку:

$$A = \frac{1}{x_1} + \dots + \frac{1}{x_n} + \frac{1}{x_1 \dots x_n} \leqslant \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} + \frac{1}{n!}.$$

Однако уже для $n = 14$ сумма, стоящая в правой части, больше 2. Но, может быть, из этой оценки все таки можно вывести, что величина $A$ ограничена и потому может принимать лишь конечное число значений? Так ведь нет: сумма $\frac{1}{2} + \dots + \frac{1}{n}$ неограниченно возрастает с увеличением $n$.

Упражнение 1. Докажите это.

По-видимому, наш метод оценки слишком груб. Нельзя ли его уличшить? Ясно, например, что все числа, входящие в решение, попарно взамимо просты. Поэтому, в частности, если $x_1 = 2$, то $x_3 > 4$.

Покажем, что сумму $\frac{1}{x_1} + \dots + \frac{1}{x_n} + \frac{1}{x_1 \dots x_n}$ можно оценить сверху числом $\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \dots + \frac{1}{p} + \frac{1}{2 \cdot 3 \cdot 5 \cdot \dots p}$, где $p$—просто число.

Действительно, обозначим через $p_i$ какой-нибудь простой делитель числа $x_i$. Заметим, что $p_i \leqslant x_i$. Поскольку числа $x_i$ попарно взамимо просты, все $p_i$ различны. Будем считать их упорядоченными по величины. Тогда $2 \leqslant p_1, 3 \leqslant p_2, 5 \leqslant p_3$ и т. д. Заменяя $x_i$ на $p_i$, получаем требуемую оценку.

Может быть, сумма величины, обратных простым числам, не превыходит некоторого простяного числа $M$? Это означает, что $A < M + 1$. Оказывается, и это неверно: с увеличением количества сумма $\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{p}$ возрастает неограниченно *). Тем не менее получаем оценка позволяет утверждать, что $A = 1$ для всех $n \leqslant 58$. Утешительного мало, но по крайней мере ясно, почему, анализируя ответы, мы ненатолкнулись на решение с константой $A = 2$: вряд ли кому-нибудь придет в голову рассматривать задачу сразу для шестидесятей чисел.

3. Добавление одного — ничего нового

Безвозмездно, то есть даром.

Кто может заранее знать, какой путь приведет к успеху? Терпение (но не упрямство) — вот принципи исследования. Вернемся еще раз к началу нашего путешествия. Телерь у нас в руках анализ ответов и методов решения задачи для частных случаев. Приставлено внимание заслуживаюл lemмы 1 и 2— они содержат хотя какой-то алгоритм нахождения некоторых решений. Какой подход они предлагают? В обеих леммах говорится о том, как из решения задачи для $n = k$ получить решение задачи для $n = k + 1$. Нам такой подход вполне привычен (вспомните метод математической индукции). Попробуем, считая, что задача решения для $n = k$, решить ее для $n = k + 1$.

Итак, путь $(x_1, \dots, x_k)$ — решение задачи для $n = k$. Обозначим произведение $x_1 \dots x_k$ через $f_k$. Тогда $\frac{1}{x_1} + \frac{1}{x_2} + \dots + \frac{1}{x_k} + \frac{1}{f_k} = A$.

Если число $x_{k+1}$ дополняется набор $x_1, \dots, x_k$ до решения задачи для $n = k + 1$ и $x_{k+1} \neq 1$, то имеет место соответствие:

$$\frac{1}{x_1} + \dots + \frac{1}{x_k} + \frac{1}{x_{k+1}} + \frac{1}{f_k x_{k+1}} = A$$

с тем же самым $A$ (продумайте это).

Приравнивая левые части этих двух равенств и отбрасывая одинаковые слагемы, получаем

$$\frac{1}{x_{k+1}} + \frac{1}{f_k x_{k+1}} = \frac{1}{f_k};$$

следоватьно, $x_{k+1} = f_k + 1$. Именно так получается решение и по

13

лемме 2! Значит, в равенстве $x_1 \dots x_k + 1 = C \cdot x_{k+1}$CONSTANTA $C$ равна 1 не случайно: дело тут не в простоте, а в уравнения (2). Кстати, лемма 2 $\delta$-ром следует из этого уравнения.

Таким образом, если решение задачи для $n = k + 1$ получается добавленем одного числа к решению задачи для $n = k$, то оно образуется либо по лемме 1, либо по лемме 2.

4. А если добавить два?

Интересно, что это так бумкнуло? Не может же я одиннадать столько шума! И куда, интересно знать, девалься мои воздушный шарик?

Пятачок

Итак, произходение леммы 2, по крайней мере, прояснились. Правда, новых решений мы не получили и попрежнему неопонятно, откуда берется решения, не образующесся применением лемм 1 и 2 (например, решение (2, 3, 7, 47, 395) для задачи с $n = 5$). Опять тупик? Подумаем еще раз, прежде чем сочти с выбранного пути. Исчерпали ли мы все возможности нашего подхода? Кто мешает нам добавить, ну хотя бы, два числа? Попробуем.

Предположим сначала, что $(x_1, \dots, x_k)$—решение задачи для $n = k$. Тогда

$$\frac{1}{x_1} + \dots + \frac{1}{x_k} + \frac{1}{f_k} = A.$$ (3)

Пусть $(x_1, \dots, x_k, x_{k+1}, x_{k+2})$—решение задачи для $n = k + 2$ и $x_{k+1} \neq 1, x_{k+2} \neq 1$. Оказывается, и в этом случае

$$\frac{1}{x_1} + \dots + \frac{1}{x_k} + \frac{1}{x_{k+1}} + \frac{1}{x_{k+2}} + \frac{1}{f_k x_{k+1} x_{k+2}} = A$$ (4)

с тем же $A$.

Следовательно,

$$\frac{1}{x_{k+1}} + \frac{1}{x_{k+2}} + \frac{1}{f_k x_{k+1} x_{k+2}} = \frac{1}{f_k},$$ (5)

откуда

$$x_{k+2} = f_k + \frac{f_k^2 + 1}{x_{k+1} - f_k}.$$ (6)

Поскольку $x_{k+2}$ должно быть целым, число $d = x_{k+1} - f_k$ является делителем числа $f_k^2 + 1$. Итак,

$$\begin{cases} x_{k+1} = f_k + d, \\ x_{k+2} = f_k + \frac{f_k^2 + 1}{d}. \end{cases}$$ (7)

Обозначим теперь через $d$ произвольный делитель числа $f_k^2 + 1$ и определим числа $x_{k+1}, x_{k+2}$ равенствами (7). Тогда для чисел $f_k, x_{k+1}, x_{k+2}$ выполняется (6), а значит, и (5). Из (3) и (5) следует (4). Значит, расширенный набор $(x_1, \dots, x_k, x_{k+1}, x_{k+2})$ является решением нашей задачи для $n = k + 2$. Итак, нами доказана.

Лемма 3. Пусть $(x_1, \dots, x_k)$—решение задачи для $n = k, f_k = x_1 \dots x_k$ и $d$—делитель числа $f_k^2 + 1$. Тогда набор $(x_1, \dots, x_k, f_k + d, f_k + \frac{f_k^2 + 1}{d})$ является решением задачи для $n = k + 2$. И наоборот: если решение задачи для $n = k$ добавленем двух чисел $n = k$ добавленем двух чисел, отличных от 1, то добавленные числа удовлетворяют равенствам (7).

Таким образом, если решение задачи для $n = k + 2$ получается добавленем двух чисел к решению задачи для $n = k$, то оно образуется либо по лемме 2, либо по лемме 3.

Два делителя $y f_k^2 + 1$ всегда: это 1 и $f_k^2 + 1$. Однако легко видеть, что для таких делителей лемма 3 не дает ничего нового по сравнению с лемкой 2. Но затем, если $f_k^2 + 1$ не является простым числом, то лемма 3 дает начало новой серии решений $(x_{k+3}$ можно строить снова по лемме 2 и т. д.). Например, для решения (2, 3, 7) имеем $f_k^2 + 1 = 1765 = 5 \cdot 353$, и мы получаем из него по лемме 3 решение (2, 3, 7, 47, 395), которое мы упоминали в п. 1. Аналогично, из решения (2, 3, 7, 43) по лемме 3 получается решения (2, 3, 7, 43, 1823, 193 667) (здесь $f_k^2 + 1 = 3261637 = 17 \cdot 191861$).

Рассмотрим последовательность решений, получающихся из решения

14

(2, 3) по лемме 2. Изовем ее базисной. Каждый раз, когда число $f_k^2 + 1$ оказывается в ней составным, от нее по лемме 3 отшпаляется по крайней мере одна ветка (рис. 2).

А много ли составных чисел среди чисел $f_k^2 + 1$ для базисной последовательности?

У пряженение 2. Докажите, что в базисной последовательности все числа $f_{2k+1}^2 + 1$ делятся на 5.

Из упражнения 2 следует, что по крайней мере при каждом нечетном $n$ от базисной последовательности по лемме 3 будет отшпалться решение, порождающее по лемме 2 новую последовательность решения. Легко проверить, что решения, принадлежшие разным последовательностям, не совпают.

Итак, всего лишь одна базисная последовательность для каждой $n > 2$ порождает по крайней мере $\left[\frac{n-1}{2}\right]$ решения, не содержащих 1. А гипотеза, что решения без единниц не так уж «много» (точнее, что их число ограничено константой, не зависит от $n$), «бумкнула». Она была бы справедлива, если бы, начиная с некоторого $n$, все решения действительно получались только применением леммы 2.

5. Другой подход

А все почему? По какой причине?
И какой из этого следует вывод?

Иа-Иа

Конечно, пусть, который был выбран, далеко не единственный. В письме читателя А. Н. Броцкого из Кнева предлагается другой подход: вместо того, чтобы из решения задачи для $n = k$ получать решение задачи для $n = k + 1$ или $n = k + 2$, попробуем из решения задачи для некоторого $n$ получить другие решения задачи для того же самого $n$. Броцкий предложил следующее теорему:

Пусть $(x_1, \dots, x_{n-2}, x_{n-1}, x_n)$ — решение, получающей по лемме 2 из решения $(x_1, \dots, x_{n-2}, x_{n-1})$ и $\frac{f_{n-2}x_n + 1}{x_{n-1}} = d_1d_2$.

Если система уравнений

$$\begin{cases} f_{n-2}x + 1 = d_1y, \\ f_{n-2}y + 1 = d_2x \end{cases}$$

имеем решение в натуральных числах, то набор $(x_1, \dots, x_{n-2}, x, y)$ может являться решение задачи.

У пряженение 3. Докажите теорему Броцкого.

Своим методом А. Н. Броцкий из решения (2, 3, 7, 47, 395, 779 731) получил решение (2, 3, 7, 47, 415, 8111), не образушееся применением леммы 3.

У пряженение 4. Проверьте, что для решения из базисной последовательности система (8) всегда имеет решение в натуральных числах,

У пряженение 5. Проверьте, дает ли метод А. Н. Броцкого, примененный к базисной последовательности, решения, не получающейся при помощи леммы 2 и 3.

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