موضوع مقاله: حدس کولاتز | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # حدس کولاتز | مقدمه: حدس کولاتز (Collatz Conjecture)، حدسی در ریاضیات است که مربوط به دنباله‌ها بوده و به این صورت مطرح می‌گردد: از هر عدد طبیعی دلخواهی چون n شروع کنید، سپس هر جمله از جمله بعدی دنباله به این صورت بدست می‌آید: اگر جمله قبلی زوج بود، جمله بعدی نصف قبلی خواهد بود. | ## بخش 1: حدس کولاتز | این حدس می‌گوید: مهم نیست که مقدار n چه باشد، در نهایت این دنباله همیشه به ۱ ختم خواهد شد. این حدس را به نام لوتار کولاتز نامگذاری کرده‌اند که اولین بار ایده آن را در ۱۹۳۷ میلادی، دو سال پس از دریافت مدرک دکترایش معرفی نمود. همچنین این مسئله را به نام‌های زیر نیز می‌شناسند: مسئله ، حدس ، حدس اولام (به یاد استنی‌سواف اولام)، مسئله کاکوتانی (به یاد شیزو کاکوتانی)، حدس توایتس (به یاد برایان توایتس)، الگوریتم هاسه (به یاد هلموت هاسه) یا مسئله سیراکوس. دنباله اعداد ظاهر شده در این حدس را برخی مواقع دنباله تگرگی یا اعداد تگرگی (به این دلیل که مقادیرش اغلب همچون تگرگ درون یک ابر، چندین نزول و صعود دارند) یا اعداد شگرف می‌نامند. پاول اردوش در مورد حدس کولاتز گفت: «ممکن است ریاضیات برای چنین مسائلی هنوز آمادگی نداشته باشد.» همچنین او جایزه ۵۰۰ دلاری را برای جواب آن اعلام نمود. جفری لاگاریاس در ۲۰۱۰ بیان نمود که حدس کولاتز «مسئله‌ای است که دشواری عجیباً زیادی داشته و کاملاً از دسترس ریاضیات کنونی خارج است.» بیان مشکل عملیات زیر را در مجموعه اعداد صحیح مثبت اختیاری در نظر بگیرید اگر عدد زوج بود، آن را بر ۲ تقسیم کن. برای مثال، اگر عملیات روی ۳ انجام شود، نتیجه ۱۰ است و اگر روی ۲۴ اجرا شود نتیجه ۱۲ است. اگر بخواهیم این عملیات را به صورت تابعی ریاضی نشان دهیم به صورت زیر خواهد بود: هم‌اکنون با اجرا کردن این عملیات بر روی یک دنباله از اعداد به‌طور متوالی با هر عدد صحیح مثبت، و گرفتن نتیجه به عنوان ورودی مرحله بعد: در حالی که: حدس کولاتز به صورت زیر است: این روند به صورت اتفاقی به عدد ۱ می‌رسد، صرف نظر از این که چه عددی به عنوان عدد اولیه انتخاب شده. اگر به ازای یک N خاص، عدد i به صورت بیان شده وجود نداشته باشد می‌گوییم N یک زمان کلی ایست نامحدود دارد و حدس غلط است. اگر حدس غلط باشد می‌تواند فقط به این دلیل باشد که یک عدد شروعی وجود دارد که به دنباله خاتمه‌ای می‌دهد که ۱ شامل آن دنباله نیست. یک چنین دنباله‌ای ممکن است وارد چرخه‌ای شود که از ۱ مستثنی باشد یا این که بدون محدودیت ادامه یابد. اثبات استدلال هرچند که این حدس هنوز اثبات نشده است، ولی اکثر ریاضیدانان که این مشکل را بررسی کرده‌اند، خود به خود اعتقاد دارند که این حدس درست است. در این قسمت دو دلیل برای این انتظار درستی بیان می‌کنیم: این حدس توسط رایانه برای تمام صحیح مثبت تا ۱۰ × ۲۵۸ ≈ ۲٫۸۸ امتحان شده است. با تعجب باید گفته شود که این گونه مقید کردن‌ها توسط رایانه ارزش مدرکی بسیار محدودی دارند. (مانند حدس پولیا، حدس مرتن یا عدد اسکیوویز) همچنین این موضوع که، {۴٬۲٬۱} تنها چرخه با دورهٔ کمتر از ۳۵۴۰۰ است، روشن شده است. مدارک احتمالی اگر کسی تنها اعداد فرد تولید شده در دنبالهٔ کولاتز را در نظر بگیرد، آنگاه کسی می‌تواند استدلال کند که در حالت میانگین (در حالت خاص میانگین هندسی قسمتها) عدد فرد بعدی باید ¾قبلی باشد، که اظهار می‌کند این دسته اعداد باید با ترتیبی طولانی کاهش یابند. (اگرچه این مدرکی علیه چرخه‌ها نیست، فقط علیه واگرایی است) دیدگاه‌های دیگر دربارهٔ موضوع در حالت معکوس دیدگاه دیگری برای اثبات این حدس به کار می‌رود، که روش رشد از بالا به پایین را در نظر می‌گیرد که گراف کولاتز نام دارد. گراف کولاتز گرافی است که با رابطهٔ معکوس زیر تعریف می‌شود: بنابراین به جای این که ثابت کنیم همهٔ اعداد طبیعی به‌طور اتفاقی به ۱ می‌رسند، می‌توانیم ثابت کنیم که ۱ به تمام اعداد طبیعی سوق داده می‌شود. برای تمام اعداد صحیح همچنین، رابطهٔ معکوس، به جز حلقهٔ ۱و۲و۴، یک درخت است(وارون حلقه ۱و۴و۲ یک تابع بدون تغییر است که در عبارت مشکل بالا مطرح شده است). | ## بخش 2: حدس کولاتز | وقتی رابطهٔ ۳n+۱ در تابع (f(n، با جانشینی رایج «میان بر» با رابطهٔ ۳n + ۱)/۲) جابه‌جا شود(بهینه‌سازی زیر را ببینید)، گراف کولاتز با رابطهٔ وارون زیر تعریف می‌شود: این رابطهٔ معکوس، به جز حلقهٔ ۱–۲، به شکل یک درخت در می‌آید (معکوس حلقهٔ ۱–۲در تابع (f(n، همان‌طور که نشان داده شد، در بالا بازبینی شده است) به عنوان اعداد گویا اعداد طبیعی می‌توانند با به‌کارگیری روشی مشخص، به اعداد گویا تبدیل شوند. براای به دست آوردن مدل گویا، بزرگ‌ترین عدد توان ۲ که کمتر مساوی عدد اصلی است پیدا کنیدو آن را به عنوان مخرج در نظر بگیرید. برای به دست آوردن مدل طبیعی عدد صورت و مخرج کسر را با هم جمع کنید (۵۱۱→ ۲۵۵/۲۵۶). تابع کولاتز به صورت زیر تغییر می‌کند: (n=صورت،d=مخزج) این روش کار می‌کند زیرا ۳x + ۱ = ۳(d + n) + ۱ = (۲d) + (۳n + d + ۱) = (۴d) + 3n - d+۱. کاهش یک عدد گویا قبل از هرگونه عملیات باید صورت گیرد تا بتوانx را فرد دریافت کرد. به عنوان یک ماشین انتزاعی استفادهٔ مکرر از تابع کولاتز را می‌توان به عنوان یک ماشین انتزاعی که با رشته‌هایی از بیت‌ها سرو کار دارد، بیان کرد. ماشین دو قدم زیر را تا زمانی که فقط ۱ باقی بماند روی هر عدد فردی انجام می‌دهد: ۱. که برابر مبنای دو در محاسبات است راه دیگر امتحان حدس ۳n+۱ اقدام از طریق اعداد در مبنای دو است. مثال آن به صورت زیر است: مثال:ما از عدد ۷ استفاده می‌کنیم پس در مبنای دو به صورت ۱۱۱ است: راه استفاده شده برای بازگو کردن هر عدد در مبنای دو به صورتی است که ابتدا عدد اولیه را می‌نویسیم سپس زیر آن همان عدد را با یک "۱" اضافه شده به انتهای سمت راست آن می‌نویسیم و دو عدد را جمع می‌کنیم. هر صفری که در انتهای راست حاصل جمع ظاهر شد حذف می‌کنیم و این روند را تا جایی ادامه می‌دهیم که به عدد ۱ برسیم. استفاده از این شکل (f(n می‌تواند نشان دهد که دنبالهٔ زوجیت برای دو عدد m,n در k دورهٔ اول مساوی است اگر و تنها اگر m,n به پیمانهٔ k۲برابر باشند. این موضوع به این اشاره دارد که هر عدد به‌طور خاص با دنبالهٔ زوجیت خود شناخته می‌شود و علاوه بر این اگر حلقه‌های کولاتز متعددی وجود داشت، حلقهٔ زوجیت متناظر با آن‌ها نیز باید متفاوت باشد. اثبات این موضوع بسیار ساده است، می‌توان به صورت شهودی و بسیار ساده مشاهده کرد که اعمال f تابع ،k بار بر عددa 2k+b عدد a 3c+d را نتیجه خواهد داد، که d نتیجهٔ اعمال f تابع ،k بار بر عدد b است و c عددی است که نشان می‌دهد چه تعداد عدد فرد در طی این دنباله به دست آمده است بنابراین زوجیت k عدد اول به کلی با b معین می‌شود و زوجیت عدد k+۱ام، اگر آخرین عدد پرمعنیa تغییر کند، تغییر خواهد کرد. حدس کولاتز را می‌توان به این صورت بیان کرد که، زوجیت دنبالهٔ کولاتز برای هر عدد نهایتاً وارد حلقهٔ ۰ → ۱ → ۰ می‌شود. مانند یک سیستم برچسب برای تابع کولاتز به فرم: دنباله‌های کولاتز توسط سیستم بسیار ساده ۲-برچسبی که قانون حاصل جمع آن به صورت زیر است محاسبه می‌شوند: و به صورتی که عدد صحیح مثبت n یک رشتهٔ nتایی از aها بیان شده است، با بیان این موضوع که عملیات برچسب روی هر کلمه‌ای که طولش از ۲ کمتر است می‌ایستد. حدس کولاتز را می‌توان به این صورت بیان کرد که، این سیستم برچسب گذاری، با یک رشتهٔ دلخواه کراندار از aها به عنوان عدد اولیه، در پایان می‌ایستد. بسط در دامنه‌های بزرگتر تکرار روی تمام اعداد صحیح: برای هر عدد صحیح، نه فقط اعداد صحیح مثبت، ما آن را روی (f(n می‌نگاریم که: *اگر n زوج f(n) = ۳n + ۱; *اگر n فرد f(n) = n/۲. به‌طور جالب توجه مشاهده می‌شود که در این حالت تنها پنج حلقه داریم، که به نظر می‌رسد که تمام اعداد نهایتاً مشمول این تکرار می‌شوند. برای ذخیره گامها، ما فقط اعداد فرد را در حلقه یادداشت می‌کنیم (به جز حلقه کوچک {۰ . | ## بخش 3: حدس کولاتز | هر عدد فرد n، وقتی تابع f مکرراً اعمال می‌شود به عدد فرد بعدی خواهد رسید در: (بزرگ‌ترین عدد توان دو که۳n+۱ را عاد می‌کند)/۳n+۱ هر حلقه با اولین عضو کمترین مقدار مطلقش فهرست شده. ما هر حلقه را با اندازهٔ حلقهٔ کامل دنبال می‌کنیم (داخل پرانتز):شمارهٔ اعضا، زوج یا فرد، به حلقه متعلق است که بدون تکرار محاسبه شده است. تکرار روی اعداد گویا با مخرج زوج: نگاشت استاندارد کولاتز را می‌توان به اعداد گویا بسط داد (چه منفی چه مثبت) که مخرج فرد دارند، زمانی که در ساده‌ترین حالت نوشته می‌شوند. دنباله‌های زوجیت همان‌طور که در بالا تعریف شد دیگر برای کسرها منحصربه‌فرد نیستند، هر چند می‌توان نشان داد هر حلقهٔ زوجیت ممکن یک دنبالهٔ زوجیت برای دقیقاً یک کسر است:اگر یک حلقه دارای طول n و شامل اعداد فرد دقیقاً m تا به صورتk۰, …, km-1، آنگاه کسر منحصربه‌فرد که حلقهٔ زوجیت را به وجود می‌آورد برابر: . برای مثال، حلقهٔ زوجیت (۱ ۰ ۱ ۱ ۰ ۰ ۱) دارای طول ۷ و ۴ عدد فرد به صورت ۰٬۲٬۳ است و کسر منحصربه‌فرد که حلقهٔ زوجیت را تولید می‌کند برابر: . حلقهٔ کامل موجود به صورت: ۱۵۱/۴۷ → ۸۵/۴۷ → ۱۷۰/۴۷ → ۳۴۰/۴۷ → ۲۱۱/۴۷ → ۱۲۵/۴۷ → ۲۵۰/۴۷ → ۱۵۱/۴۷ هرچند جایگشت‌های تناوبی دنباله‌های زوجیت اصلی کسرهایی منحصربه‌فرد هستند ولی حلقه منحصربه‌فرد نیست. هر کسر جایگشت برابر عدد بعدی در دور حلقه است: (۰ ۱ ۱ ۰ ۰ ۱ ۱) → (۱ ۱ ۰ ۰ ۱ ۱ ۰) → (۱ ۰ ۰ ۱ ۱ ۰ ۱) → (۰ ۰ ۱ ۱ ۰ ۱ ۱) → (۰ ۱ ۱ ۰ ۱ ۱ ۰) → (۱ ۱ ۰ ۱ ۱ ۰ ۰) → همچنین برای منحصربه‌فردی، دنباله‌های زوجیت باید «اول» باشد. برای مثال، دنباله‌های زوجیت (۱ ۱ ۰ ۰ ۱ ۱ ۰ ۰) می‌تواند به دو زیر دنبالهٔ یکسان(۱ ۱ ۰ ۰ ۱ ۱ ۰ ۰) تقسیم شود. محاسبهٔ کسر ۸-عاملی این دنباله نشان می‌دهد: (۱ ۱ ۰ ۰ ۱ ۱ ۰ ۰) → ولی وقتی کسر را ساده کنیم {۵/۷} مانند همان زیر دنبالهٔ ۴-عاملی است: (۱ ۱ ۰ ۰) → و این به این دلیل است که دنبالهٔ زوجیت ۸-عاملی در واقع دو حلقه از دور حلقه‌ای تعریف شده توسط زیر دنبالهٔ ۴-عاملی است. در این زمینه، حدس کولاتز برابر با این است که بگوییم(۰٬۱) تنها حلقه‌ای است که تمام اعداد مثبت ایجاد می‌شود. اگر نگاشت استاندارد کولاتزی که در بالا تعریف شده توسط جایگزینی “۳n+۱”با “۳n+۱)/۲)”بهینه شده باشد، این موضوع می‌تواند نشان داده شود که یک محدودیت برای اعداد حقیقی یا اعداد مختلط است: ، پس از ساده‌سازی: . تکرار نگاشت بهینه‌سازی شدهٔ فوق در صفحهٔ اعداد مختلط فراکتال کولاتز را ایجاد می‌کند. بهینه سازیها در قسمت «زوجیت» راهی برای سرعت بخشیدن به شبیه‌سازی دنباله ارائه شد. برای جلو افتادن k قدم در هر تکرار (با استفاده از تابع f در همان قسمت)، عدد فعلی را به دو قسمت تقسیم می‌کنیم،b(kتا کم ارزشترین رقم‌ها)، و a (بقیه رقم‌های عدد). برای مثال اگر ،k=۵ باشد، می‌توان ۵ قدم در هر تکرار توسط جدا کردن ۵ تا از کم ارزشترین رقم‌ها به جلو پرید و استفاده از: c [۰...۳۱] = {۰٬۳٬۲٬۲٬۲٬۲٬۲٬۴٬۱٬۴٬۱٬۳٬۲٬۲٬۳٬۴٬۱٬۲٬۳٬۳٬۱٬۱٬۳٬۳٬۲٬۳٬۲٬۴٬۳٬۳٬۴٬۵} d [۰...۳۱] = {۰٬۲٬۱٬۱٬۲٬۲٬۲٬۲۰٬۱٬۲۶٬۱٬۱۰٬۴٬۴٬۱۳٬۴۰٬۲٬۵٬۱۷٬۱۷٬۲٬۲٬۲۰٬۲۰٬۸٬۲۲٬۸٬۷۱٬۲۶٬۲۶٬۸۰٬۲۴۲} تابع سیراکوس اگر k یک عدد فرد باشد، آنگاه ۳k+۱ زوج است، پس می‌توانیم بنویسیم ۳k + ۱ = ۲ak′، K یک عدد فرد و a ≥ ۱ است. ما تابع f را از روی مجموعهٔ Iاز اعداد فرد به روی خودش تعریف می‌کنیم، که تابع سیراکوس نام دارد، با فرض این که f (k) = k′ برخی از خواص تابع سیراکوس: برای تمام kها درI f (4k + ۱) = f (k) برای تمام p ≥ ۲ و hهای فرد،f p - ۱(۲ p h - ۱) = ۲ ۳ p - 1h – ۱ برای تمام hهای فرد،f (2h - ۱) ≤ (۳h - ۱)/۲ حدس سیراکوس این است که برای تمام kها در I، وجود دارد عدد صحیح n ≥ ۱ به صورتی کهf n(k) = ۱. به‌طور هم ارز، فرض می‌کنیم E مجموعه اعداد فرد k باشد که عدد صحیح n ≥ ۱ وجود دارد به صورتی کهf n(k) = ۱باشد. در ادامه تلاشی را برای اثبات از طریق استقرا آغاز می‌کنیم: می‌دانیم ۱و۳و۵و۷و۹ در E وجود دارند. فرض می‌کنیم که k-۲ و تمام اعداد فرد قبل از آن در E هستند و اثبات می‌کنیم که kدر E است. | ## جمع‌بندی | در اینجا اگر سعی کنیم که نشان دهیم که برای هر عدد صحیح فرد′k، ۱ ≤k′≤ k-۲ ; ۳k′ ∈ E کار تمام است.