Часть 1. Разминка

Длина пути — это число стрелок (шагов) до единицы.

Число	Путь до 1	Длина пути
7	7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1	16
12	12 → 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1	9
19	19 → 58 → 29 → 88 → 44 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1	20

Полезная проверка: $12 = 2\cdot 6$ чётное, поэтому $12 \to 6$, и длина пути $12$ на 1 больше длины пути $6$: $9 = 8 + 1$.

---

Часть 2. Исследование

2.1. Путь числа 27

Полный путь (числа после 27):

82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242,
121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700,
350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668,
334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638,
319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288,
3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616,
2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244,
122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10,
5, 16, 8, 4, 2, 1

• Длина пути: 111 шагов.
• Самое большое число на пути: 9232 (это происходит на 77-м шаге: $3077 \cdot 3 + 1 = 9232$).

Это знаменитый «бунтарь»: 27 сначала долго растёт (почти в 343 раза больше исходного числа!), а потом обрушивается до 1.

2.2. Длины путей чисел от 1 до 20

n	1	2	3	4	5	6	7	8	9	10
длина	0	1	7	2	5	8	16	3	19	6

n	11	12	13	14	15	16	17	18	19	20
длина	14	9	9	17	17	12	20	20	20	7

(у 1 длина 0 — она уже и есть 1)

Дольше всех идут 18 и 19 — по 20 шагов.

2.3. Соседние числа с одинаковой длиной

Сравнивая соседние значения в таблице, получаем ровно 3 пары:

• $(12, 13)$ — оба по 9 шагов;
• $(14, 15)$ — оба по 17 шагов;
• $(18, 19)$ — оба по 20 шагов.

Ответ: 3 пары.

(Заметьте интересное «правило»: если $n \equiv 2 \pmod 4$ и путь $n$ начинается с $n \to n/2$, то часто длина $n$ совпадает с длиной $n+1$, когда $3(n+1)+1$ даёт «удачное» маленькое число. Но это лишь эмпирика.)

2.4. Короткая программа (Python)

def collatz(n):
    path = [n]
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        path.append(n)
    return path

for n in [7, 12, 19, 27]:
    p = collatz(n)
    print(n, len(p) - 1, max(p))

lens = {n: len(collatz(n)) - 1 for n in range(1, 21)}
print(lens)
print(max(lens, key=lens.get))
print([(n, n+1) for n in range(1, 20) if lens[n] == lens[n+1]])

---

Часть 3. Небольшие доказательства

3.1. Нечётное число превращается в чётное

Пусть $n$ нечётное, то есть $n = 2k + 1$ для некоторого целого $k \ge 0$. Тогда

$3n + 1 = 3(2k+1) + 1 = 6k + 4 = 2(3k + 2).$

Полученное число делится на 2, значит, $3n + 1$ всегда чётное.

Что это значит: шаг «$\times 3 + 1$» никогда не идёт подряд. За ним всегда следует хотя бы одно деление на 2. Следовательно, «один нечётный шаг» на самом деле стоит минимум двух шагов:

$n \to 3n+1 \to \frac{3n+1}{2}.$

Более того, если $n = 4t+1$, то $3n+1 = 12t+4$ делится на 4, и за одним шагом умножения идут сразу два деления на 2.

3.2. Степень двойки $2^k$ идёт ровно $k$ шагов

Индукция по $k$.

База. $k = 0$: $2^0 = 1$, до единицы 0 шагов. $k = 1$: $2 \to 1$, 1 шаг.

Шаг индукции. Пусть $2^{k-1}$ доходит до 1 ровно за $k-1$ шаг. Число $2^k$ чётное (при $k \ge 1$), поэтому первый шаг:

$2^k \to \frac{2^k}{2} = 2^{k-1}.$

По предположению индукции от $2^{k-1}$ до 1 ещё $k-1$ шаг, значит всего $1 + (k-1) = k$ шагов.

