HMMT 二月 2006 · 冲刺赛 · 第 45 题
HMMT February 2006 — Guts Round — Problem 45
题目详情
- On your answer sheet, clearly mark at least seven points, as long as (i) No three are collinear. (ii) No seven form a convex heptagon. Please do not cross out any points; erase if you can do so neatly. If the graders deem that your paper is too messy, or if they determine that you violated one of those conditions, your submission for this problem will be disqualified. Otherwise, your score will be the number of points you marked minus 6, even if you actually violated one of the conditions but were able to fool the graders.
解析
- On your answer sheet, clearly mark at least seven points, as long as (i) No three are collinear. (ii) No seven form a convex heptagon. Please do not cross out any points; erase if you can do so neatly. If the graders deem that your paper is too messy, or if they determine that you violated one of those conditions, your submission for this problem will be disqualified. Otherwise, your score will be the number of points you marked minus 6, even if you actually violated one of the conditions but were able to fool the graders. Solution: This is the heptagon case of what is known as the “Happy Ending” or “Erd˝ os-Szekeres” problem, which in general asks, For any integer n ≥ 3 , what is the smallest N ( n ) , such that any N ( n ) points in the plane in general position determine a convex n -gon? It is known that such an N ( n ) always exists and is finite (in fact a n − 2 specific upper bound has been found). The best known lower bound is N ( n ) ≥ 2 +1; Erd˝ os and Szekeres conjectured that this bound is tight. The n ≤ 5 cases have been known for some time. According to the Wikipedia, the n = 6 case is solved but unpublished, and for n ≥ 7, the problem remains open. For a discussion, see W. Morris and V. Soltan. The Erd˝ os-Szekeres Problem on Points in Convex Postion—A Survey, Bulletin of the American Math Monthly . 37 (2000), 437–458. This article is available at http://www.ams.org/bull/2000-37-04/S0273-0979-00-00877-6/home.html . If N (7) = 33, the highest sure score on this problem would be 32 − 6 = 26. It is not known whether there exist arbitrarily large sets of points that will fool the graders. The unexamined life is not worth living. 17