از گره هاي نگشوده رياضيات: كُللاتس - پرُبلم يا 3n+1 پرُبلم

[خروش]

خدا عدد هاي طبيعي را به ما داد، چيزهاي ديگر همگي ساخته آدميست.
Leopold Kronecker



از گره هاي نگشوده رياضيات: كُللاتس - پرُبلم يا 3n+1 پرُبلم

اين پرُبلم را نخستين بار رياضيدان آلماني (Lothar Collatz (06.07.1910-26.09.1990 در سال 1937 به آگاهي همه رساند.

با عدد طبيعي n آغاز ميكنيم، اگر n جفت (زوج) بود، آنرا به 2 بخش مي كنيم، و اگر تك (فرد) بود، عدد يك را به 3 برابر آن مي افزاييم، و اين روش را چندبار انجام مي دهيم تا سرانجام به عدد هاي 4 و 2 و 1 برسيم.



گمان:سرانجام هر عدد طبيعي n ، پس از گام هاي( كه بي پاپان نيست)، 1 مي باشد.

تاكنون نه درستي اين گمان نشان داده شده و نه نادرستي آن.
جهان چشم براه شماست. بهرروي يك پاداشت جداگانه پيش خروش است،

[rrkh]

مي گم اين يكي كه ديگه اثبات نشده كه غيرقابل حله؟ها

[خروش]

درسته، همينطوره،
نه درستي آن ثابت شد و نه نادرستي آن.
براي اثبات نادرستي آن يك نمونه بسنده است و
براي درستي آن ...

با سپاس
خروش

[rrkh]

سلام

چرا 3n+1؟؟؟؟

n+1 یا n-1 هم جواب میده.
نه؟؟


ممنون.............رضا

[خروش]

سلام

چرا 3n+1؟؟؟؟

n+1 یا n-1 هم جواب میده.
نه؟؟


ممنون.............رضا

آري اما نشان دادن آنها بايد آسان باشد. ( آسان به نظر مي رسد.)

[rrkh]

سلام

من نمی دونم باید از چه راهی برم ولی اگر n+1 اثبات بشود،خود به خود گره ی ما گشوده می شود.
چون 3n زیر مجموعه ای از n است.

ممنون.......رضا

[rrkh]

ایده ی جالبی دادم . نه؟

[asmann]

با سلام
اثبات براي n+1 ساده است، ولي من فكر ميكنم كمكي به حل اون مسئله نميكنه.

اثبات:
هر دو مرحله متوالي را كه در نظر بگيريم، از اين سه حالت خارج نيست:
1- در مرحله اول، به عدد يك واحد اضافه كرده، و مرحله بعد حاصل را نصف كرده ايم. يعني اگر قبل از انجام اين دو مرحله عددمان برابر با n بوده باشد، پس از اين دو مرحله عدد حاصل برابر خواهد بود با 2/(n+1)
2- در مرحله اول، عدد را نصف كرده، و مرحله بعد به حاصل يك واحد اضافه كرده ايم. يعني اگر قبل از انجام اين دو مرحله عددمان برابر با n بوده باشد، پس از اين دو مرحله عدد حاصل برابر خواهد بود با n/2 + 1
3- هم در مرحله اول و هم در مرحله دوم عدد را نصف كرده ايم. يعني اگر قبل از انجام اين دو مرحله عددمان برابر با n بوده باشد، پس از اين دو مرحله عدد حاصل برابر خواهد بود با n/4

براي هر n>1 ، عدد 2/(n+1) از عدد n كوچكتر است
براي هر n>2 ، عدد n/2 + 1 از عدد n كوچكتر است
براي هر n ، عدد n/4 از عدد n كوچكتر است

ميبينيم كه براي هر دو مرحله متوالي، عدد در حال كوچكتر شدن است. واضح است كه هيچ كدام از اين مراحل نميتوانند از يك عدد طبيعي، يك عدد غير طبيعي بسازند. در نتيجه پس از تعداد متناهي مرحله، به عدد 1 ميرسيم.

[rrkh]

سلام دوست عزیز

خوب اگه اینجوری باشه مسئله حل هست!

ما می گیم که به ازای تمامی اعداد(n) این شرط صدق می کنه.
پس به ازای اعداد مضرب 3 هم صدق می کنه.

یعنی این دنباله توی اعداد طبیعی(N) درسته است.
اعداد طبیعی مضرب 3 هم که زیر مجموعه ای از اعداد طبیعی (N) هستند.
پس توی اعداد طبیعی مضرب 3 هم درسته.

پس سوال حل شد.


خروش جواب رو به کودوم سازمان بدیم.

[asmann]

با سلام
به نظر من اين حرف شما درست نيست.
تفاوت اين دو مسئله در اعداد ورودي نيست(در هر دو مسئله، عدد ورودي ميتواند هر عدد طبيعي باشد) بلكه تفاوت در الگوريتمهاي اين دو مسئله است.
الان چيزي كه ما ثابت كرديم، اين بوده كه براي هر عدد طبيعي، پس انجام فلان الگوريتم، فلان نتيجه حاصل ميشود، و اين ربطي به الگوريتم داده شده در مسئله اوليه ندارد.

[rrkh]

[rrkh]

ببین عزیز!

شما قبول داری که برای تمام اعداد طبیعی این حکم را ثابت کردید یه نه؟

[doost]

به نظر من اشکالی دراستدلال اسمان نیست به هرحال این اعمال یه دنباله نزولی رو ایجاد میکنه وچون مجموعه اعداد طبیعی خوش ترتیب است در نهایت هردو دنباله ها به یک میرسند فکر کنم یه قضیه محکمی برای این دنباله نزولی دراعداد طبیعی داشته باشیم اگه لازمه قول میدم بعدا براتون بنویسم

[asmann]

با سلام
به نظر شما ميشه براي اثبات مسئله اصلي(كه جناب خروش قرار دادند) هم از اين استراتژي استفاده كرد؟ چون اگه بشه نشون داد كه بعد از هر m مرحله متوالي، الزاما حاصل كوچك خواهد شد، مثل دفعه قبل ميشه نتيجه گرفت كه بعد از تعداد متناهي مرحله، به عدد 1 ميرسيم.

[doost]

اصل نزول نامتناهی:
هیچ دنباله اکیدا نزولی از اعداد طبیعی وجود ندارد
یک دنباله نزولی اگه اکیدا نزولی نباشه از یه جایی به بعد باید ثابت باشه نتیجه دیگه اینه که هیچ دنباله نامتناهی نزولی از اعداد طبیعی وجود نداره
ابنجا چون مشخص میشه با این اعمال یک دنباله نزولی ساخته شده ومجموعه اعداد طبیعی خوش ترتیب است یعنی دارای کوچکترین عضو به نام یک است بنابراین دنباله مجبوره به یک همگرا بشه
حالا با یک روش مقبول مثل استقرا باید ثابت کرد گزاره برای هر عددی صحیح است یعنی فرض میکنیم برای یک درست باشد واگر برای k درست بود برای k+1 هم درست است در واقع اگه بشه بین عدد وتعداد مراحل رسیدن به یک ارتباطی برقرار کرد ..........