О последовательности Колатца

[bot]

Матбой - 2006 (ММФ НГУ)

Для натурального $n$ положим
$T(n)=\frac{n}{2}$ для $n$ чётного и
$T(n)=\frac{3n+1}{2}$ для $n$ нечётного.

Доказать, что для любого конечного набора целых чисел $a_0, a_1, ... , a_k,$ найдётся такое $n$, что
$T^{(i)}(n) \equiv a_i (mod \ 2)$ для $i=0,1,...,k.$

Здесь $T^{(i)} \ - \ i$-ая итерация.

[juna]

Последовательность действительно интересная. Думаю, Вы не обидитесь, если я добавлю дополнительные пояснения непосредственно от Вас: http://www.sciteclibrary.ru/cgi-bin/yabb/YaBB.cgi?board=golovolomki&action=display&num=1085653302&start=0
Интересна связь конечной последовательности нулей и единиц с заданным числом $n$ - может это эффективно решает проблему о ее сложности (см. Арнольда)

[bot]

Раскопали. А я думал, что уже глубоко ушла.
Собссно там и решение есть - оно очень короткое.
Для себя я этот факт открыл давно, но в терминах более короткой разновидности последовательности Колатца (степень двойки на каждом шаге полностью сокращается) и в том контексте по невнимательности не сразу даже признал.
Когда это обнаружил, сильно вдохновился и, видимо как многие, возомнил, что это даёт ключ к положительному решению. Боюсь, что это не даст также ничего ни для отрицательного решения ни для оценки сложности - она явно не проще чем оценка хаотичности взаиморасположения степеней двойки и тройки.
Арнольда ещё не смотрел - текучка заедает.

[Юстас]

Несложная задачка, интересно увидеть самое короткое решение:
Определим $T(n)=\left\{\begin{array}{1} \frac n 2,\ n=0(mod\ 2) \\ \frac{3n+1}{2},\ n=1(mod\ 2) \end{array}$. Пусть $(a_0,\dots, a_k)$ - последовательность из 0 и 1. Доказать, что существует $N:\ T(T(\dots T(n)\dots)=a_i(mod\ 2)\ \forall\ i=0\dots k$, композиция берется $i$ раз.

[juna]

Вот тут в точности такая же задача.

[Юстас]

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

[bot]

Юстас писал(а):

Там обсуждается задача Колатца

Так и задача именно о последовательности Колатца. Факт, конечно, несложный и известен в той или иной форме всем, кто с этой последовательностью повозился достаточное время. Что касается решения, то вряд ли есть короче, чем то, которое можно найти по ссылке, которую там указал Артамонов Ю.Н., впрочем найти его там, возможно, не проще, чем найти решение самостоятельно.
Именно то обсуждение и навело меня на мысль, что задачка-то, пожалуй, пригодна для матбоя.

[Руст]

Решения там не нашёл, но задача слишком тривиальная, так как T(n) линейный оператор, соответственно на множестве остатков по модулю 2^k все степени оператора до к включительно образует невырожденное линейное отображение последовательности длины k из нулей и единиц. Поэтому, для любого вектора существует решение.
В принципе можно представить и решение в явном виде начиная разрешать с конца.

[juna]

bot писал(а):

Отсюда понятно, что меня заинтересовали совершенно естественные цепочки (m - нечётное):

$2^km - 1 -> 2^{k-1}\text{ }3m - 1 -> ... -> 3^km-1=2^s(2^k'm' - 1) -> ...$

Как отсюда возникает вектор х, думаю объяснять не надо. И тривиальность теоремы 1 отсюда тоже прёт – пристроить слева к вектор х, начинающемуся с 1, вектор на (1,0,…) ( k>=0 нулей) не составляет труда: надо просто число n, реализующее этот х, заменить числом z=(2у-1)/3, где $y=2^kn + 2^N$, а $N$ – достаточно большое число с условием, что $z$ целое.

[bot]

Руст писал(а):

... T(n) линейный оператор, соответственно на множестве остатков по модулю 2^k ...

Какая линейность? $T(1)=2, T(2)=1, T(3)=5$

Цитата:

В принципе можно представить и решение в явном виде начиная разрешать с конца

Так и есть. Удлинять двоичную последовательность надо с конца. Пристроить нули спереди нет проблем. Чуть сложнее пристроить единицу с некоторым количеством нулей.
Чуть подробнее скажу, чем в цитате выше.
1) Сначала подъём: вместо $n$ берём $m=n+2^N$, тогда очевидно $T^i(n)\equiv_2 T^i(n)$ для $i=0,1,2, ... , N-1$, то есть возникающая из $m$ двоичная последовательность не будет отличаться от прежней столь долго, сколько пожелаем.
2) Умножив на $2^k, k\ge 0$, получим $m'=2^km$, для которого эта последовательность надстроится $k$ нулями спереди.
3) Достаточно большое $N$ выбираем теперь так, чтобы $2^{k+1}m' - 1$ делилось на $3$.

Согласен, что задача несложная. Цитата перед вами - сам оценивал это как тривиальный факт и когда предлагал её для матбоя, в котором участвовали студенты 1-3 курсов тоже имел сомнения, а не слишком ли она проста. Как оказалось - не слишком.

[Юстас]

Тут проще всего доказывать по индукции, чтобы сделать шаг $n\rightarrow n+1$ нужно положить $N_{n+1}=N_n+t2^n$, и выбрать $t$ так, чтобы получить нужную нам 1 или 0.