Может кто поможет...

Задача:
Берется произвольное натуральное число. Если оно четное, оно делится на 2. Если нечетное, умножается на 3 и к результату прибавляется 1. Процесс повторяется. Доказать, что всегда за конечное число шагов получится 1.

Все не так просто как кажется в начале... Или я совсем глупый...

По-моему доказательство задачи сводится к доказательству получения на конечном шаге степени двойки...

Воспользуйся методом математической индукциии...

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

>Все не так просто как кажется в начале... Или я совсем глупый...
Не совсем ;)
Это Collatz problem (из нерешенных задач теории чисел)

так один вечер в пустую это я еще хорошо отделался

Вопрос к хозяину этой темы: задача у Вас решена или еще нет? Я, кажется, решила ее, но не знаю, как здесь набирать ответ. Там всякие символы специальные нужны...

bagira, а ты в пэйнте решение нарисуй! очень интересно посмотреть...

http://directory.google.com/Top/Science/Ma...ollatz_Problem/

Правда, ну как набрать значки суммы, степени и т.д.?

Здесь ведь нет таких возможностей...

bagira, если на то пошло, то сделай в equasion editor и запость файл.

У меня нет такого Едитора....
На работе есть, а дома почему-то не оказалось. Просто не пригождался раньше.
Ладно, завтра на работе наберу этот текст...

може, сканер поблизости есть?
а вообще можно было бы объяснить идею доказательства, может, поймем и так

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

Цитата(bagira @ 2.3.2004, 22:35)

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

Хм... Все очень интересно. Я конечно не хочу сомниваться в вас, но эту задачу уже много лет (как оказалось) весь мир считает нерешаемой.
Вы уверены что ваше доказательство верно?
Если да, то снимаю шляпу. Даже если нет, все равно хотелось бы посмотреть каким образом вы это делали.

YuriT

Свой вариант решения задачи я отправила вчера Podval'у - Вы можете обратиться к нему.

Да, действительно, последний шаг этой задачи (после всех преобразований) я рассмотрела лишь как частный случай. Для общего случая, т.е. строго математически - не получилось...

Зачем спрашивать, если знаете, что задача заведомо нерешаемая? Мы ведь не подозревали подвоха, старались все, как могли...

Задача поиска степени двойки. Как только получается 2^N, то кол-во оставшихся итераций равно N.
Теперь как находим степень двойки:
Может быть можно воспользоваться тем, что:
N*N - (N-1)*(N-1)=2N-1 -разность квадратов соседних чисел всегда нечетна
и тем, что (3N+1)-N =2N+1 -разность чисел найденных с помощью 3N+1 - всегда нечетна, т.е. результат всегда четный:
K=K/2, если K=2N
K=K*3+1, если К=2N+1, причем после этой итерации K всегда будет четным и за этой итерацией всегда будет K/2, значит:
K=(K*3+1)/2, если K=2N+1
А вот дальше...

СУВ.

Цитата(bagira @ 5.3.2004, 23:27)

Зачем спрашивать, если знаете, что задача заведомо нерешаемая? Мы ведь не подозревали подвоха, старались все, как могли...

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

Я сам 2 дня пытался это решить, но сами понимаете, что тщетно.

Вариант, предложенный Багирой.



Присоединённый файл ( Кол-во скачиваний: 43 )
 solution.zip

ДОКАЗАННО!!! Эта задача решается за 100 в среднем шагов и на С++.

Код

int main(int argc, char* argv[]) { srand(time(0)*125); char s[256]; long i=0; long x=(long)rand()*254; while(x!=1){  i++; //  printf("x = %li n = %li\n",x,i); //  scanf(s);  if(x%2!=1)    x/=2;  else {    x*=3;x++;  } } printf("x = %li n = %li",x,i); scanf(s); return 0; }

Поправьте меня если я неправ!

Нужна не программа, а строгое доказательство в общем виде.

Цитата

Erdos commented that "mathematics is not yet ready for such problems" (Lagarias 1985).

Я конечно не претендую на решение данной проблемы. Мы пытались
составить программу, находящую самые вредные такие числа на
http://algolist.manual.ru. Вот к чему пришли

1) Можно не разбирать четные числа (они максимум на 1 сложнее
в два раза меньших)
2) Числа вида 3N+2 можно не рассматривать, так как всегда есть
более вредное число 2N+1:

2N+1 ---> 6N+4 --> 3N+2

3) Самое сложное: Если число нечетное, то

