مسألة نهاية سعيدة

مسألة النهاية السعيدة، كل مجموعة من خمس نقاط في موضع عام تضم أربع نقاط تشكل مضلع محدب.

في الرياضيات، مسألة النهاية السعيدة، سميت بهذا الاسم من قبل بول إيردوس لأنها أدت إلى زواج جورج سيكيرس من إيستير كلاين، تنص على ما يلي:

أي مجموعة من خمس نقاط في المستوي في مواضع عامة تحوي على مجموعة جزئية من أربع نقاط تشكل رؤوس مضلع محدب.

كانت هذه واحدة من النتائج الأصلية التي أدت إلى تطوير نظرية رمزي.

بالإمكان إثبات مبرهنة النهاية السعيدة عن طريق تحليل حالة بسيطة: إذا كان أربع نقاط أو أكثر رؤوس لانغلاق محدب، يمكن اختيار أية أربع نقاط منهم. أما من ناحية أخرى لمجموعة النقط شكل مثلث مع نقتطين بداخله، يمكن اختيار النقتطين الداخليتين وواحد من جوانب المثلث. راجع قالب:Harvard citation text للشرح المصور للاثبات، و قالب:Harvard citation text للمزيد من الدراسة المفصلة للمسألة التي نقدمها هنا.

مضلعات أكبر

مجموعة من ثمانية نقط في مواضع عامة بدون مثمن محدب.

برهن قالب:Harvard citation text التعميم التالي:

لأي عدد صحيح موجب N، أي مجموعة نقاط محدودة كبيرة بما فيه الكفاية في المستوي في مواضع عامة لها مجموعة جزئية من N نقط التي تشكل مضلع محدب.

يظهر البرهان في نفس المقال الذي يبرهن نظرية إيردوس-سيكيرس على مجموعات جزئية رتيبة في تسلسل أعداد.

نرمز بـ (f(N لأدنى قيمة لـ M بحيث لمجموعة من M نقط في مواضع عامة يجب أن تحتوي على محدب بـ N رؤوس، معروف أن:

f(3) = 3, بديهيا.
^[١]f(4) = 5.
^[٢]f(5) = 9.
^[٣]f(6) = 17.
قيمة (f(N غير معروفة لكل N > 6; كنتيجة من قالب:Harvard citation text معروفة أنها محدودة.

على أساس القيم (f(N المعروفة لكل N = 3, 4 و 5، حزر إيدرش وسكريش في مقالهما الأصلي أن

f (N) = 1 + 2^{N - 2} for all N \geq 3 .

برهنوا لاحقا، عن طريق بناء أمثلة واضحة، أن:

f (N) \geq 1 + 2^{N - 2},

^[٤]

ولكن الحد الأعلى الأفضل المعروف لـ N ≥ 7 هو:

f (N) \leq (\binom{2 N - 5}{N - 2}) + 1 = O (\frac{4^{N}}{\sqrt{N}}) .

^[٥]

مراجع

قالب:مراجع

قالب:بداية المراجع

قالب:نهاية المراجع قالب:شريط بوابات

↑ This was the original problem, proved by Esther Klein.
↑ According to قالب:Harvard citation text, this was first proved by E. Makai; the first published proof appeared in قالب:Harvard citation text.
↑ This has been proved by قالب:Harvard citation text. They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations.
↑ قالب:Harvard citation text
↑ قالب:Harvard citation text. See معامل ثنائي and رمز O الكبير for notation used here and عدد كاتالانs or تقريب ستيرلينغ for the asymptotic expansion.

[1] This was the original problem, proved by Esther Klein.

[2] According to قالب:Harvard citation text, this was first proved by E. Makai; the first published proof appeared in قالب:Harvard citation text.

[3] This has been proved by قالب:Harvard citation text. They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations.

[4] قالب:Harvard citation text

[5] قالب:Harvard citation text. See معامل ثنائي and رمز O الكبير for notation used here and عدد كاتالانs or تقريب ستيرلينغ for the asymptotic expansion.

[١]

[٢]

[٣]

[٤]

[٥]

مسألة نهاية سعيدة

مضلعات أكبر

مراجع

قائمة التصفح

بحث