موضوع مقاله: مسئله پایان خوش | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله پایان خوش | مقدمه: مسئلهٔ پایان خوش (که توسط پل اردیش نامگذاری شده‌است، چرا که به ازدواج جورج سیکریس و استر کلاین منجر شد) گزارهٔ ذیل است: قضیه. | ## بخش 1: مسئله پایان خوش | هر مجموعهٔ پنج تایی از نقاط در صفحه که دارای موقعیت عمومیدر این متن، موقعیت عمومی به این معناست که هیچ سه نقطه‌ای روی یک خط نیستند و هیچ دو نقطه‌ای روی هم قرار ندارند. هستند، یک زیرمجموعهٔ متشکل از چهار نقطه دارد که این نقاط رأس‌های یک چهار ضلعی محدب را تشکیل می‌دهند. قضیهٔ پایان خوش، با تحلیل یک حالت ساده اثبات می‌شود: اگر چهار یا تعداد بیش‌تری نقطه، رأس‌های یک بدنهٔ محدب باشند، هر چهار نقطه‌ای به این شکل می‌توانند انتخاب شوند. از طرفی دیگر، اگر مجموعهٔ نقاط به فرم یک مثلث با دو نقطه درون آن باشند، دو نقطهٔ درونی و یکی از اضلاع مثلث می‌توانند انتخاب شوند. برای توضیح مصور این اثبات، پترسون (۲۰۰۰) را ببینید و برای بررسی دقیق‌تر این مسئله نسبت به آنچه اینجا ارائه شده‌است، موریس و سالتن (۲۰۰۰) را ببینید. تخمین اردوش-سیکریس رابطهٔ کلی بین تعداد نقاطی که در یک مجموعهٔ نقاط با موقعیت عمومی هستند و بزرگ‌ترین چندضلعی محدب آن را به‌طور دقیق بیان می‌کند. دو دانشمند به نام‌های اردوش و سیکریس این قضیه را به صورت زیر تعمیم داده‌اند: قضیه. | ## بخش 2: مسئله پایان خوش | برای هر عدد صحیح مثبت N، هر مجموعهٔ بزرگ ناتهی و کافی از نقاط در صفحه که هیچ سه تایی از آن‌ها روی یک خط نباشند و هیچ دوتایی از آن‌ها روی هم نباشند (موقعیت عمومی)، شامل یک زیرمجموعه از N نقطه است که رئوس چندضلعی محدب را تشکیل می‌دهند. اثبات قضیه اردیش–ژکرس در مقاله‌ای که قضیهٔ زیردنباله‌های یکنواخت در دنباله‌های عددی را اثبات می‌کند آمده است. فرض کنید (f(N کمترین مقدار M را نشان دهد که برای هر مجموعه از M نقطه در موقعیت عمومی یک Nضلعی محدب وجود داشته باشد. مجموعه‌ای از هشت نقطه که پنج ضلعی محدب ندارند در شکل نشان داده شده‌است، که نشان می‌دهد f(5)> ۸ است. قسمت دشوارتر اثبات این است که نشان دهیم هر مجموعه از ۹ نقطه در وضعیت معمولی دارای رئوس یک پنج‌ضلعی محدب است. f(۶) = ۱۷.این مسئله توسط (Erdos – Peters(2006 اثبات شده است، آن‌ها یک برنامهٔ کامپیوتری طراحی کردند که تمام حالاتی که برای 17 نقطه شش‌ضلعی محدب خالی وجود نداشت را حذف کند، البته تعداد حالات معدودی از شکل‌ها را بررسی کردند. مقدار f برای اعداد بیشتر از ۶ نامعلوم است، اما با توجه به نتیجهٔ مقالهٔ اردوش-سیکریس (۱۹۳۵) می‌دانیم مقدار متناهی دارد. | ## بخش 3: مسئله پایان خوش | چندضلعی‌های خالی ممکن است سؤال پیش بیاید که آیا برای هر مجموعهٔ کافی از نقاط در موقعیت عمومی دارای یک چهارضلعی، پنج‌ضلعی و.. راه حل اصلی مسئلهٔ پایان خوش را می‌توان طوری تطابق داد که نشان دهد به ازای هر پنج نقطه با وضعیت موقعیت عمومی در صفحه یک چهارضلعی محدب خالی وجود دارد، همان‌طور که در تصویر نشان داده شده، و به ازای هر ده نقطه با شرایط فوق یک پنج‌ضلعی محدب خالی وجود دارد.(Harborth(1978 اگرچه مجموعه‌های بزرگ و دلخواهی از نقاط با موقعیت عمومی ممکن است وجود داشته باشند که هیچ هفت‌ضلعی خالی برای آن‌ها یافت نشود.(Horton(1983 برای مدت طولانی این سؤال که آیا شش‌ضلعی خالی وجود دارد یا نه، بدون پاسخ ماند، ولی نیکولاس (۲۰۰۷) و گرکن (۲۰۰۸) ثابت کردند که به ازای هر مجموعهٔ کافی از نقاط با موقعیت عمومی در صفحه یک شش‌ضلعی محدب خالی وجود دارد. (f در بالا تعریف شده) درحالیکه نیکولاس نشان داد این مقدار حداکثر به اندازهٔ (f(۲۵ است. (Valtr(۲۰۰۶ اثبات گرکن را ساده می‌کند و نشان می‌دهد که به نقاط بیشتری از (f(۹، یعنی به اندازهٔ (f(۱۵ که برابر ۳۰ نقطه می‌شود، نیاز داریم، چرا که یک مجموعه از ۲۹ نقطه در موقعیت عمومی در صفحه وجود دارد که برای آن شش‌ضلعی محدب خالی وجود ندارد.(Overmars(2003 مسائل مرتبط مسئلهٔ پیدا کردن مجموعه‌عای شامل n نقطه به طوری که تعداد چندضلعی‌های محدب را کمینه کند، مشابه کمینه‌کردن تعداد عبور در یک ترسیمِ خطِ مستقیمِ یک گراف کامل است. تعداد چندضلعی‌ها باید متناسب با توان چهارم n باشد، اما مقدار ثابت دقیقی، مشخص نیست.(Scheinerman & Wilf(1994 به‌طور سرراست می‌توان نشان داد که در فضای اقلیدسی با ابعاد بالاتر، مجموعه‌های به اندازهٔ کافی بزرگ از نقاط، یک زیرمجموعه از k نقطه خواهند داشت که رأس‌های یک چندبر محدب را تشکیل می‌دهند، برای هر k بزرگ‌تر از بُعد: این مسئله خیلی سریع از موجود بودن k-ضلعی محدب در مجموعه‌های نقاط مسطح به اندازهٔ کافی بزرگ پیروی می‌کند، به این صورت که مجموعه نقاط با ابعاد بالاتر را در یک شبه فضای دوبعدی اختیاری طراحی می‌کند. | ## جمع‌بندی | اما تعداد نقاط لازم برای پیدا کردن K نقطه در حالت محدب ممکن است در ابعاد بالاتر نسبت به حالتی که در صفحه است، کم‌تر باشد، و همچنین پیدا کردن زیرمجموعه‌هایی که محدودتر هستند، امکان‌پذیر است.