1) Прибавляем к нему 1
2) Раскладываем полученное число на множители
3) Заменяем все двойки на тройки
4) Вычитаем из полученного числа 1
5) Делим на 2
6) Это число получится из исходного после 2N+1 итераций,
где N - число двоек в разложении.

Например - число 7. Прибавляем 1 - 8
Раскладываем - 8=2*2*2
Заменяем - 3*3*3=27
Вычитаем - 27-1=26
Делим - 26/2 = 13
Это число получится из 7 после 2*3+1=7 итераций

Проверка 7-22-11-34-17-52-26-13 :-)

Если интересно, будем копать дальше

Мое почтение!
Вот размышление на тему решения данной задачи
Введем последовательность нечетных чисел след.образом
Chislo[k] = (Chislo[k-1]*3+1)>>j, k>1, j>0(j степень двойки на кот. делится число на к-1 шаге). Или что то же самое
Chislo[k] = (Chislo[k-1]<<1 +(Chislo[k-1]+1))>>j
Причем в силу нечетности Chislo[k] имеет вид 1...0111(1 повторяются к раз).
0 -- 1-ый 0
Chislo[k-1]<<1 =1..01110
Chislo[k-1]+1 =01.s1000(s - нас не интересует что).
Таким образом при сложении 0 точно "перепрыгивает" по крайней мере на 1 позицию вправо(cлева от него единица в каждом слагаемом ),где в последствии и "съедается" сдвигом. Таким образом Chislo[k] <= Chislo[k-1]*2 и последовательность заведомо сходится;
Если нет 0 в числе т.е. Сhislo[k-1] = 1......1...1..1...1, то
п.1 Сhislo[k] = 10...1..1..1..1 (т.е хотябы 1 ноль точно появится -- проверяется непосредственной проверкой, мат. индукцией или как угодно), далее повторяем до тех пор пока не останется 1.
Вот самая банальная часть докозательства --
Осталось
1) Строго показать, что последовательность сходится
2) Проверить п.1
У меня ни сил ни времени (ехал в метро когда решал) не хватило.

Это сообщение отредактировал(а) Sined - 31.8.2004, 18:23

Хочется сказать пару слов о решении Багиры : условие взятое в док-ве слишком жесткое, достаточно чтоб для любого начального значения, исключая 1, существовал элемент последовательности меньший начального, совершенно не обязательно доказывать строгое убывание.

3,14
Возможно, ты прав...
Но, узнав, что задача не решается в принципе, я больше и не бралась за нее
Но вдруг у тебя получится?

Пробовал, ещё до того как эта задача попала на форум, один злобный студент с механико-математического факультета подсунул, не получилось док-во с числами вида 2*j+1, где j-нечётное

Цитата(3)

не получилось док-во с числами вида 2*j+1, где j-нечётное

Вот этот момент можно пояснить?
Очевидно, что 2*j+1 и так нечетно, если j - целое.

Если j - нечётное, а не 2*j + 1

Прочитал решение bagira. Даже упрощенное - оно с ошибками. Комментарии нужны?

Цитата(Peter @ 3.9.2004, 12:41)

Прочитал решение bagira. Даже упрощенное - оно с ошибками. Комментарии нужны?

В чем мои ошибки?

Отправлено по электронной почте.

Peter
А на форум не выложишь???

На склолько я понял, задачка тут уже давно валяется, я как-то посидел - ничего не вышло. Потом ещё посидел, кое-чё выдумал. Когда сформулирую - напишу.

Цитата(EKoshelev @ 6.12.2004, 13:04)

На склолько я понял, задачка тут уже давно валяется

Да этой задаче вообще больше 70 лет возраста

3,14
Но форуму-то, я так понимаю поменьше. Интернету, кстати, тоже.

Прочитай мое сообщение

Ну вот...

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

Рассмотрим все положительные числа. Чётные сразу отпадают, т.к. делятся на два и, следовательно, ни одно из них не является минимальным из этого множества. Остаются нечётные. Т.е. 2n + 1, где n = 0, 1, 2, …
После первой итерации все становятся чётными:
6n + 4. После второй (3n + 2) при чётных n становятся чётными
После третьей получаем (3n + 2)/2. Это всегда (кроме случая, когда n = 0, но тогда 2n + 1 обратится в 1) меньше 2n + 1:
(3n + 2)/2 – 2n + 1 = 3n + 2 – 4n + 2 = –n
Следовательно, для 2n + 1 отпадают все при чётных n, т.к. не могут быть наименьшими из того самого множества.

