The Happy Ending Problem
Imagine you have 5 distinct points somewhere in the plane. Can you always join up at least 4 of them to make a convex quadrilateral? For instance in the three collections of points below there are 4 highlighted points making a quadrilateral:
It turns out it is always true. If 4 or 5 points form a convex shape on the periphery (a convex hull) then we are already done. The other case is that we have 3 points on the periphery with two on the inside (such as the green case above). In which case you can also pick both of them along with two of the outside vertices.
This problem was proposed by Esther Klein and was solved by George Szekeres (along with Paul Erdős). It was Erdos that coined the name "The Happy Ending Problem" after it led to the meeting and subsequently marriage of Klein and Szekeres two years later in 1937. In 2005 they died within an hour of one another after many years of happy marriage.
The number of points needed for a n-gon is only conjected so far at 2n-2+1. We have proven this as a lower bound, but our upper bound is slightly higher (although definitely finite). We have also shown the formula is true for the pentagon (9 points needed) and the hexagon (17 points needed). Below is a set of 8 points that don't form a pentagon:
8 are not sufficient for a pentagon, but 9 always are.
