Участник:МетаСкептик12/Черновик: различия между версиями
Нет описания правки |
|||
| Строка 1: | Строка 1: | ||
[[Image:Happy-End-problem.svg|thumb|300px|Задача о счастливом конце: любое множество из пяти точек содержит вершины выпуклого четырехугольника.]] |
[[Image:Happy-End-problem.svg|thumb|300px|Задача о счастливом конце: любое множество из пяти точек содержит вершины выпуклого четырехугольника.]] |
||
'''Задача о счастливом конце''' (названная так [[Эрдёш, Пол|Полем Эрдёшем]], поскольку она привела к свадьбе [[George Szekeres| |
'''Задача о счастливом конце''' (названная так [[Эрдёш, Пол|Полем Эрдёшем]], поскольку она привела к свадьбе [[George Szekeres|Дьёрдя Секереша]] и [[Esther Klein|Эстер Кляйн]]) формулируется следующим образом: |
||
:'''Теорема.''' Любое множество из пяти точек на плоскости [[general position|в |
:'''Теорема.''' Любое множество из пяти точек на плоскости [[general position|в общем положении]]<ref>В данном контексте общее положение означает, что никакие две точки не совпадают и никакие три точки не лежат на одной прямой.</ref> имеет подмножество из четырех точек, которые являются вершинами [[Выпуклый многоугольник|выпуклого ]] [[Четырехугольник|четырехугольника]]]. |
||
Теорема счастливого конца доказывается простым анализом. Если не менее четырех точек образуют [[Выпуклая оболочка|выпуклую оболочку]], в качестве выпуклого четырехугольника можно выбрать любой набор из четырех точек оболочки. В противном случае мы имеем треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырехугольник. |
Теорема счастливого конца доказывается простым анализом. Если не менее четырех точек образуют [[Выпуклая оболочка|выпуклую оболочку]], в качестве выпуклого четырехугольника можно выбрать любой набор из четырех точек оболочки. В противном случае мы имеем треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырехугольник. |
||
| Строка 18: | Строка 18: | ||
* ''f''(4) = 5.<ref> То, что доказала Эстер Кляйн.</ref> |
* ''f''(4) = 5.<ref> То, что доказала Эстер Кляйн.</ref> |
||
* ''f''(5) = 9.<ref>Согласно {{sfn|Erdős|Szekeres|1935}}, это первым доказал Э. Макаи; первое опубликованное доказательство появилось в {{sfn|Kalbfleisch|Kalbfleisch|Stanton|1970}}.</ref> Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, чтоt ''f''(5) > 8; сложнее доказать, что любое множество из девяти точек в общей позиции содержит выпуклый многоугольник. |
* ''f''(5) = 9.<ref>Согласно {{sfn|Erdős|Szekeres|1935}}, это первым доказал Э. Макаи; первое опубликованное доказательство появилось в {{sfn|Kalbfleisch|Kalbfleisch|Stanton|1970}}.</ref> Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, чтоt ''f''(5) > 8; сложнее доказать, что любое множество из девяти точек в общей позиции содержит выпуклый многоугольник. |
||
* ''f''(6) = 17.<ref>Это было доказано в {{ |
* ''f''(6) = 17.<ref>Это было доказано в {{sfn|Szekeres|Peters|2006}}. В работе реализован компьютерный перебор возможных конфигураций из 17 точек.</ref> |
||
* Значения ''f''(''N'') неизвестны для ''N'' > 6. |
* Значения ''f''(''N'') неизвестны для ''N'' > 6. |
||
| Строка 34: | Строка 34: | ||
==Пустые многоугольники== |
==Пустые многоугольники== |
||
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общей позиции ''пустой'' выпуклый четырехугольник, [[пятиугольник]], и так далее. То есть многоугольник не содержащий внутренних точек. |
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общей позиции ''пустой'' выпуклый четырехугольник, [[пятиугольник]], и так далее. То есть многоугольник не содержащий внутренних точек. |
||
Если внутри четырехугольника, существующего согласно теореме о счастливом конце, есть точка, то, соединив эту точку с двумя вершинами, не соединенными ребрами мы получим два четырехугольника один из которых выпуклый и пустой. Таким образом, пять точек в общей позиции содержат пустой выпуклый четырехугольник, как видно на иллюстрации. Любые десять точек в общей позиции содержит пустой выпуклый пятиугольник.<ref>{{ |
Если внутри четырехугольника, существующего согласно теореме о счастливом конце, есть точка, то, соединив эту точку с двумя вершинами, не соединенными ребрами мы получим два четырехугольника один из которых выпуклый и пустой. Таким образом, пять точек в общей позиции содержат пустой выпуклый четырехугольник, как видно на иллюстрации. Любые десять точек в общей позиции содержит пустой выпуклый пятиугольник.<ref>{{sfn|Harborth|1978}}.</ref> Однако существуют сколь угодно большие множества точек в общей позиции, которые не содержат пустой [[Правильный семиугольник|семиугольник]].<ref>{{sfn|Horton|1983}}</ref> Таким образом, эта проблема не является проблемой [[Теория Рамсея|теории Рамсея]] и в принципе решена. |
||
Вопрос о существовании пустого [[Шестиугольник|шестиугольника]] долгое время оставался открытым. Но в {{ |
Вопрос о существовании пустого [[Шестиугольник|шестиугольника]] долгое время оставался открытым. Но в {{sfn|Nicolás|2007}} и {{sfn|Gerken|2008}} было доказано, что всякое достаточно большое множество точек в общей позиции содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более ''f''(9) (предположительно 129) и не менее 30 точек.<ref>{{sfn|Overmars|2003}}.</ref> |
||
==Примечания== |
==Примечания== |
||
Версия от 15:11, 5 февраля 2013
Задача о счастливом конце (названная так Полем Эрдёшем, поскольку она привела к свадьбе Дьёрдя Секереша и Эстер Кляйн) формулируется следующим образом:
- Теорема. Любое множество из пяти точек на плоскости в общем положении[1] имеет подмножество из четырех точек, которые являются вершинами выпуклого четырехугольника].
Теорема счастливого конца доказывается простым анализом. Если не менее четырех точек образуют выпуклую оболочку, в качестве выпуклого четырехугольника можно выбрать любой набор из четырех точек оболочки. В противном случае мы имеем треугольник и две точки внутри него. Прямая, проходящая через две внутренние точки, в силу общего положения точек не пересекает одну из сторон треугольника. Вершины этой стороны и две внутренние точки образуют выпуклый четырехугольник.
Многоугольники с произвольным числом вершин
Эрдёш и Секереш обобщили этот результат на произвольное число точек, что является оригинальным развитием теории Рамсея. Они также выдвинули гипотезу Эрдёша-Секереша - точную формулу для максимального числа вершин выпуклого многоугольника обязательно существующего в множестве из N точек в общей позиции.
В [2] доказано следующее обобщение:
- Теорема. Для любого натурального N, всякое достаточно большое множество точек в общей позиции на плоскости имеет подмножество N точек, которые являются вершинами выпуклого многоугольника.
Это доказательство появилось в той же статье, где доказывается теорема Эрдёша — Секереша о монотонных подпоследовательностях в числовых последовательностях.
Пусть f(N) означает минимальное M для которого любое множество any из M точек в общей позиции содержит выпуклый N-угольник. Известно что
- f(3) = 3, очевидно.
- f(4) = 5.[3]
- f(5) = 9.[4] Множество из восьми точек не содержащее выпуклый пятиугольник на иллюстрации показывает, чтоt f(5) > 8; сложнее доказать, что любое множество из девяти точек в общей позиции содержит выпуклый многоугольник.
- f(6) = 17.[5]
- Значения f(N) неизвестны для N > 6.
Исходя из известных значений f(N) для N = 3, 4 и 5, Эрдёш и Секереш предположили, что
- для всех
Эта гипотеза не доказана, но известны оценки сверху и снизу.
Позднее конструктивным построением авторы гипотезы доказали оценку снизу, совпадающую с гипотетическим равенством.
Однако наилучшая известная оценка сверху при N ≥ 7 не является близкой.
Пустые многоугольники
Интересен также вопрос о том, содержит ли достаточно большое множество точек в общей позиции пустой выпуклый четырехугольник, пятиугольник, и так далее. То есть многоугольник не содержащий внутренних точек. Если внутри четырехугольника, существующего согласно теореме о счастливом конце, есть точка, то, соединив эту точку с двумя вершинами, не соединенными ребрами мы получим два четырехугольника один из которых выпуклый и пустой. Таким образом, пять точек в общей позиции содержат пустой выпуклый четырехугольник, как видно на иллюстрации. Любые десять точек в общей позиции содержит пустой выпуклый пятиугольник.[8] Однако существуют сколь угодно большие множества точек в общей позиции, которые не содержат пустой семиугольник.[9] Таким образом, эта проблема не является проблемой теории Рамсея и в принципе решена.
Вопрос о существовании пустого шестиугольника долгое время оставался открытым. Но в [10] и [11] было доказано, что всякое достаточно большое множество точек в общей позиции содержит пустой шестиугольник. Сегодня известно, что это множество должно содержать не более f(9) (предположительно 129) и не менее 30 точек.[12]
Примечания
- ↑ В данном контексте общее положение означает, что никакие две точки не совпадают и никакие три точки не лежат на одной прямой.
- ↑ Erdős, Szekeres, 1935.
- ↑ То, что доказала Эстер Кляйн.
- ↑ Согласно , это первым доказал Э. Макаи; первое опубликованное доказательство появилось в .
- ↑ Это было доказано в . В работе реализован компьютерный перебор возможных конфигураций из 17 точек.
- ↑
- ↑ . Смотри биномиальные коэффициенты и «O» большое и «o» малое относительно обозначений и формулу Стирлинга для вывода асимптотики.
- ↑ .
- ↑
- ↑ Nicolás, 2007.
- ↑ Gerken, 2008.
- ↑ .
Ошибка в сносках?: Тег <ref> с именем «_235064262f5638dd», определённый в <references>, не используется в предшествующем тексте.
Ошибка в сносках?: Тег <ref> с именем «_1d28749f954a18d7», определённый в <references>, не используется в предшествующем тексте.
Ошибка в сносках?: Тег <ref> с именем «_e3ed6f63a3570f66», определённый в <references>, не используется в предшествующем тексте.
Ошибка в сносках?: Тег <ref> с именем «_90e3935bb3ca33a2», определённый в <references>, не используется в предшествующем тексте.
Ошибка в сносках?: Тег <ref> с именем «_579d45ac93326f97», определённый в <references>, не используется в предшествующем тексте.
Ошибка в сносках?: Тег <ref> с именем «_5d258ce12ce0877c», определённый в <references>, не используется в предшествующем тексте.
Ошибка в сносках?: Тег <ref> с именем «_419f983f63825cea», определённый в <references>, не используется в предшествующем тексте.
<ref> с именем «_f35c3446fd84ffc3», определённый в <references>, не используется в предшествующем тексте.Ссылки
- Chung, F.R.K.; Graham, R.L. (1998), "Forced convex n-gons in the plane", Discrete and Computational Geometry, 19 (3): 367—371, doi:10.1007/PL00009353.
- Erdős, P.; Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Math, 2: 463—470.
- Erdős, P.; Szekeres, G. (1961), "On some extremum problems in elementary geometry", Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 3—4: 53—62. Reprinted in: Erdős, P. (1973), Spencer, J. (ed.), The Art of Counting: Selected Writings, Cambridge, MA: MIT Press, pp. 680—689.
- Gerken, Tobias (2008), "Empty convex hexagons in planar point sets", Discrete and Computational Geometry, 39 (1—3): 239—272, doi:10.1007/s00454-007-9018-x.
- Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M. (eds.), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, ISBN 0-387-00424-6.
- Harborth, Heiko (1978), "Konvexe Fünfecke in ebenen Punktmengen", Elem. Math., 33 (5): 116—118.
- Horton, J. D. (1983), "Sets with no empty convex 7-gons", Canadian Mathematical Bulletin, 26 (4): 482—484, doi:10.4153/CMB-1983-077-8.
- Kalbfleisch, J.D.; Kalbfleisch, J.G.; Stanton, R.G. (1970), "A combinatorial problem on convex regions", Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 1, Baton Rouge, La.: Louisiana State Univ., pp. 180—188.
- Kleitman, D.J.; Pachter, L. (1998), "Finding convex sets among points in the plane", Discrete and Computational Geometry, 19 (3): 405—410, doi:10.1007/PL00009358.
- Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", Bulletin of the American Mathematical Society, 37 (04): 437—458, doi:10.1090/S0273-0979-00-00877-6.
- Nicolás, Carlos M. (2007), "The empty hexagon theorem", Discrete and Computational Geometry, 38 (2): 389—397, doi:10.1007/s00454-007-1343-6.
- Overmars, M. (2003), "Finding sets of points without empty convex 6-gons", Discrete and Computational Geometry, 29 (1): 153—158, doi:10.1007/s00454-002-2829-x.
- Peterson, Ivars (2000), "Planes of Budapest", MAA Online.
Внешние связи
- Happy ending problem and Ramsey-theoretic proof of the Erdős-Szekeres theorem on PlanetMath
- Weisstein, Eric W. Happy End Problem (англ.) на сайте Wolfram MathWorld.
Категория:Дискретная геометрия Категория:Евклидова геометрия Категория:Математика Категория:Теория Рамсея