Maths Olympiad Prep

Library / Harvard-MIT Mathematics Tournament /278 of 352

Harvard-MIT Mathematics Tournament

Geometry Difficulty 5.5 AIME, harder Prove it United States

Problem:
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 66, even if you actually violated one of the conditions but were able to fool the graders.

Solution

Solution:
This is the heptagon case of what is known as the "Happy Ending" or "Erdős-Szekeres" problem, which in general asks, For any integer n≥3n \geq 3, what is the smallest N(n)N(n), such that any N(n)N(n) points in the plane in general position determine a convex nn-gon? It is known that such an N(n)N(n) always exists and is finite (in fact a specific upper bound has been found). The best known lower bound is N(n)≥2n−2+1N(n) \geq 2^{n-2}+1; Erdős and Szekeres conjectured that this bound is tight. The n≤5n \leq 5 cases have been known for some time. According to the Wikipedia, the n=6n=6 case is solved but unpublished, and for n≥7n \geq 7, the problem remains open.
For a discussion, see
W. Morris and V. Soltan. The Erdős-Szekeres Problem on Points in Convex Position-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)=33N(7)=33, the highest sure score on this problem would be 32−6=2632-6=26. It is not known whether there exist arbitrarily large sets of points that will fool the graders.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.