Maths Olympiad Prep

Library / /300 of 377

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 n3n \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)2n2+1N(n) \geq 2^{n-2}+1; Erdős and Szekeres conjectured that this bound is tight. The n5n \leq 5 cases have been known for some time. According to the Wikipedia, the n=6n=6 case is solved but unpublished, and for n7n \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 326=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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