Также заметим, что этот путь — ровно $2^k, 2^{k-1}, \dots, 4, 2, 1$, и он монотонно убывает, то есть никакого «лишнего» блуждания нет. $\blacksquare$

Например: $2^5 = 32 \to 16 \to 8 \to 4 \to 2 \to 1$ — 5 шагов.

3.3. Числа 1, 5, 21, 85, 341

Посмотрим на них: $1, 5, 21, 85, 341$. Разности: $4, 16, 64, 256 = 4^1, 4^2, 4^3, 4^4$. Это геометрическая прогрессия:

$n_k = 1 + 4 + 4^2 + \dots + 4^{k-1} = \frac{4^k - 1}{3} = \frac{2^{2k} - 1}{3}, \quad k = 1, 2, 3, \dots$

Проверка: $k=1 \Rightarrow 1$; $k=2 \Rightarrow 5$; $k=3 \Rightarrow 21$; $k=4 \Rightarrow 85$; $k=5 \Rightarrow 341$. $\checkmark$

1) $n_k$ — целое. Число $4^k - 1$ делится на 3, потому что $4 \equiv 1 \pmod 3$, поэтому $4^k \equiv 1^k = 1 \pmod 3$ и $4^k - 1 \equiv 0 \pmod 3$. Явно:

$4^k - 1 = (4-1)(4^{k-1} + 4^{k-2} + \dots + 4 + 1) = 3\big(4^{k-1} + \dots + 4 + 1\big),$

то есть $n_k = 4^{k-1} + \dots + 4 + 1 \in \mathbb{N}$. (Или: $2^{2k} - 1 = (2^k-1)(2^k+1)$, а среди двух подряд идущих нечётных чисел $2^k \pm 1$ ровно одно делится на 3, так что произведение делится на 3.)

2) $n_k$ нечётное. В сумме $1 + 4 + 4^2 + \dots + 4^{k-1}$ все слагаемые, кроме первого, чётные, плюс 1 — значит сумма нечётная. Значит, для $n_k$ применимо правило $n \to 3n+1$.

3) Один шаг даёт степень двойки:

$$3n_k + 1 = 3 \cdot \frac{4^k - 1}{3} + 1 = 4^k - 1 + 1 = 4^k = 2^{2k}.$$$

Это степень двойки! А по пункту 3.2 число $2^{2k}$ доходит до 1 ровно за $2k$ шагов. Итого полная длина пути:

$L(n_k) = 1 + 2k.$

Например, $n_3 = 21$: $21 \to 64 = 2^6 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$, всего $1 + 6 = 7$ шагов. $\blacksquare$

---

Чачасть 4. Главная задача

4.1. Пристально: доказать гипотезу Коллатца нельзя

Честный ответ: полного доказательства не существует — на сегодня его нет ни у кого в мире. Это одна из открытых задач математики; награда за решение — мировая известность. Поэтому здесь нельзя «доказать» утверждение: это означало бы решить задачу, открытую с 1937 года. Дальше — то, что доказать можно, и это реально упражнение из вашей задачи.

4.2. Нет цикла из двух чисел и нет фиксированной точки

Обозначим правило $T(n) = n/2$ при чётном $n$ и $T(n) = 3n+1$ при нечётном $n$.

Лемма 1 (нет фиксированной точки). Не существует натурального $n$ с $T(n) = n$.

• Если $n$ чётное: $n/2 = n \Rightarrow n = 0$, не натуральное.
• Если $n$ нечётное: $3n + 1 = n \Rightarrow 2n = -1$, нет натурального решения.

Теорема (нет двойного цикла). Не существует натуральных $n \ne m$ с $T(n) = m$ и $T(m) = n$.

Доказательство. Рассмотрим все случаи по чётности $n$.

Случай 1: $n$ чётное. Тогда $m = n/2$.

