Метод бесконечного спуска

24

Метод бесконечного спуска

Какое irrationalное число само «старое»? Несомненно, $\sqrt{2}$. Мы не знаем точно, кто первый доказал irrationalность этого числа, однокто мы убежданы, что сделано было это примерно так.

Доказательство первого

Допустим, что число $\sqrt{2}$ irrationalно. Геометрический это означает, что диагональ квадрата длины $c$ созмерма с его стороны длины $a$, то есть найдет отрезок длины $d$ и целые числа $m$ и $n$ такие, что $c=dm$, $a=dn$. Отметим $m-1$ точек на диагонали $AC$ и $n-1$ точек на стороне $DC$, делящие эти отрезки на кусочки длины $d$. Отложим на $|AC|$ отрезок $AK: |AK|=|AD|;$ на $|DC|$ — отрезок $DE: |DE|=|KC|$. Точки $K$ и $E$ попадут в отмещенные точки

Рис. 1.

Доказательство второе

Иrrationalность $\sqrt{2}$ означает, что уравнения $x^2=2y^2$ нет решения в натуральных числах $x, y$. Допустим, что такие решения есть, и $x=m$, $y=n$ — одно из них.

Из уравнения следует, что $m$-четное число, $m=2m_1$. Подставляя $m=2m_1$ в уравнение, получаем $n^2=2m_1^2$, то есть $x=n$, $y=m_1$- тоже решение. Отметим при этом, что $n<m$, $m_1<n$. Тепер видно, что и $n$-четное число, $n=2n_1$, следовательно, $m_1^2=2n_1^2$. Таким образом

25

разом, $x = m_1, y = n_1$ — решение уравнения, при этом $m_1 < n, n_1 < m_1$. Мы можем построить так же и дальнейше, получая все меньше и меньше решение уравнения. Но здесь-то уже и есть противоречие. Ведь все числа $m, n, m_1, n_1, \dots$ — натуральные, $m > n > m_1 > n_1 > \dots$, а бесконечной убывающей последовательности натуральных чисел быть не может! Значит, наше предположение было ошибочно, и число $\sqrt{2}$ irrationalно.

Оба рассуждания по существу проходили по одному схеме: предположив, что у задачи есть решение, мы строили некоторый бесконечный процесс, в то время как по самому смыслу задачи этот процесс должен на чем-то кончаться. Подобный метод и называется методом бесконечного спуска $^*$.

Часто метод спуска применяется в более простой форме. Предположив, что мы уже добавились до естественного конца процесса, мы видим, что «остановиться» не может.

Доказательство третье

Пусть $x = m, y = n$ — решение уравнения $x^2 = 2y^2$ с наименьшим возможным $x$. Число $m$ должно быть четным, $m = 2m_1$, следовательно, $x = n, y = m_1$ — тоже решение нашего уравнения. Однако $m > n$, что противоречит выбору решение $m, n$ как «наименьшего».

Из этого варианта доказательства видно, что метод спуска средний метод математической индукции. Оба метода основаны на том факте, что любое неусмотное множество науральных чисел имеет минимальный элемент. Метод спуска наиболее удобен для доказательства «отрицанию» теорем.

Метод спуска в задачах

Задача 1. Доказать неразрешимость в науральных числах уравнения

$$8x^4 + 4y^4 + 2z^4 = t^4.$$

*) Метод бесконечного спуска изобрел, по-видимому, древнегреческий математик. Есть основания полагать, что Ферма пытается доказывать свою Великую теорему именно этим методом.

Решение. Допустим, что решение есть, и $x = m, y = n, z = p, t = r$ — решение с наименьшим возможным $x$. Из уравнения видно, что $r$ — четное число, $r = 2r_1$.

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

$$4m^4 + 2n^4 + p^4 = 8r_1^4.$$

Тепер ясно, что $p$ — четное, $p = 2p_1$, следовательно,

$$2m^4 + n^4 + 8p_1^4 = 4r_1^4.$$

Далее действует так же: $n = 2n_1$, $m^4 + 8n_1^4 + 4p_1^4 = 2r_1^4$.

Наконец, $m = 2m_1$, $8m_1^4 + 4n_1^4 + 2p_1^4 = r_1^4$.

Таким образом, $x = m_1, y = n_1, z = p_1, t = r_1$ — решение нашего уравнения. Но ведь $m_1 < m$! Мы получили противоречение с выбором решения $m, n, p, r$ как «наименьшего».

Рассмотрим задачу сложнее.

Задача 2. Доказать неразрешимость в науральных числах уравнения

$$x^2 + y^2 + z^2 + u^2 = 2xyzu.$$

Решение. Пусть $x, y, z, u$ — решение.

