2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 О последовательности Колатца
Сообщение27.05.2006, 06:05 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Матбой - 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$-ая итерация.

 Профиль  
                  
 
 
Сообщение11.06.2006, 00:09 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение11.06.2006, 05:50 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Доказать, что существует N
Сообщение04.09.2006, 21:01 
Заслуженный участник


01/12/05
458
Несложная задачка, интересно увидеть самое короткое решение:
Определим $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$ раз.

 Профиль  
                  
 
 
Сообщение04.09.2006, 22:21 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Вот тут в точности такая же задача.

 Профиль  
                  
 
 
Сообщение05.09.2006, 09:12 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение05.09.2006, 10:36 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Юстас писал(а):
Там обсуждается задача Колатца

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

 Профиль  
                  
 
 
Сообщение05.09.2006, 10:59 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение05.09.2006, 14:33 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
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$ целое.

 Профиль  
                  
 
 
Сообщение07.09.2006, 11:37 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Руст писал(а):
... 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 курсов тоже имел сомнения, а не слишком ли она проста. Как оказалось - не слишком.

 Профиль  
                  
 
 
Сообщение07.09.2006, 14:48 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group