В сети и в развлекательной литературе нередко можно встретить разные математические фокусы: вас просят задумать какое-то число, затем выполнить с ним ряд арифметических действий. После этого собеседник точно называет получившееся у вас число. Большинство этих фокусов основано на том, что исходное число в ходе преобразований незаметно подменяется другим, а затем за несколько шагов сводится к известному ответу. Такие фокусы, например, можно встретить в книгах Якова Перельмана.
Гипотеза Коллатца оставляет все подобные фокусы позади. На первый взгляд может показаться, что это тоже какой-то фокус с подвохом. Однако при внимательном рассмотрении оказывается, что никакого подвоха нет. Вы загадываете число и несколько раз повторяете для него одно из двух арифметических действий. Удивительно, что результат этих действий будет всегда одним и тем же. Или не всегда? Этого пока наверняка никто не знает, но получить что-то другое пока никому не удалось.
Давайте попробуем. Итак, загадайте любое целое положительное число. Дальше следуйте простому алгоритму:
1. Если число чётное, разделите его на 2. Иначе умножьте его на 3 и прибавьте 1.
2. Повторите шаг 1 с полученным числом.
Как вы думаете, что мы получим в итоге, если будем много раз выполнять шаги 1 и 2?
Немецкий математик Лотар Коллатц считает, что для любого целого положительного числа мы рано или поздно получим сначала 4, потом закономерно — 2, а потом 1. И после этого мы будем ходить по кругу, вновь и вновь получая цепочку 4–2–1. Самое удивительное в том, что мы придём к такому результату, с какого бы числа мы ни начали.
Не верите? Это не сложно проверить, тем более, что условия задачи очень просты. Пожалуй, на данный момент это простейшая формулировка нерешённой математической задачи — умножать и складывать умеет каждый. Справедливости ради стоит заметить, что для некоторых исходных чисел считать придётся долго. Так что для загадывания в дружеской компании этот «фокус» если и подойдёт, то только для небольших исходных чисел. Но мы всегда можем написать маленькую программку — куда уж проще: цикл с одним условием. Вот мой вариант простейшей программы на любимом Delphi:
program collatz;
{$APPTYPE CONSOLE}
uses
SysUtils, Classes;
var
s: string;
num, steps, max: integer;
begin
readln(s);
num:=strtoint(s); // Исходное число
steps:=0; // Счётчик шагов
max:=num; // Максимальное промежуточное число
while (num<>1) do
begin
if odd(num) then num:=num*3+1 // Число нечётно
else num:=num div 2; // Число чётно
if num>max then max:=num;
inc(steps);
writeln(inttostr(num));
end;
writeln('Steps - '+inttostr(steps));
writeln('Max - '+inttostr(max));
end.При желании попробуйте сами немного поэкспериментировать с этой гипотезой. Кстати, в сети можно найти много интересных визуализаций, показывающих распределение решений и шагов для разных исходных данных. А ещё есть сайт, который содержит варианты реализации этой задачи для множества языков программирования.
Знаете, что ещё интересно? Утверждение Коллатца не зря называется гипотезой — пока никто так и не смог придумать её логическое доказательство. Лотар Коллатц сформулировал свою гипотезу ещё в 30-х годах 20 века и с тех пор предпринимались многочисленные попытки доказать или опровергнуть это утверждение с помощью строгой математической логики. Но всё, чего смогли добиться математики, — это просто проверить гипотезу экспериментально. В этой задаче программный поиск решения по сути ничем не ограничен, кроме вычислительных мощностей. Пока гипотеза не опровергнута — даже для огромных исходных чисел рано или поздно алгоритм достигает 1. Для решения этой задачи даже был организован проект добровольных распределённых вычислений. Но для классической математики этого недостаточно. Числа иногда бывают очень коварны. Где-то среди неимоверно огромных исходных чисел может скрываться такое исходное число, для которого гипотеза не подтвердится.
Кстати, у гипотезы Коллатца есть ещё несколько менее известных названий:
дилемма 3n+1 — это вариант шага для нечётных чисел;
гипотеза градины — графики последовательностей чем-то напоминают траектории движения града в атмосфере;
гипотеза Улама — по имени польского математика Станислава Улама;
проблема Какутани — по имени японского математика Сидзуо Какутани;
гипотеза Туэйтса — по имени английского математика Брайна Туэйта;
алгоритм Хассе — по имени немецкого математика Хельмута Хассе;
сиракузская проблема.
По количеству разнообразных наименований видно, что математиков всерьёз заинтересовала эта проблема. Однако оказалось, что это одна из тех «вредных» задач, которые очень легко формулируются, но чрезвычайно тяжело решаются. Прямо как Великая теорема Ферма.
Числа в этой задаче ведут себя крайне странно: в некоторых случаях вычисления доходят до единицы очень быстро, а иногда промежуточный итог добирается до довольно большого числа, а затем быстро «срывается» вниз — до самой единицы. Например, для начального числа 27 промежуточный итог достигает 9232, а затем за несколько шагов быстро спускается до 1. В итоге количество шагов для 27 равно 111. И это при том, что для 26 оно равно 10 (максимальное промежуточное число — 40), а для 28 — 18 (максимальное промежуточное число — 52).
Хоть математикам и не удалось полностью логически подтвердить или опровергнуть гипотезу, они всё же кое-чего достигли. Как это часто бывает, учёные подбираются к решению постепенно. Совсем недавно, 8 сентября 2019, математик из Калифорнийского университета Теренс Тао опубликовал доказательство, где показано, что гипотеза Коллатца, по меньшей мере, «почти» верна «почти» для всех чисел. История того, как математики штурмовали эту проблему и о том, чего удалось достичь Теренсу Тао подробно описана в этой статье.
В журналах и в сети уже неоднократно появлялись варианты доказательства гипотезы Коллатца. Однако, к большому сожалению, все они либо содержали ошибки, либо были неполными. Так что гипотеза пока остаётся гипотезой, а ещё — крутым и красивым математическим фокусом.
Статья была впервые опубликована на другом ресурсе 10 марта 2021.
Комментарии (100)
Alonerover
28.12.2021 10:50+2Определённо результат есть следствие самих правил.
Возникает вопрос - как будет меняться результат если менять правила?
Natasha2021
29.12.2021 08:40извините за глупый вопрос - зачем нечетное число сначала умножать на 3? При умножении нечетного числа на 3 все равно ведь получим нечетное, затем, чтобы получить четноеЮ прибавляем 1. Вроде бы если просто к исходному нечетному числу прибавить 1 (не умножая его предварительно на 3), получим четное число, а далее идем согласно алгоритму. Результат будет тем же (4 - 2 -1), только придем к нему короче. Можете, пожалуйста, объяснить, в чем смысл умножения на 3?
Botu
29.12.2021 10:03+2Подозреваю, чтобы оно точно стало не простым... Если в формулировке задачи было - берем любое непростое число - это чуть чуть сложнее, чем берем любое число и умножаем на 3. Хотя можно по программе проверить - работает ли гипотеза при умножении на 7 например ...
Milliard
29.12.2021 12:16+4Если просто прибавить 1, то в итоге гарантированно придем к единице, доказать просто. В случае 3*n+1 доказать, что для любого натурального n результат будет единица, пока никому не удалось, т.к. не исключены другие два варианта: результат устремится к бесконечности или результат замкнется в цикле, отличном от 4-2-1.
vassabi
29.12.2021 14:11... или может быть еще один цикл "четное-четное-нечетное", который не 4-2-1
Nikita22007
29.12.2021 20:18+2Другого цикла из 3х элементов быть, скорее всего, не может. Доказывается просто
Обозначим последнее число (нечётное) за X. Согласно циклу можно получить последовательность "3x+1, (3x+1)/2, (3x+1)/4", она же "4x, 2x, x". Выводим формулу: (3x+1)/4=x => x=1. Других решений нетAngmarets
29.12.2021 21:00В видео из первого комментария утверждают, что есть пруф на то, что если цикл и существует - он не может включать меньше чем 180 миллиардов чисел.
rpc1
29.12.2021 19:12Тогда,насколько я понял, мы не придем к результату 4-2-1, который будет повторяться бесконечное количество раз
Vsevo10d
28.12.2021 10:52+1Что-то я не особо вижу тут математической красоты. Единственным препятствием деления до единицы было бы получить простое число, поэтому условия таковы, что даже если мы на него натыкаемся, то "обходим" с помощью двух различных множителей. Процесс приводит к тому, что мы рано или поздно натыкаемся на ряд степени двойки, который автоматически "сгорает" до единицы. Как-то не сильно сложнее перельмановских задачек.
Wizard_of_light
28.12.2021 11:00+12Нет доказательства, что на каком-то числе не существует замкнутой последовательности, которая бесконечно крутится в цикле возрастания-убывания.
PsihXMak
28.12.2021 11:14+15Знаете, порой мне кажется, что за таким огромным количеством математических гипотез, мы теряем из виду какую то базовую концепцию, которая бы дала объяснение, как со всем этим работать. Подобно мнимым числам.
Wizard_of_light
28.12.2021 15:09+3Конечно упускаем, но тут уж такое - Вселенная не только велика, но и и не задокументирована. Так что всё наоборот - на доказательстве/для доказательства некоторого множества таких гипотез базовые концепции потом и строятся.
leshabirukov
28.12.2021 15:41+2Вот нет, даже если вдруг гипотетическое доказательство Коллатца сопутствующим ущербом закроет еще сколько-то актуальных гипотез, это будет небольшое их подмножество. Математика доказано (Гёделем) неисчерпаема.
charypopper
28.12.2021 16:04+1С Гёделем, если вы про полноту, то там не все так просто. В доказательстве нет ошибок, но он оно построено на законе исключённого третьего. Он кажется логичным, и в большинстве случаев даёт результат, который отражается в мире. Но такие доказательства, построенные от противного - имхо, показывают что не все так радужно. И, возможно, в целом - работает многозначная логика, и тогда часть докозателсьв неприменимы.
leshabirukov
28.12.2021 17:10+3Моя позиция сформирована под влиянием книги "Гёдель, Эшер, Бах" Хофштадтера, всячески рекомендую.
mayorovp
29.12.2021 23:25+1Тут хохма в том, что сам ввод многозначной логики уже означает выделение верных, но недоказуемых утверждений.
napa3um
30.12.2021 21:43Очень плюсую упомянутую в треде "Гёдель, Эшер, Бах" Хофштадтера, там он (помимо других метафор) поэтически обобщил до фундамента функцию математика, исследующего математические структуры - это не доказательства или опровержения теорем, это поиск симметрии и отклонения от неё. Такой минимальный квант математической мысли, кирпичик (хотьсколькозначной) логики, которым разум исследует вселенную (в том числе математическую) :).
PsihXMak
28.12.2021 11:03+3Согласен. Простое перемалывание чисел до тех пор, пока мы не наткнёмся на очередную степень двойки.
Nacreous1991
28.12.2021 12:39Ну например очевидно, что к примеру ряд f(n)=f(n-1)+1 и f(0)=1 никогда не наткнется на степень двойки. Почему же тут мы уверены что всегда будем натыкаться на степень двойки
shvez
28.12.2021 17:57+2ну ряды разные и судить по одному о свойствах другого вряд ли в этом случае поможет
Тут наверное фокус не в степени двойки, а в том, что всё больше становится чётных чисел, которые дают после деления чётное число. таким образом алогоритм сваливается к маленьким числам, где уже достигает степени двойки.
Хотя это всё гипотезы :)Nacreous1991
28.12.2021 18:27+3Чётных чисел всегда половина
Mavolio-Bent
29.12.2021 08:39+5Не совсем верно. Четных чисел столько же сколько всех чисел (натуральных или целых)
eaglebuk
29.12.2021 19:12+2К сожалению, это так. Хотя здравый смысл подсказывает, что во множестве чётных чисел не хватает некоторых чисел, входящих во множество целых)
masai
29.12.2021 19:24+2Здравый смысл плохо работает с бесконечностями. Например, аксиома выбора тоже кажется очевидной, но приводит к парадоксу удвоения шара.
DieselMachine
29.12.2021 21:05+3Нет, тут дело не в аксиоме выбора. Парадокс удвоения шара возможен потому что свободная группа с двумя образующими допускает специальное разложение (https://en.wikipedia.org/wiki/Paradoxical_set). Это связано с тем что шар вложен в трёхмерное Евклидово пространство, а на плоскости такой парадокс уже невозможен.
А аксиома выбора явно или неявно используется во многих местах, в том числе и в доказательстве этого парадокса, и без неё многие теоремы просто не могут быть доказаны.
masai
29.12.2021 23:59+1Да, пример неудачный, согласен. :)
Ну, в любом случае парадокс от аксиомы выбора зависит. Я хотел привести пример, когда из чего-то очевидно следует контринтуитивная результат. Но ничего конкретного в голову сейчас не приходит. (Вернее, приходит половина математики. :))
Вы бы что предложили?
DieselMachine
30.12.2021 18:40Например, Канторово множество, которое имеет меру нуль, но тем не менее его мощность континуум
Botu
29.12.2021 12:11+1на каждом новом этапе мы как минимум приводим число к четному и на следующим оно в 2 раза уменьшается, при этом уменьшаться может несколько раз подряд, а увеличение в 3 раза несколько раз подряд идти точно не может...
LeXaNe
28.12.2021 12:39+10Простое перемалывание чисел до тех пор, пока мы не наткнёмся на очередную степень двойки
Простое, да не совсем. Если изменить условие и вместо +1 сделать -1, то уже с числа 5 мы не выходим на степень двойки. 5-14-7-20-10-5...
Если и есть такое число, что приводит к бесконечному циклу, то результат преобразований не должен опускаться ниже уже проверенных чисел
leok
28.12.2021 21:09+1Попробуйте доказать, что следующее число должно делится на степень двойки выше чем 1. Или что средняя степень двойки выше, чем log(3)/log(2). То, что гипотеза кажется рабочей на небольших числах, которые мы можем посчитать, ничего не значит.
Особенно Skewes' number
MATAS-T-E
28.12.2021 12:39А как по научному оформить вариант решения, если он есть, и где публиковать?
LeXaNe
28.12.2021 12:46+10Публикуй здесь, на Хабре. Тут много математиков, которые укажут, где ошибка(а она найдется с точностью 99,99%)
Alexandroppolus
28.12.2021 12:53+6Не маловато ли девяток?
LeXaNe
28.12.2021 13:05+26Ага, зажал, для себя берегу. Планировал на выходных доказать гипотезу Римана ))
tenzink
28.12.2021 18:13+15Ландау заказал в университетской типографии 500 бланков со следующим текстом: «Уважаемый …! Благодарю Вас за присланную Вами рукопись с доказательством Великой теоремы Ферма. Первая ошибка находится на стр. … в строке …»
OBIEESupport
29.12.2021 22:44-1Алексей Савватеев на канале Маткульт-привет! недавно повторил его подвиг в видео. Ничего, так все теоремы без "великих математиков" в Кембридже и Оксфорде докажут. Нашим только крошки с их десктопов упадут.
pavelsc
28.12.2021 13:00+2const test = x => x%2 === 0 ? x/2 : x*3+1;const run = x => { if (x!==4) { console.log(x); run(test(x)) }};Кто хочет в браузере погонять
LeXaNe
28.12.2021 14:04+2Когда то давно гонял числа по данной гипотезе. При больших числах (число в степени несколько тысяч и больше) количество шагов становится одинаковым у большинства соседних чисел
ed007
28.12.2021 14:09Ожидал что-то поэффектнеее Парадокса Монти Холла, по крайней мере заголовок именно это и обещал.
Alexandroppolus
28.12.2021 14:40+2Не уверен, что сабж является самым крутым фокусом, но, имхо, уж покрупнее Монти-Холла (да и в тервере, кстати, есть более забавные штуки, например нетранзитивные кости или игры с рандомизированной стратегией).
WilmShakespear
28.12.2021 15:24-5Так себе фокус. По-моему, всё очевидно. Зачем умножать на 3 в условии задачи? Можете сразу прибавлять 1 к выбранному нечетному числу и поворять шаг 1, получите то же самое с той же сутью.
emaxx
28.12.2021 15:39+2Нет, это совсем другое. В гипотезе Коллатца, например, из 11 переходим в 34, и оттуда в 17. Это гораздо более "рандомная" последовательность, чем +1 и /2. Полная последовательность, начиная с 11, будет выглядеть 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
DoNotPanic
28.12.2021 16:04+2Интуитивно кажется, что вы правы, и 3-ка здесь только для запутывания, так как работа с ней делает последовательность менее очевидной.
Но если задачи эквивалентны, это ещё надо строго доказать… И пока не известно, доказательство чего проще (и правильна ли гипотеза из статьи в принципе).
Wizard_of_light
28.12.2021 16:19+1По-моему, всё очевидно. Зачем умножать на 3 в условии задачи?
Как раз для того чтобы было неочевидно. Навскидку кажется очевидным иное - число чётных и нечетных чисел в случайной выборке равно, четные делятся пополам, нечетные умножаются на 3, таким образом средний результат должен вроде как представлять серию умножений на 3/2, и в результате должен бесконечно возрастать. Однако для любых чисел последовательность с завидным постоянством, немного побрыкавшись, приводит к единице. Парадокс.
gchebanov
28.12.2021 18:05+4Не, тут всегда известно что сразу после умножения на 3 последует 1 деление на 2.
Таким образом в среднем за (1/2 + 3/2)/2 = 1. Но в случае с умножением нужно брать среднее геометрическое (или перейти к логарифмам), тут уже будет результат sqrt(3)/2~0.86<1.
Парадокса нет, проблема в том что нужно доказать для каждого, а не в "среднем".
Ndochp
28.12.2021 18:35Пусть начальное число А чет нечет — как повезет. к — средний коэффициент для следующего шага. Формула для "через 2 шага"
0,5(А:2*к) + 0,5((А*3+1):2)=А*к^2 к =((А(А*49+16))^0,5 + А)/(8А)что при больших А стремиться к 1, так что 3/2 тут не пахнет.
lzl
28.12.2021 18:47+2Если не умножать на три, то доказать что последовательность сойдется к 1 не сложно.
Для х > 1, x + 1 < 2x - значит наша последовательность будет содержать убывающую подпоследовательность. А т.к. числа натуральные, то эта подпоследовательность будет содержать минимальный элемент - еденицу.
bbc_69
29.12.2021 10:06В случае просто приавления 1 задача тривиальна: после +1 получаем чётное число, после деления 0,5n + 0.5, что заведомо меньше изначального (для чисел больше одного). Таким образом мы получаем убывающую последовательность, которая сходится к одному.
С умножением на 3 такой фокус не проходит: т.е. числа упираются в какое-то подобие степеней двойки. Немного контринтуитивно.
Chupaka
29.12.2021 11:18+1Выше привели пример: если делать не +1, а -1, то вроде суть всё ещё та же, но уже на пятёрке вы замкнётесь без достижения единицы. Но суть-то та же?
iShrimp
28.12.2021 17:55+15В целочисленных задачах прикол в том, что ответ может оказаться очень большим числом. Поэтому поиск его методом перебора может занять намного больше времени, чем возраст Вселенной.
Например, вот такое уравнение:
имеет такие натуральные корни:
Или может оказаться так, что она нерешаема за разумное время (как, например, вычисление TREE(3)), или существование решения практически недоказуемо.
Zanzibarra
28.12.2021 18:05+5На работе решил отвлечься на Хабр... Зря так сделал. В итоге час просто сам себе пытался доказать эту гипотезу. По-моему, её доказательство достаточно простое (если отталкиваться от чётности-нечётности и если я не обманул сам себя)
Сейчас написать своё решение не могу - надо полностью его продумать. Но буду надеяться, что по приезду домой смогу написать мини-статью (или просто большой комментарий) с некоторыми выкладками по этой теории
P.S. Смотрю на свои записи и удивляюсь... Если гипотеза градины до сих пор гипотеза, то мне не верится, что моё доказательство может считаться полноценным - слишком оно лёгкое
Jury_78
28.12.2021 18:14+21Это вольный пересказ записей на полях теоремы Ферма? :)
Zanzibarra
28.12.2021 19:06+1В общем-то я понял где я ошибся. Когда быстро пытаешься что-то доказать (по крайней мере, в моём случае), то теряешь из виду возможные допущения. В итоге, когда с холодной (буквально) головой я перечитал свои листы, понял, что там только почва для доказательства, но дальше я продвинуться не могу в силу слабого матаппарата
В комментарии ниже оставлю своё "доказательство", распишу где косяки и теорему, к которой у меня сводится доказательство данной теоремыiShrimp
28.12.2021 19:10+6Очень интересно! Главное - вовремя остановиться, так как гипотеза Коллатца уже получила дурную славу среди математиков, потративших на неё десятилетия жизни :)
Jury_78
28.12.2021 19:30+1Предпологаю, что все простые пути пройдены. Осталось что то зубодробильное. Правда всегда остается надежда на удачу, что все просмотрели что то элементарное...
khajiit
28.12.2021 20:07+1Ну, этот попробует как программист.
С продвижением к бесконечности все больше чисел, в двоичной системе имеющих хвост из нулей — то есть, многократно делимых на 2. Между тем как любое нечетное число после первого же преобразования всегда становится четным и испытывает распространение переноса — более или менее массовый битфлип с образованием хвоста из нулей.Каждое число на каждой итерации испытывает не более одного увеличения (после которого становится четным) и не менее одного уменьшения (младший бит после умножения на нечетное число и сложения с единицей с вероятностью 100% будет нулевым). Бит 1 с вероятностью 50% окажется равным 0, Бит 2 — 25%, Бит 3 — 12,5%, что дает в пределе 2 (последовательных уменьшения).
Итого, произвольно взятое число, грубо, в среднем умножается на 3 и делится на 4.
Deosis
29.12.2021 09:17+6Проблема среднего в том, что не учитываются выбросы.
Если в среднем число не является точной степенью двойки, то это не значит, что точных степеней двойки не существует.
khajiit
29.12.2021 12:44Так в данном случае выбросы — это несколько делений подряд, так? Когда мы получаем число вида a*2^n.
Deosis
30.12.2021 08:16Наоборот, выброс - много умножений на 3. Т.е. число вида 2^n-1
Такое число за 2n шагов перейдет в 3^n-1
khajiit
30.12.2021 09:19-1Так на три умножаются только нечетные числа, по условиям. После чего нечетный результат сразу приводится к четному: каскад умножений, по условиям задачи, — невозможен.
Cerberuser
30.12.2021 09:33+1Но возможен каскад пар - `n -> 3n+1 -> (3n+1)/2 -> 3*(3n+1)/2+1 -> (3*(3n+1)/2+1)/2 -> ...`. Если в цепочке нет двух делений подряд, то каждая пара операций будет увеличивать значение числа.
Cerberuser
30.12.2021 12:14+1Так вот в этом и вопрос - оно всегда на такой хвост наткнётся, или только "почти всегда"?
khajiit
30.12.2021 12:32-1Множество чисел вида a*2^n разве не мощнее множества нечетных чисел, произведениями которых (и не только их) они являются?
Не силен в теории множеств, могу нести чушь )
Cerberuser
30.12.2021 12:40+3Ну, во-первых, оба этих множества счётные (при этом их плотность в множестве натуральных чисел, конечно, разная, но мощность одинакова), а во-вторых, это всё равно аргумент "в среднем", "почти всегда", а не гарантия того, что ни одно число не проскочит только по "меньшему" подмножеству, не затронув "большее".
Alexandroppolus
30.12.2021 12:42+2Нет, не мощнее. Они оба - "алеф-0". Между элементами этих множеств легко установить взаимно-однозначное соответствие, по аналогии с тем как это делается для соответствия целых и рациональных.
bbc_69
29.12.2021 10:38Каждое число на каждой итерации испытывает не более одного увеличения
(после которого становится четным) и не менее одного уменьшенияПо мне, так ключевая мысль. Если рассмотреть последовательности подряд чётных чисел, то получится, что единственное целочисленное решение, при котором ряд закольцовывается, получается при двух чётных подряд и число должно быть 1. При больших числах целых чисел нет - там ряд плавно убывает к нулю. ЧТД.
mayorovp
29.12.2021 23:32+3Ну, "в среднем" гипотезу уже доказали. Вот только хотелось бы "в общем", а не "в среднем"...
kogemrka
29.12.2021 08:44+4Строго говоря, не факт что "простые" пути, в принципе могут существовать.
Пример - последовательность гудстейна.
https://ru.wikipedia.org/wiki/Теорема_Гудстейна
Работает примерно по такому же принципу - берём некое стартовое число, делаем вполне себе алгоритмичную операцию над числом, повторяем до упора. Увы, операция не такая красивая и простая, как в этом примере, но тоже что-то что в две строчки делается на бумаге.
Прикол в том, что доказано, что теорема гудстейна недоказуема в аксиоматике пеано. То есть не получится придумать доказательство по индукции.
Не получается придумать доказательство без оперирования бесконечными множествами.
Возможно доказать только в арифметике второго порядка (а это уже достаточно сложная система для того, чтобы в ней можно было выражать вещественные числа, к примеру).
Но в формулировке последовательности, так же, как и в задаче 3n+1, у нас нет ни вещественных чисел, ни бесконечных множеств, только арифметика - технически, задача выглядит мало чем отличающейся от какой-нибудь арифметической или геометрической прогрессии.
Другой похожий пример - это задача о гидре
https://avva.livejournal.com/244874.html?delayedid=
Ну вот у вас есть схема гидры. Вполне себе такая конечная контрукция. Граф. Можно в структурку на любимом языке программирования записать.
Но вот доказать "простым" образом (например, без привлечения ординалов) не получится в принципе. И невозможность этого - это не какое-то эмпирическое наблюдение, она строго доказана.
masai
28.12.2021 18:38+1Обязательно напишите. Даже если ошиблись, то напишите, где. Изучать ошибки тоже интересно.
Arioch
28.12.2021 20:13+5на любимом Delphi
Точно ли он любимый???
readln(s); num:=strtoint(s); // Исходное число ... writeln(inttostr(num));readln(num); // Исходное число ... writeln(num);
allex
28.12.2021 21:39+11Давным-давно, когда я ещё школьником был, ехал в поезде и коротал время за книжкой с математическими задачками. Большинство из них были достаточно простыми и решались устно. А потом попалась одна с очень простой формулировкой, но решить её никак не получалось. Через какое-то время я сдался и заглянул в ответы в конце книжки. А там было написано, что если вы решили эту задачу, смело требуйте себе докторскую степень, потому что проблему эту ещё никто не смог решить :)
Вот так я и познакомился с задачей "3n+1" :)
mafia8
29.12.2021 00:42+3У кого есть доступ к вычислительным ресурсам и настроение что-то сделать, можно сделать следующее. Эта задача — пусть будет f(3,2). То есть 3n+1, n/2. f(x,y): xn+1, n/y.
Просчитать для разных x и y. И отметить на графике (x,y) точки разного цвета: приходит к 1, уходит в бесконечность, зацикливается.Arioch
29.12.2021 14:56+2Тут вы предполагаете, что f(x,y) будет вести себя одинаково с любым стартовым n.
Но это как раз не доказано даже для f(3,2). Для других тем более, вполне может оказаться функция, ведущая себя очень по разному для разных начальных значений.
dTex
29.12.2021 09:03-6На звание самого крутого математического фокуса не тянет. Ожидал что действительно можно будет угадать число. А тут прогностическая способность уровня - возьмите любое положительное целое число и и отнимайте от него по 1. Как бы вы ни старались оно превратится в 1. Уау, правда?
Только неизвестно сколько раз отнимать.
Число Пи тоже содержит все числа от 0 до 9. Тоже можно поугадывать, если не важно где цифра должна стоять и картинок нарисовать, может даже более красивых. Там даже интересней - а вдруг оно содержит ваш номер телефона, и если да, то кому принадлежат соседние номера. Или если поставить в соответствие числам буквы, можно ли там найти ваше имя и фамилию.
А тут получается, надо "просто" найти второе число, которое зациклит алгоритм.
kogemrka
29.12.2021 09:20+10Ожидал что действительно можно будет угадать число. А тут
прогностическая способность уровня - возьмите любое положительное целое
число и и отнимайте от него по 1. Как бы вы ни старались оно превратится
в 1. Уау, правда?Ну, для того, чтобы доказать, что в вашей задаче число всегда превратиться в единицу нужно секунд 30 и квалификация школьника.
Для того, чтобы доказать, что в задаче 3n+1 число всегда превратиться в единицу пока не хватило 90 лет и квалификации лучших математиков этой планеты.
Хотя, по вашим же словам, сама задача выглядит столь же простой, как и в первом случае.
По-моему, это как минимум любопытно
Число Пи тоже содержит все числа от 0 до 9. Тоже можно поугадывать, если не важно где цифра должна стоять и картинок нарисовать, может даже более красивых. Там даже интересней - а вдруг оно содержит ваш номер телефона, и если да, то кому принадлежат соседние номера. Или если поставить в соответствие числам буквы, можно ли там найти ваше имя и фамилию.
Ну, собственно, да.
Доказать, что какая-то конкретная последовательность не встретится в десятичной записи числа Пи (или доказать, что любая конечная последовательность рано или поздно встретится) - это чертовски интересный результат, который было бы очень интересно рано или поздно увидеть.
Не понимаю вашего сарказма, что не так-то?
michael_v89
30.12.2021 13:06Если число чётное, разделите его на 2. Иначе умножьте его на 3 и прибавьте 1.
(во втором случае можно сразу разделить на 2, так как всегда получается четное число)
Я думал над этой задачей некоторое время, пришел к такому выводу. Если не делить на 2, то прибавлять надо будет не 1, а некоторую степень двойки, которая равна позиции младшей единицы в двоичной записи текущего числа (или что-то вроде того). Тогда получается примерно такая цепочка:
00001xxxxxxx1 0001xxxxxxx10 0001xxxxxx100 001xxxxxx1000Так как запись заданного целого числа конечна, впереди у него будут нули, и потом начальная единица. Надо как-то математически доказать, что нули в конце растут быстрее, и рано или поздно догонят начальную единицу.
Demanoidos
30.12.2021 14:22Delphi для вас не очень любимый, потому что в коде есть лишние вещи. Например, преобразования типов в тех местах, где они нафиг не нужны. Условие неравности, где надо проверять на "больше", лишние writeln, но отсутствие readln в конце для паузы, раз уж вы сделали консольное приложение.
program collatz; {$APPTYPE CONSOLE} var iNum, iSteps, iMax: integer; begin readln(iNum); iSteps := 0; iMax := iNum; while iNum > 1 do begin if Odd(iNum) then iNum := iNum * 3 + 1 else iNum := iNum div 2; if iNum > iMax then iMax := iNum; inc(iSteps); writeln(iNum); end; write('Steps : ', iSteps, #13#10, 'Max : ', iMax); readln; end.
rrrav
30.12.2021 15:51+3Почти век самые мощные умы не нашли доказательства. Насколько я смутно помню, была еще подобная последовательность, которая тоже завела всех в тупик, но в конце концов было найден вариант опровержения (кажется, нашелся цикл).
emaxx
30.12.2021 17:02+2Как в 1960 г. писал математик Сидзуо Какутани:
For about a month everyone at Yale worked on it, with no result. A similar phenomenon happened when I mentioned it at the University of Chicago. A joke was made that this problem was part of a conspiracy to slow down mathematical research in the U.S.
(Примерный перевод: "Каждый в Йельском университете проработал над этой проблемой в течение месяца. Похожий фенонен наблюдался в Чикагском университете после того, как я упомянул о ней. Ходила шутка, что эта задача была частью заговора, имевшего целью затормозить математические исследования в США.".)
Finesse
Видео по этой теме (RU):
RigelNM
И ещё о том же, но под другим углом.
https://youtu.be/s-LHvJTTF04