Так как $x^2 + y^2 + z^2 + u^2$ — четное число, то средние чисел $x, y, z, u$ — четное число нечетных, то есть либо четые, либо два, либо нуль. Если все числа нечетные, то $x^2 + y^2 + z^2 + u^2$ не делится на 4, а $2xyzu$ не делится. Если же только два нечетных числа, то $x^2 + y^2 + z^2 + u^2$ не делится на 4, а $2xyzu$ делится. Поэтому все числа, то есть $x = 2x_1, y = 2y_1, z = 2z_1, u = 2u_1$. Подставив эти значения в уравнение, получаем

$$x_1^2 + y_1^2 + z_1^2 + u_1^2 = 8x_1y_1z_1u_1.$$

Как и прежде, видим, что все четые числа нечетными быть не могут, иначе $x_1^2 + y_1^2 + z_1^2 + u_1^2$ не делится на 8. Так же не могут быть нечетнымировно числа, либо и тогда $x_1^2 + y_1^2 + z_1^2 + u_1^2$ не делится на 8. Итак, мы получаем, что все числа нечетные, то есть

$$x_1 = 2x_2, y_1 = 2y_2, z_1 = 2z_2, u_1 = 2u_2.$$

26

Позтому

$$x_2^2 + y_2^2 + z_2^2 + u_2^2 = 32x_2y_2z_2u_2.$$
Рассуждая как и раньше, получаем, что $x_2, y_2, z_2, u_2$ — четные числа и так далее. Легко понять, что при всяком натуральном s

$$x_s^2 + y_s^2 + z_s^2 + u_s^2 = 2^{2s+1}x_sy_sz_su_s,$$

причем

$$x_k = 2x_{k+1}; y_k = 2y_{k+1};$$

$$z_k = 2z_{k+1}; u_k = 2u_{k+1}; k \geqslant 1.$$

To есть при любом натуральном s числа $\frac{x}{2^s}, \frac{y}{2^s}, \frac{z}{2^s}, \frac{u}{2^s}$ — целые. Ну, а это невозможно ни при каких натуральных x, y, z, u.

А вот уравнение, у которой бесконечного много решений, но которое исследуется тем же методом.

Задача 3. Найти все решения в натуральных числах уравнения

$$x^2 - 2y^2 = 1.$$

Решение е. Очевидно, что $x_1 = 3, y_1 = 2$ — решение данного уравнения. Докажем, что если пара x, y — решение, то пара 3x + 4y; 2x + 3y — тоже решение. Это следует изложества

$$(3x + 4y)^2 - 2(2x + 3y)^2 = x^2 - 2y^2.$$

Таким образом,

$$x_2 = 3 \cdot 3 + 4 \cdot 2 = 17,$$

$$y_2 = 2 \cdot 3 + 3 \cdot 2 = 12;$$

$$x_3 = 99, y_3 = 70,$$ и так далее.

Мы указываем бесконечную последовательность решений $x_1, y_1; x_2, y_2; \dots$ Докажем теперь, что других чисел, удовлетворяющих уравнению, нет.

Пусть x, y — неокторое решение. В таком случае 3x - 4y, 3y - 2x — также решение, либо

$$(3x - 4y)^2 - 2(3y - 2x)^2 = x^2 - 2y^2.$$

Из условия 9 = 9x^2 - 18y^2 > -2y^2 следует, что 3x > 4y; а при y > 2 из условия 4 = 4x^2 - 8y^2 < y^2 следует, что 3y > 2x. To есть при y > 2 мы из решения x, y получаем решение $x^{(1)}, y^{(1)}$ в натуральных числах, причем $x^{(1)} < x, y^{(1)} < y$. Так как этот процесс не может продолжаться бесконечно (в любом неупустом множестве натуральных чисел есть наименьший элемент!), то когда-нибудь мы получим решение $x^{(n)}, y^{(n)}$, где $y^{(n)} \leqslant 2$. Так как $y^{(n)}$, очевидно, не может равнять 1, то $y^{(n)} = 2$. Значит, $x^{(n)} = 3$.

А это и означает, что числа x и y принадлежат построенной ранее последовательности.

Do сх пор мы рассматривали только уравнения. Телерь решим нашим методом «текстового» задачу.

Задача 4. Имеется 2n + 1 цифры, каждой из которых весит целое число граммов. Известно, что любые 2n из них можно так разложить на чиси весов, по n на каждую, что настуит равновесие. Доказать, что все цифры имеют одинаковый вес.

Решение е. Ясно, что всегири одновременно имеют или четный или нечетный вес: вес любых 2 n гирь четен. Вычитем теперь весов всех гирь вес самой легкой гири (или самых легких, если их несколько). Новая система гирь, оченьindo, также удовлетворяет условиям задачи, причем среди гирь есть «гири» нульового веса. Поэтому опять же получаем, что вес всех гирь четен, и так далее. Из «бесконечного спуска» следует, что все «гири» нульовые, а это и означает, что все исходные гири имеют одинаковый вес.

Идея бесконечного спуска позволяет решать неокторные задачи комбиниаторов геометрии.

