| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Математическая задача |
| Автор: YuriT 28.2.2004, 16:46 |
| Может кто поможет... Задача: Берется произвольное натуральное число. Если оно четное, оно делится на 2. Если нечетное, умножается на 3 и к результату прибавляется 1. Процесс повторяется. Доказать, что всегда за конечное число шагов получится 1. Все не так просто как кажется в начале... Или я совсем глупый...  |
| Автор: Kesh 29.2.2004, 13:05 |
| По-моему доказательство задачи сводится к доказательству получения на конечном шаге степени двойки... |
| Автор: val 1.3.2004, 10:28 |
| Воспользуйся методом математической индукциии... |
| Автор: maxim1000 1.3.2004, 12:28 |
| ну вот, один вечер пропал... хорошо еще если бы решил, а то безрезультатно... мат. индукция не получается что-то мне кажется нужно смотреть на двоичное представление чисел... |
| Автор: MBo 1.3.2004, 13:31 |
| >Все не так просто как кажется в начале... Или я совсем глупый... Не совсем ;) Это Collatz problem (из нерешенных задач теории чисел) |
| Автор: maxim1000 1.3.2004, 13:33 |
| так один вечер в пустую это я еще хорошо отделался |
| Автор: bagira 1.3.2004, 17:25 |
| Вопрос к хозяину этой темы: задача у Вас решена или еще нет? Я, кажется, решила ее, но не знаю, как здесь набирать ответ. Там всякие символы специальные нужны... |
| Автор: Kefir 1.3.2004, 20:06 |
| bagira, а ты в пэйнте решение нарисуй! очень интересно посмотреть... http://directory.google.com/Top/Science/Math/Number_Theory/Open_Problems/Collatz_Problem/ |
| Автор: bagira 1.3.2004, 20:29 |
| Правда, ну как набрать значки суммы, степени и т.д.? Здесь ведь нет таких возможностей... |
| Автор: Kefir 1.3.2004, 21:11 |
| bagira, если на то пошло, то сделай в equasion editor и запость файл. |
| Автор: bagira 1.3.2004, 21:31 |
 У меня нет такого Едитора.... На работе есть, а дома почему-то не оказалось. Просто не пригождался раньше. Ладно, завтра на работе наберу этот текст... |
| Автор: maxim1000 2.3.2004, 12:10 |
| може, сканер поблизости есть? а вообще можно было бы объяснить идею доказательства, может, поймем и так |
| Автор: bagira 2.3.2004, 22:35 |
 Простите, сегодня набрать текст не успела. Понимаю, что виновата... Видимо, на самом деле придется в самом ближайшем времени воспользоваться сканером... |
