что такое наименьшее возможное число

― верный пример в пункте а);

― обоснованное решение пункта б);

― доказательство того, что в пункте в) количество цифр не превосходит четырёх;

― приведён пример наибольшего хорошего четырёхзначного числа.

Источник

Простая математическая задача, которую мы все еще не в состоянии решить

А мы традиционно делимся с вами переводом интересного материала.

Несмотря на недавние сподвижки с небезызвестной гипотезой Коллатца, мы до сих пор не можем понять, может ли число выйти из бесконечного цикла.

Эта статья идет вместе с предупреждением: не пытайтесь решить эту математическую задачу.

Вы будете испытывать соблазн попробовать сделать это. Эта проблема достаточно просто сформулирована, понятна и слишком заманчива. Просто выберите число, любое число: если число четное, разделите его пополам; если оно нечетные, умножьте его на 3 и прибавьте 1. Возьмите получившееся новое число и повторяйте этот процесс снова и снова. Если вы будете продолжать выполнять эти итерации достаточное количество раз, в конечном итоге вы застрянете в бесконечном цикле. По крайней мере, мы так думаем.

Или давайте попробуем 11: это нечетное число, поэтому мы утроим его и прибавим 1. Теперь мы получили 34, что является четным числом, поэтому мы делим его пополам и получаем 17, утраиваем и прибавляем 1, чтобы получить 52, уменьшаем вдвое, чтобы получить 26, и снова, чтобы получить 13, устраиваем его и добавляем 1, чтобы получить 40, уменьшите его вдвое, чтобы получить 20, затем 10, затем 5, утраиваем и добавляем 1, чтобы получить 16, делим пополам, чтобы получить 8, затем 4, 2 и 1. И мы снова застряли в бесконечном цикле.

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

И я не смог проигнорировать ее, когда впервые узнал о ней в школе. Мы с друзьями целыми днями обменивались захватывающими идеями, которые в итоге никак не приближали нас к ответу. Но гипотеза Коллатца печально известна не просто так: даже если каждое число, которое когда-либо было опробовано, в конечном итоге попадает в этот цикл, мы все еще не можем быть уверены, что это утверждение справедливо всегда. Несмотря на все внимание, это до сих пор всего лишь предположение.

Тем не менее некоторый прогресс все же был достигнут. Один из величайших математиков в мире проигнорировал все предупреждения и взялся за дело, в итоге достигнув крупнейшего за последние десятилетия успеха в решении этой проблемы. Давайте посмотрим, что делает эту простую проблему такой сложной.

Чтобы понять гипотезу Коллатца, мы начнем со следующей функции:

Удобно представлять орбиту в виде последовательности со стрелками. Вот орбита 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, но в немного более простой цикл:

Во-первых, мы знаем, что половина положительного целого числа всегда меньше самого целого числа. Итак, если n четное и положительное, то ℊ(n) = n/ 2 . Другими словами, когда орбита достигает четного числа, следующее число всегда будет меньше.

Обратите внимание, что

вероятно, тоже меньше n. И в самом деле, несложно доказать, что покуда n> 1, то всегда выполняется

Может ли аналогичное доказательство сработать с гипотезой Коллатца? Вернемся к исходной функции.

Как и в случае с ℊ, подстановка в f четного числа уменьшает его. Как и в случае с ℊ, подстановка в f нечетного числа возвращает нам четное число, что означает, что мы знаем, что произойдет дальше: f сократит новое число вдвое. Вот как выглядит орбита f, когда n нечетное:

Но здесь наше доказательство начинает разваливаться. В отличие от примера выше, это число больше n:

, что всегда больше n. Ключом к доказательству гипотезы Ноллатца было то, что нечетное число через два шага должно стать меньше, но это неверно в случае Коллатца. Наше доказательство не работает.

Если у вас есть что-то общее со мной и моими школьными друзьями, вы, возможно, захотите попробовать доказать, что гипотеза Коллатца ложна: в конце концов, если орбита продолжает увеличиваться, то как она может опуститься до 1? Но это доказательство требует понимания того, что происходит дальше, а что происходит дальше, проливает свет на то, почему гипотеза Коллатца настолько скользкая: мы не можем быть уверены, четное ли

Мы знаем, что 3n + 1 четное. Если 3n + 1 также делится на 4, то

тоже четное, и орбита будет уменьшаться. Но если 3n + 1 не делится на 4, то

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

Но этот подход не совсем бесполезен. Поскольку половина всех положительных целых чисел четные, с вероятностью в 50%

четное, что делает следующий шаг по орбите равным

. Для n > 1 это уже меньше, чем n, поэтому в половине случаев нечетное число должно уменьшаться после двух шагов. Также существует 50%-ная вероятность, что

это четное число, что означает, что существует 25%-ная вероятность того, что нечетное число станет меньше более чем в два раза после трех шагов. И так далее. Конечный результат состоит в том, что в некотором среднестатистическом случае орбиты Коллатца уменьшаются, когда они сталкиваются с нечетным числом. А поскольку орбиты Коллатца всегда уменьшаются для четных чисел, это наталкивает на вывод, что все последовательности Коллатца в долгосрочной перспективе должны уменьшаться. Это доказательство на основе вероятностей широко известно, но еще никому не удалось довести его до полного доказательства гипотезы.

А в 2019 году Теренс Тао, один из величайших математиков мира, улучшил этот результат. Если Террас доказал, что почти для всех чисел последовательность Коллатца для n в итоге приходит к числу меньшему, чем n, Тао доказал, что почти для всех чисел последовательность Коллатца для n заканчивается намного ниже: ниже

Даже в этом случае гипотеза будет продолжать привлекать математиков и энтузиастов. Так что выберите число, любое число и вперед. Просто помните, вас предупреждали: не зацикливайтесь бесконечно.

Упражнения

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

3. В недавнем разговоре о гипотезе Коллатца Терренс Тао упомянул следующую функцию Коллатца:

Тао указывает, что в дополнение к петле 1 → 2 → 1 → 2 → 1… появляются еще две петли. Вы можете их найти?

Ответы

Нажмите, чтобы раскрыть ответ 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 → …

Источник

• ← что такое нитрат серебра
• кредит в лизинг что это такое →