Задача 5. Можно ли куб разрезать на неокторко различных кубков?

Решение е. Сделаем сначала одно очень замечание. Пусть квадрат P разбит на конечное число различных квадратов. Тогда самый маленький квадрат не прилегает к границе квадрата P.

Допустим теперь, что куб Q удалилось разрезать на различные кубы Q_j; пусть P — одна из граней Q. Кубы Q_j, прилегающие к P, порождают разбиение P на попарно различные квадраты. Пусть P_1 — самый маленький из этих квадратов, Q_1 — соответствующий к границе P, следовательно, он окружен большими квадратами. Соответствующие кубы образуют «колодец», в котором лежит кубик Q_1.

27

Пусть $P_1'$ — «верхняя» грань (противоположная грани $P_1$) куба $Q_1$. Кубы, прилегающие к $P_1'$, порождают разбиение $P_1'$ на различные квадраты. Вновь самый маленький из них, $P_2$, расположен внутри $P_1'$, следовательно, кубы, окружающие соответствующей кубик $Q_2$, больше $Q_2$ и снова образуют «колодец». Продолжая построение и дальнейше, мы получим бесконечную «башню», состоящую из все уменьшаюшихся кубов, а это невозможно.

В заключение — задача на клетчатой бумаге.

Задача 6. Дан лист клемма-той бумаги. Доказать, что при $n \neq 4$ не существует правильного $n$-уольника с вершинами в узлах. Действительно, пусть $a$ — длина стороны этого треугольника; тогда $a^2$ — целое число по теореме Пифагора. Площадь треугольника равна $\frac{a^2 \sqrt{3}}{4}$, то есть irrationalна. С другой стороны, оченьindo, что площадь любого многоугольника с вершинами в узлах разциональная.

Поскольку в правильный шестиугольник можно писать правильный треугольник с вершинами в его вершинах, для $n=6$ утверждение тоже доказано.

Пусть $n \neq 3,4,6$. Допустим, что $P_1, P_2, \dots, P_n$ — $n$-уольник с вершинами в узлах. Отложим от точек $P_1, P_2, \dots, P_n$ векторы, соответствующее вектором $\overrightarrow{P_2}P_3; \overrightarrow{P_3}P_4; \dots, \overrightarrow{P_1}P_2$ (рис. 2). Новые точки вновь попадут в узлы решетки и образуют правильный $n$-уольник внутри первого равноваяного. С новым $n$-уольником можно построить так же, и так далее, без конца. Однако квадрат длины сторон $n$-уольника — целое число, а при наших построениях оно все время уменьшается!

У разженяя

1. Доказать, что основание и боковая сторона равноведренного треугольника с углом при вершине $36^\circ$ несозмерными.
2. Доказать, что число 7 нельзя представить в виде суммы квадратов трех разциональных чисел.
3. Решить в целых числах уравнения:
   a) $x^3 - 3y^3 - 9z^3 = 0$;
   b) $5x^3 + 11y^3 + 13z^3 = 0$.
4. Доказать, что уравнение
   a) $x^2 + y^2 + z^2 = 2xyz$;
   b) $(x+1)^3 - x^3 = y^2$.
5. Решить в натуральных числах уравнения:
   a) $x^2 + (x+1)^2 = y^2 + 1$;
   b) $3x^2 - 7y^2 + 1 = 0$;
   b) $(x+1)^3 - x^3 = y^2$.
6. Доказать, что нижкое число вида $4^n(8k-1)$, где $k$ и $n$ — натуральные, не является полным квадратом и не представимо в виде суммы двух или трех квадратов чисел.
7. $a_1, a_2, \dots, a_n$ — набор попарно различных натуральных чисел ($n > 2$). Из него получается новый набор $\frac{a_1 + a_2}{2}, \frac{a_2 + a_3}{2}, \dots, \frac{a_{n-1} + a_n}{2}, \frac{a_n + a_1}{2}$;
   из него — следующее, по тому же правлиу, и так далее. Доказать, что через несколько шагов обязаательно получится набор, в котором не все числа будут целыми.
8. Дан выпуклый многоугольник и точка внутри него. Доказать, что хотя бы один из перпендикуляров к плоскостям граней, проведенных через эту точку, пересекается с соответствующей гранью. Верен ли этот факт для невыпуклого многоугольника?
9. Пусть $a_1, a_2, \dots, a_{2n}$ — произвольный набор натуральных чисел. Доказать, что если образовать из него новый набор $b_1, b_2, \dots, b_{2n}$ по правлиу $b_k = |a_k+1 - a_k|$, $k=1, 2, \dots, 2^n$, $a_{2n+1} = a_1$, затем из набора $b_1, b_2, \dots, b_{2n}$ по тому же правлиу образовать набор $c_1, c_2, \dots, c_{2n}$, то через некоторое количество шагов мы придем к набору, состоящему только из нуля.