| Автор: YuriT 5.3.2004, 15:35 | ||
Хм... Все очень интересно. Я конечно не хочу сомниваться в вас, но эту задачу уже много лет (как оказалось) весь мир считает нерешаемой. Вы уверены что ваше доказательство верно? Если да, то снимаю шляпу. Даже если нет, все равно хотелось бы посмотреть каким образом вы это делали. |
| Автор: bagira 5.3.2004, 23:27 |
| YuriT Свой вариант решения задачи я отправила вчера Podval'у - Вы можете обратиться к нему. Да, действительно, последний шаг этой задачи (после всех преобразований) я рассмотрела лишь как частный случай. Для общего случая, т.е. строго математически - не получилось... Зачем спрашивать, если знаете, что задача заведомо нерешаемая? Мы ведь не подозревали подвоха, старались все, как могли... |
| Автор: PILOT 6.3.2004, 11:45 |
| Задача поиска степени двойки. Как только получается 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 А вот дальше... СУВ. |
| Автор: YuriT 6.3.2004, 18:15 | ||
Багира, я, конечно, злой, но не на столько. О том, что задача не решается я узнал только после того как в этом топике про это рассказали. После чего покапался по нэту и только убедился в этом. Я сам 2 дня пытался это решить, но сами понимаете, что тщетно. |
| Автор: podval 6.3.2004, 19:28 |
| Вариант, предложенный Багирой. |
| Автор: ExPresident 9.3.2004, 21:09 | ||
ДОКАЗАННО!!! Эта задача решается за 100 в среднем шагов и на С++.
Поправьте меня если я неправ! |
| Автор: podval 9.3.2004, 22:12 |
| Нужна не программа, а строгое доказательство в общем виде. |
| Автор: cardinal 10.3.2004, 13:56 | ||
|
| Автор: Blueboar 30.8.2004, 19:04 |
| Я конечно не претендую на решение данной проблемы. Мы пытались составить программу, находящую самые вредные такие числа на 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 :-) Если интересно, будем копать дальше |
| Автор: Sined 31.8.2004, 10:20 |
| Мое почтение! Вот размышление на тему решения данной задачи Введем последовательность нечетных чисел след.образом 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 У меня ни сил ни времени (ехал в метро когда решал) не хватило. |
| Автор: 3,14 31.8.2004, 16:00 |
| Хочется сказать пару слов о решении Багиры : условие взятое в док-ве слишком жесткое, достаточно чтоб для любого начального значения, исключая 1, существовал элемент последовательности меньший начального, совершенно не обязательно доказывать строгое убывание. |
| Автор: bagira 1.9.2004, 19:35 |
| 3,14 Возможно, ты прав... Но, узнав, что задача не решается в принципе, я больше и не бралась за нее  Но вдруг у тебя получится? |
| Автор: 3,14 2.9.2004, 07:10 |
| Пробовал, ещё до того как эта задача попала на форум, один злобный студент с механико-математического факультета подсунул, не получилось док-во с числами вида 2*j+1, где j-нечётное |
| Автор: podval 2.9.2004, 18:28 | ||
Вот этот момент можно пояснить? Очевидно, что 2*j+1 и так нечетно, если j - целое. |
| Автор: 3,14 2.9.2004, 18:31 |
| Если j - нечётное, а не 2*j + 1 |
| Автор: Peter 3.9.2004, 12:41 |
| Прочитал решение bagira. Даже упрощенное - оно с ошибками. Комментарии нужны? |
| Автор: bagira 21.9.2004, 21:27 | ||
В чем мои ошибки? |
| Автор: Peter 6.12.2004, 11:45 |
| Отправлено по электронной почте. |
| Автор: EKoshelev 6.12.2004, 13:04 |
| Peter А на форум не выложишь??? На склолько я понял, задачка тут уже давно валяется, я как-то посидел - ничего не вышло. Потом ещё посидел, кое-чё выдумал. Когда сформулирую - напишу. |
| Автор: 3,14 6.12.2004, 13:59 | ||
Да этой задаче вообще больше 70 лет возраста |
| Автор: EKoshelev 6.12.2004, 16:00 |
| 3,14 Но форуму-то, я так понимаю поменьше. Интернету, кстати, тоже. |
| Автор: cardinal 6.12.2004, 16:02 |
| Прочитай мое сообщение |
| Автор: EKoshelev 6.12.2004, 16:03 |
| Ну вот... Предположим, что на числовой оси существует некое не нулевое множество чисел, которые в результате таких операций устремляются в бесконечность. Попытаемся найти самое маленькое число из этого множества. Рассмотрим все положительные числа. Чётные сразу отпадают, т.к. делятся на два и, следовательно, ни одно из них не является минимальным из этого множества. Остаются нечётные. Т.е. 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. Следовательно, ни одно положительное число не является последним числом из множества чисел, которые вследствие выполнения над ними описанных действий устремляются в бесконечность. Если в множестве нет минимальных чисел, значит в нём вообще нифига нет. Короче, теорема доказана. Давайте говорите теперь мне где тут ошибка. |
| Автор: 3,14 6.12.2004, 16:19 |
| Смотри, ты сравниваешь (27n + 26)/2 с 18n + 17, а нужно сравнивать с начальным числом 2 * (2 * (2 * n + 1) + 1) + 1 = 8n + 7, очевидно что исходное число меньше |
| Автор: cardinal 6.12.2004, 16:27 | ||
Вот в это не въехал  |
| Автор: EKoshelev 6.12.2004, 17:04 |
| 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 Слушай, я завтра выложу на подобие, только чуть дебильнее доказательство. Там, вроде, всё правильно. |
| Автор: cardinal 6.12.2004, 21:50 |
| EKoshelev, понял... Это я протормозил Не а вообще, ты что серьезно нобелевскую получить решил? |
| Автор: EKoshelev 7.12.2004, 08:02 |
| cardinal Да, я посмотрел, чё-то не выходит всё равно. Но в то, что за эту хрень нобелевку дадут, я что-то не очень верю. И вообще, насколько мне известно, ни один математик её ещё не получил. |
| Автор: 3,14 7.12.2004, 09:30 | ||
В любом случае над задачей подумать интересно  |
| Автор: EKoshelev 7.12.2004, 14:25 |
| Вообще, идейка ещё одна появилась. На основе того, что уже излагал. Там всё упирается в выведение хитрой закономерности, на основе которой нужно будет составить числовой ряд и доказать, что он стремится к 1 с бесконечным количеством членов. Правда и здесь можно будет на грабли наступить... 3,14, а подумать, на самом деле интересно. |
| Автор: podval 8.12.2004, 17:37 |
| Модератор: Давайте вернёмся к теме обсуждения. |
| Автор: Peter 17.12.2004, 13:36 | ||
Могу. |
| Автор: ovr2000 20.12.2004, 12:45 |
| Почему решение EKoshelev не правильное Рассмотрим ряд: (1,3,7,24,800,2450,20,2,0,1,0,1,0,0,0....) По аналогии рассмотрим его первый член - 1 , второй -3 , ... , пятый - 800 Значит ряд постоянно увеличивается и сходится к бесконечности, т.е. не имеет предела (надеюсь всем понятно , что он сошелся к 0) |