• Если $m$ чётное, то $T(m) = m/2 = n/4$. Из $n/4 = n$ получаем $n = 0$ — противоречие.
• Если $m$ нечётное, то $T(m) = 3m + 1 = 3\cdot\frac{n}{2} + 1$. Из условия $T(m) = n$:

$n = \frac{3n}{2} + 1 \Rightarrow 2n = 3n + 2 \Rightarrow n = -2,$

что не является натуральным числом. Противоречие.

Случай 2: $n$ нечётное. Тогда $m = 3n + 1$ (и $m$ чётно — это часть 3.1). Значит, $T(m) = m/2 = \frac{3n+1}{2}$. Из условия $T(m) = n$:

$n = \frac{3n+1}{2} \Rightarrow 2n = 3n + 1 \Rightarrow n = -1,$

снова не натуральное. Противоречие.

Все случаи приводят к противоречию, значит цикла длины 2 (и фиксированной точки) среди натуральных чисел не бывает. $\blacksquare$

4.3. Бонус: любой цикл длиннее трёх «узлов» — почему 1 → 4 → 2 → 1 единственный малый

Пусть есть цикл $x_1 \to x_2 \to \dots \to x_t \to x_1$ из натуральных чисел, среди которых $a$ нечётных и $b$ чётных ($a + b = t$). Перемножим все переходы:

$\prod_{i=1}^{t} x_{i+1} = \prod_{\text{нечётные } x_i} (3x_i + 1) \cdot \prod_{\text{чётные } x_i} \frac{x_i}{2} = \frac{\prod_{\text{нечёт}} (3x_i+1) \cdot \prod_{\text{чёт}} x_i}{2^{b}}.$

Левая часть равна $\prod x_i = \prod_{\text{нечёт}} x_i \cdot \prod_{\text{чёт}} x_i$. Сокращая $\prod_{\text{чёт}} x_i$:

$2^{b} \prod_{\text{нечёт}} x_i = \prod_{\text{нечёт}} (3x_i + 1).$

Так как $3x_i + 1 > 3x_i$, имеем $2^b > 3^a$. Отсюда:

• $a \ge 1$ (иначе $2^b = 1$, то есть пустой цикл) — любой цикл содержит нечётное число;
• $b > a \log_2 3 \approx 1{,}585\,a$, а значит $t = a + b > 2{,}585\,a \ge 3$.

Итого длина любого цикла не меньше 3. Цикл $1 \to 4 \to 2 \to 1$ ($a = 1$, $b = 2$, $2^2 = 4 > 3$ — неравенство выполнено) является единственным известным и, как считают, единственным вообще.

4.4. Что даёт «почти всё» Тао (2019)

Тао доказал: для почти всех натуральных $n$ (в смысле плотности — доля исключений стремится к нулю) выполнено $\liminf_k T^{(k)}(n) = O(1)$, то есть путь возвращается к сколь угодно малым числам. Но «почти все» логически не даёт «все»: контрпример мог бы быть среди редчайших чисел.

4.5. Как выглядело бы настоящее доказательство

Нужно исключить две возможности для каждого $n$:

1. Расходящийся путь — неограниченный рост. Трудность в том, что «в среднем» нечётный шаг ведёт к $\frac{3n+1}{2} \approx 1{,}5\,n$ (рост), а чёредование шагов ведёт к фактору $3/4 = 0{,}75$ (спад). Нужно строго доказать, что спад неизбежно перевешивает.
2. Цикл, не содержащий 1 — исключается, если доказать, что никакой цикл невозможен (уже исключены циклы длин 1 и 2; циклы длины $\ge 3$ остаются открытой частью проблемы, хотя известно, что минимальная длина неизвестного цикла огромна, а степень наименьшего элемента тоже велика).

Вывод: задание части 4 выполнено ровно на том уровне, который возможен: мы доказали отсутствие циклов длины 1 и 2 и отсутствие фиксированных точек, а полное доказательство гипотезы Коллатца остаётся открытой проблемой математики.

