Сергей Жестков - преподаватель МФТИ и по совместительству эксперт OTUS, приглашает всех желающих на бесплатный демо-урок продвинутого курса "Математика для Data Science", по теме: «Отображения, их матрица и диагонализация».
А мы традиционно делимся с вами переводом интересного материала.
Несмотря на недавние сподвижки с небезызвестной гипотезой Коллатца, мы до сих пор не можем понять, может ли число выйти из бесконечного цикла.
Эта статья идет вместе с предупреждением: не пытайтесь решить эту математическую задачу.
Вы будете испытывать соблазн попробовать сделать это. Эта проблема достаточно просто сформулирована, понятна и слишком заманчива. Просто выберите число, любое число: если число четное, разделите его пополам; если оно нечетные, умножьте его на 3 и прибавьте 1. Возьмите получившееся новое число и повторяйте этот процесс снова и снова. Если вы будете продолжать выполнять эти итерации достаточное количество раз, в конечном итоге вы застрянете в бесконечном цикле. По крайней мере, мы так думаем.
Возьмем, к примеру, 10: 10 - четное, поэтому мы делим его пополам и получаем 5. Поскольку 5 - нечетное число, мы умножаем его на 3 и прибавляем 1. Теперь у нас есть 16, которое является четным, поэтому мы делим его на 2 и получаем 8, а затем делим пополам 8 и получаем 4, затем снова делим его пополам и получаем 2, и еще раз, получив наконец 1. Поскольку 1 нечетно, мы утраиваем его и прибавляем 1. Мы снова вернулись к 4, а мы уже знаем, куда это нас приведет: 4 превратится в 2, которое превратится в 1, которое превратится в 4, и так далее. Мы застряли в бесконечном цикле.
Или давайте попробуем 11: это нечетное число, поэтому мы утроим его и прибавим 1. Теперь мы получили 34, что является четным числом, поэтому мы делим его пополам и получаем 17, утраиваем и прибавляем 1, чтобы получить 52, уменьшаем вдвое, чтобы получить 26, и снова, чтобы получить 13, устраиваем его и добавляем 1, чтобы получить 40, уменьшите его вдвое, чтобы получить 20, затем 10, затем 5, утраиваем и добавляем 1, чтобы получить 16, делим пополам, чтобы получить 8, затем 4, 2 и 1. И мы снова застряли в бесконечном цикле.
Печально известная гипотеза Коллатца гласит, что если вы начнете с любого положительного целого числа, вы всегда окажетесь в этом бесконечном цикле. И вы, вероятно, проигнорируете мое предупреждение о попытке решить эту проблему: она кажется слишком простой и слишком складной, чтобы сопротивляться пониманию. На самом деле, было бы трудно найти математика, который бы не пытался найти подход к этой проблеме.
И я не смог проигнорировать ее, когда впервые узнал о ней в школе. Мы с друзьями целыми днями обменивались захватывающими идеями, которые в итоге никак не приближали нас к ответу. Но гипотеза Коллатца печально известна не просто так: даже если каждое число, которое когда-либо было опробовано, в конечном итоге попадает в этот цикл, мы все еще не можем быть уверены, что это утверждение справедливо всегда. Несмотря на все внимание, это до сих пор всего лишь предположение.
Тем не менее некоторый прогресс все же был достигнут. Один из величайших математиков в мире проигнорировал все предупреждения и взялся за дело, в итоге достигнув крупнейшего за последние десятилетия успеха в решении этой проблемы. Давайте посмотрим, что делает эту простую проблему такой сложной.
Чтобы понять гипотезу Коллатца, мы начнем со следующей функции:
(even - четные, odd - нечетные)
Вы можете вспомнить «кусочные» функции из школы: функция выше принимает на вход n и применяет к нему одну из двух формул, в зависимости от того, является n четным или нечетным. Эта функция f применяет формулы процедуры, описанной выше: например, f (10) = 10/2 = 5, поскольку 10 четное, и f (5) = 3 × 5 + 1 = 16, поскольку 5 нечетное. Благодаря формуле для нечетных переменных гипотеза Коллатца также известна как гипотеза 3n + 1.
Гипотеза Коллатца касается «орбит» этой функции f. Орбита - это то, что вы получите, если начнете с какого-либо числа и многократно примените функцию, принимая каждый результат и возвращая его в функцию в качестве новой переменной. Мы называем это «итерированием» функции. Мы уже начали вычислять орбиту 10 для f, поэтому давайте найдем следующие несколько членов:
f (10) = 10/2 = 5
f (5) = 3 × 5 + 1 = 16
f (16) = 16/2 = 8
f (8) = 8/2 = 4
Удобно представлять орбиту в виде последовательности со стрелками. Вот орбита 10 для f:
10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → …
В конце мы видим, что застряли в бесконечном цикле 1 → 4 → 2 → 1 →….
Аналогично, орбита 11 для f может быть представлена как
11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → ….
Мы снова попадаем в тот же цикл. Попробуйте еще несколько примеров, и вы увидите, что орбита всегда стабилизируется в этом цикле 4 → 2 → 1 →…. Начальные значения 9 и 19 забавны, а если у вас есть несколько свободных минут, попробуйте 27. Если ваша арифметика будет верна, вы окажетесь в цикле после 111 шагов.
Гипотеза Коллатца утверждает, что орбита каждого числа для f в конечном итоге достигает 1. И хотя никто не доказал эту гипотезу, она была проверена для каждого числа меньше 26⁸. Так что, если вы ищете контрпример, вы можете начать с 300 квинтиллионов. (Вы были предупреждены!)
Легко проверить, что гипотеза Коллатца верна для любого конкретного числа: просто вычисляйте орбиту, пока не дойдете до 1. Но чтобы понять, почему так трудно доказать ее для каждого числа, давайте исследуем немного более простую функцию ℊ.
Функция ℊ похожа на f, но для нечетных чисел она просто добавляет 1 вместо того, чтобы сначала утроить их. Так ℊ и f разные функции, числа имеют разные орбиты. Например, вот орбиты 10 и 11 для ℊ:
10 → 5 → 6 → 3 → 4 → 2 → 1 → 2 → 1 → 2 → …
11 → 12 → 6 → 3 → 4 → 2 → 1 → 2 → 1→ 2 → …
Обратите внимание, что орбита числа 11 достигает 1 быстрее для ℊ, чем для f. Орбита 27 также достигает 1 намного быстрее для ℊ.
27 → 28 → 14 → 7 → 8 → 4 → 2 → 1 → 2 → …
В этих примерах орбиты ℊ тоже выглядят стабилизирующимися, так же как орбиты f, но в немного более простой цикл:
→ 2 → 1 → 2 → 1 → ….
Мы можем предположить, что орбиты ℊ всегда стремятся к 1. Я назову это гипотезой «Ноллатца», но мы также можем называть ее гипотезой n + 1. Мы могли бы поэкспериментировать с ней, проверив больше орбит, но знание того, что что-то верно для множества чисел - даже 26⁸ из них - не является доказательством того, что это верно для всех чисел. К счастью, гипотеза Ноллатца может быть доказана. Вот каким образом.
Во-первых, мы знаем, что половина положительного целого числа всегда меньше самого целого числа. Итак, если n четное и положительное, то ℊ(n) = n/ 2 < n. Другими словами, когда орбита достигает четного числа, следующее число всегда будет меньше.
Теперь, если n нечетное, то ℊ(n) = n + 1, что больше n. Но так п нечетно, п + 1 четно, и поэтому мы знаем куда орбита приведет нас дальше: ℊ поделит п + 1 пополам. Для нечетного n орбита будет выглядеть так:
Обратите внимание, что
. Поскольку
и
- это очень мало,
вероятно, тоже меньше n. И в самом деле, несложно доказать, что покуда n> 1, то всегда выполняется
Это говорит нам о том, что когда орбита ℊ достигает нечетное число большее 1, мы всегда будем получать меньшее число двумя шагами позже. Теперь мы можем обрисовать в общих чертах доказательство гипотезы Ноллатца: где угодно на нашей орбите, будь то четное или нечетное число, мы будем иметь тенденцию к снижению. Единственное исключение - когда мы достигаем 1 в конце этого спуска. Но как только мы достигаем 1, мы попадаем в бесконечный цикл, как мы и предполагали.
Может ли аналогичное доказательство сработать с гипотезой Коллатца? Вернемся к исходной функции.
Как и в случае с ℊ, подстановка в f четного числа уменьшает его. Как и в случае с ℊ, подстановка в f нечетного числа возвращает нам четное число, что означает, что мы знаем, что произойдет дальше: f сократит новое число вдвое. Вот как выглядит орбита f, когда n нечетное:
Но здесь наше доказательство начинает разваливаться. В отличие от примера выше, это число больше n:
и
, что всегда больше n. Ключом к доказательству гипотезы Ноллатца было то, что нечетное число через два шага должно стать меньше, но это неверно в случае Коллатца. Наше доказательство не работает.
Если у вас есть что-то общее со мной и моими школьными друзьями, вы, возможно, захотите попробовать доказать, что гипотеза Коллатца ложна: в конце концов, если орбита продолжает увеличиваться, то как она может опуститься до 1? Но это доказательство требует понимания того, что происходит дальше, а что происходит дальше, проливает свет на то, почему гипотеза Коллатца настолько скользкая: мы не можем быть уверены, четное ли
или нечетное.
Мы знаем, что 3n + 1 четное. Если 3n + 1 также делится на 4, то
тоже четное, и орбита будет уменьшаться. Но если 3n + 1 не делится на 4, то
нечетное, и орбита увеличивается. Как правило, мы не можем предсказать, что из этого окажется правдой, поэтому наше доказательство несостоятельно.
Но этот подход не совсем бесполезен. Поскольку половина всех положительных целых чисел четные, с вероятностью в 50%
четное, что делает следующий шаг по орбите равным
. Для n > 1 это уже меньше, чем n, поэтому в половине случаев нечетное число должно уменьшаться после двух шагов. Также существует 50%-ная вероятность, что
это четное число, что означает, что существует 25%-ная вероятность того, что нечетное число станет меньше более чем в два раза после трех шагов. И так далее. Конечный результат состоит в том, что в некотором среднестатистическом случае орбиты Коллатца уменьшаются, когда они сталкиваются с нечетным числом. А поскольку орбиты Коллатца всегда уменьшаются для четных чисел, это наталкивает на вывод, что все последовательности Коллатца в долгосрочной перспективе должны уменьшаться. Это доказательство на основе вероятностей широко известно, но еще никому не удалось довести его до полного доказательства гипотезы.
Однако несколько математиков доказали, что гипотеза Коллатца «почти всегда» верна. Это означает, что они доказали, что по сравнению с количеством чисел, которые, как они знают, приводят к 1, количество чисел, в которых они не уверены, ничтожно мало. В 1976 году эстонско-американский математик Рихо Террас доказал, что после многократного итерирования функции Коллатца почти все числа в конечном итоге оказываются ниже тех, с которых они начинались. Как мы видели выше, доказательство того, что числа на орбите постоянно уменьшаются, - это один из способов доказать, что они в конечном итоге доходят до 1.
А в 2019 году Теренс Тао, один из величайших математиков мира, улучшил этот результат. Если Террас доказал, что почти для всех чисел последовательность Коллатца для n в итоге приходит к числу меньшему, чем n, Тао доказал, что почти для всех чисел последовательность Коллатца для n заканчивается намного ниже: ниже
, ниже
, ниже
(натуральный логарифм n), даже ниже каждого f(n), где f(x) - любая функция, уходящая в бесконечность, независимо от того, насколько медленно. То есть почти для каждого числа мы можем гарантировать, что его последовательность Коллатца будет настолько низкой, насколько мы захотим. В разговоре о проблеме, Тао сказал, что этот результат является «пределом того насколько близко можно подобраться к гипотезе Коллатца без фактического решения.»
Даже в этом случае гипотеза будет продолжать привлекать математиков и энтузиастов. Так что выберите число, любое число и вперед. Просто помните, вас предупреждали: не зацикливайтесь бесконечно.
Упражнения
1. Покажите, что существует бесконечно много чисел, чьи орбиты Коллатца проходят через 1.
2. «Время остановки» числа n - это наименьшее количество шагов, которое требуется, чтобы орбита Коллатца числа n достигла 1. Например, Время остановки 10 равно 6, а время остановки 11 равно 14. Найдите два числа со временем остановки 5.
3. В недавнем разговоре о гипотезе Коллатца Терренс Тао упомянул следующую функцию Коллатца:
Тао указывает, что в дополнение к петле 1 → 2 → 1 → 2 → 1… появляются еще две петли. Вы можете их найти?
Ответы
Обратите внимание, что каждая степень двойки имеет простой орбитальный путь к 1. Например,
Поскольку существует бесконечно много степеней двойки, существует бесконечно много чисел, чьи орбиты Коллатца проходят через 1.
Обратите внимание что 2^5 имеет время остановки 5, так как
…. А поскольку 2^4 имеет время остановки 4, любое число, которое на один шаг отстает от 2^4, имеет время остановки 5. Например, 5 → 16 → 8 → 4 → 2 → 1. Могут ли быть и другие?
Другие петли:
5 → 14 → 7 → 20 → 10 → 5 → …
и
17 → 50 → 25 → 74 → 37 → 110 → 55 → 164 → 82 → 41 → 122 → 61 → 182 → 91 → 272 → 136 → 68 → 34 → 17 → …