The Happy Ending problem (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein) is the following statement:
- Theorem. Any set of five points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral.
This was one of the original results that led to the development of Ramsey theory.
The Happy Ending theorem can be proven by a simple case analysis: If four or more points are vertices of the convex hull, any four such points can be chosen. If on the other hand the point set has the form of a triangle with two points inside it, the two inner points and one of the triangle sides can be chosen. See Peterson (2000) for an illustrated explanation of this proof, and Morris & Soltan (2000) for a more detailed survey of the problem than we provide here.
The Erdős–Szekeres conjecture states precisely a more general relationship between the number of points in a general-position point set and its largest convex polygon. It remains unproven, but less precise bounds are known.
Read more about Happy Ending Problem: Larger Polygons, Empty Polygons, Related Problems
Famous quotes containing the words happy ending, happy and/or problem:
“...one of my motivating forces has been to recreate the world I know into a world I wish I could be in. Hence my optimism and happy endings. But I’ve never dreamed I could actually reshape the real world.”
—Kristin Hunter (b. 1931)
“When you realize how hard it is to know the truth about yourself, you understand that even the most exhaustive and well-meaning autobiography, determined to tell the truth, represents, at best, a guess. There have been times in my life when I felt incredibly happy. Life was full. I seemed productive. Then I thought,”Am I really happy or am I merely masking a deep depression with frantic activity?” If I don’t know such basic things about myself, who does?”
—Phyllis Rose (b. 1942)
“Our political problem now is “Can we, as a nation, continue together permanentlyforever—half slave, and half free?” The problem is too mighty for me. May God, in his mercy, superintend the solution.”
—Abraham Lincoln (1809–1865)