3n + 2 при нечётных n даёт нечётный результат. То есть, все 2n + 1 через две итерации дают 3n + 2.

В таком случае теперь будем рассматривать 3(2n + 1) + 2 = 6n + 5, где n = 0, 1, 2, … (то есть, вроде как нужно рассматривать 2(2n + 1) + 1, но, по сути, мы это и рассматриваем, только после двух итераций).
После первой итерации все чётные: 18n + 16
После второй 9n + 8. При чётных n эта формула даёт чётный результат, тогда после третьей итерации имеем: (9n + 8)/2. Это всегда меньше 6n + 5.
Следовательно, 6n + 5 при чётных n не является минимальным числом из нашего множества.

9n + 8 при нечётных n даёт нечётный результат. То есть, все 6n + 5 через две итерации дают 9n + 8.

В таком случае рассмотрим 9(2n + 1) + 8 = 18n + 17, где n = 0, 1, 2, …
После первой итерации 54n + 52
После второй – 27n + 26. При чётных n эта формула даёт чётный результат, тогда после третьей итерации имеем: (27n + 26)/2. Это всегда меньше 18n + 17.
Следовательно, 18n + 27 при чётных n не является минимальным числом из нашего множества.

18n + 17 при нечётных n даёт нечётный результат. То есть, все 18n +17 через две итерации дают 27n + 26.

Тогда рассмотрим 27(2n + 1) + 26 = 54n +53, где n = 0, 1, 2, …
После первой итерации 164n + 160. При любом n это число кратно четырём. Тогда после третьей итерации имеем: 41n + 40, а это всегда меньше 54n + 53. Следовательно, ни одно положительное число не является последним числом из множества чисел, которые вследствие выполнения над ними описанных действий устремляются в бесконечность. Если в множестве нет минимальных чисел, значит в нём вообще нифига нет.

Короче, теорема доказана.

Давайте говорите теперь мне где тут ошибка.

Смотри, ты сравниваешь (27n + 26)/2 с 18n + 17, а нужно сравнивать с начальным числом 2 * (2 * (2 * n + 1) + 1) + 1 = 8n + 7, очевидно что исходное число меньше

Цитата(EKoshelev @ 6.12.2004, 15:03)

Остаются нечётные. Т.е. 2n + 1, где n = 0, 1, 2, … После первой итерации все становятся чётными: 6n + 4.

Вот в это не въехал

cardinal
При n = 0, 1, 2, ... 2n + 1 - всегда нечётное число.
Если его умножить на три и прибавить один (первая (по счёту) итерация), то получим:
3(2n + 1) + 1 = 6n + 3 + 1 = 6n +4. Т.к. n - целое, то 6n - всегда чётное (чётное умножить на нечётное равно чётное). Если добавим четыре, то чётным быть оно не перестанет. И так при любом целом n, т.е. после первой итерации все 2n + 1 становятся чётными (6n + 4).

Разжевал как мог.
Добавлено @ 17:07
3,14
Да. Ну я и тормоз... Подумаю, может выкручусь ещё...
Добавлено @ 17:14
3,14
Слушай, я завтра выложу на подобие, только чуть дебильнее доказательство. Там, вроде, всё правильно.

EKoshelev, понял... Это я протормозил

Не а вообще, ты что серьезно нобелевскую получить решил?

cardinal
Да, я посмотрел, чё-то не выходит всё равно. Но в то, что за эту хрень нобелевку дадут, я что-то не очень верю. И вообще, насколько мне известно, ни один математик её ещё не получил.

Это сообщение отредактировал(а) EKoshelev - 7.12.2004, 08:03

Цитата(cardinal @ 6.12.2004, 21:50)

Не а вообще, ты что серьезно нобелевскую получить решил?

В любом случае над задачей подумать интересно

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


3,14, а подумать, на самом деле интересно.

Модератор: Давайте вернёмся к теме обсуждения.

Цитата(EKoshelev @ 6.12.2004, 13:04)

Peter А на форум не выложишь???

Могу.



Это сообщение отредактировал(а) podval - 12.1.2005, 19:54

Присоединённый файл ( Кол-во скачиваний: 1 )
 solution.zip

Почему решение EKoshelev не правильное
Рассмотрим ряд: (1,3,7,24,800,2450,20,2,0,1,0,1,0,0,0....)
По аналогии рассмотрим его первый член - 1 , второй -3 , ... , пятый - 800
Значит ряд постоянно увеличивается и сходится к бесконечности, т.е. не имеет предела
(надеюсь всем понятно , что он сошелся к 0)