Часть 1. Разминка

Длина — это число переходов между числами. Поэтому путь от 1 до 1 имеет длину 0.

Число	Путь до 1	Длина
7	7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1	16
12	12 → 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1	9
19	19 → 58 → 29 → 88 → 44 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1	20

Часть 2. Исследование

Путь числа 27:

27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161,
484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155,
466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890,
445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850,
425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619,
4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154,
3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325,
976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80,
40, 20, 10, 5, 16, 8, 4, 2, 1

В пути 111 шагов. Самое большое число — 9232.

Длины путей для чисел от 1 до 20:

Число	Длина	Число	Длина
1	0	11	14
2	1	12	9
3	7	13	9
4	2	14	17
5	5	15	17
6	8	16	4
7	16	17	12
8	3	18	20
9	19	19	20
10	6	20	7

Дольше всех идут числа 18 и 19: у каждого длина пути равна 20.

Соседние числа с одинаковой длиной пути:

• 12 и 13 — длина 9;
• 14 и 15 — длина 17;
• 18 и 19 — длина 20.

Всего таких пар — 3.

Часть 3. Небольшие доказательства

1. Если n нечётное, то 3n + 1 чётно.

Нечётное число можно записать как $n=2q+1$. Тогда:

$$3n+1=3(2q+1)+1=6q+4=2(3q+2).$$

Значит, $3n+1$ делится на 2 и чётно. Поэтому следующим шагом его нужно разделить на 2. Если результат делится на 2 ещё раз, правило применяется повторно.

2. Число $2^k$ приходит к единице ровно за k шагов.

При каждом шаге степень двойки уменьшается на единицу:

$$2^k \to 2^{k-1} \to 2^{k-2} \to \cdots \to 2 \to 1.$$

До последнего шага все числа в этой цепочке больше 1, значит, раньше путь не заканчивается. Всего происходит ровно $k$ переходов. Для $k=0$ число уже равно 1, и шагов 0.

3. Общая формула для чисел 1, 5, 21, 85, 341.

Формула:

$$n_j=\frac{4^j-1}{3}, \qquad j=1,2,3,\ldots$$

Она даёт $1, 5, 21, 85, 341,\ldots$.

Так как $4\equiv1\pmod 3$, число $4^j-1$ делится на 3. Следовательно, $n_j$ — целое положительное число. Кроме того,

$$3n_j+1=3\cdot\frac{4^j-1}{3}+1=4^j=2^{2j}.$$

Значит, за один шаг $n_j$ превращается в степень двойки. После этого до единицы остаётся ещё $2j$ шагов.

Часть 4. Главная задача

Доказать, что путь любого натурального числа приходит к 1, пока не удалось никому: это и есть открытая гипотеза Коллатца. Проверка очень большого, но конечного количества чисел и результаты о «почти всех» числах не доказывают утверждение для каждого натурального числа. Поэтому честно дать доказательство главной задачи сейчас нельзя.

Зато можно доказать, что цикла из двух различных положительных чисел нет. Обозначим переход по правилу Коллатца через $T$ и предположим, что $T(n)=m$ и $T(m)=n$.

• Если $n$ чётное, то $m=n/2<n$. Если $m$ тоже чётное, то $T(m)=m/2<m<n$, так что вернуться к $n$ нельзя. Если $m$ нечётное, то для возврата потребовалось бы $3m+1=n=2m$, откуда $m=-1$, что невозможно.
• Если $n$ нечётное, то $m=3n+1$ чётное. Тогда следующий шаг даёт $T(m)=m/2$. Для цикла нужно, чтобы $(3n+1)/2=n$, откуда снова получилось бы $n=-1$, что невозможно.

Значит, цикла из двух различных положительных чисел нет. Это исключает только двухчисловые циклы, но само по себе не доказывает гипотезу и не исключает циклы большей длины. Известный цикл длины три — $1\to4\to2\to1$.