The happy ending problem

The happy ending problem is one of those mathematical questions that are quite easy to explain but have as yet defied all attempts to answer them. Some of the best mathematicians in the world have put their minds to it, to no avail. It concerns points drawn on a piece of paper and the figures you can create by connecting them up.

Let's start with three points, drawn on a piece of paper, that don't all lie on a line. You can always connect them up to form a triangle which has the three points as its corners:

What happens when you have four points (with no three of them lying on the same line)? Connecting them you can create a four-sided figure (called a quadrilateral) which has the four points as its corners:

But depending on how the points are distributed, the quadrilateral might look a bit odd (like the centre one in the image above) containing dents and spikes and not at all resembling the neat and regular rectangle that first springs to mind when we think of four-sided figures. So let's impose a further restriction. Let's see if we can draw a convex quadrilateral with our four points, that is, one in which all internal angles are at most 180 degrees. This ensures the shape contains no corners that are "pushed inwards", creating a dent. The quadrilateral below is not convex, but the left and right ones in the figure above are.

Some simple examples show that given four points, you can't always draw a convex quadrilateral:

Things change, though, when you add one more point. When you have five points drawn on a piece of paper (without three of them lying on the same line), you can always connect four of them to form a convex quadrilateral. The extra point gives you just enough flexibility to do it. Here are some examples (you might actually be able to draw several different convex quadrilateral with the same five points):

This result was named the happy ending theorem by the mathematician Paul Erdős, because two of his friends who worked on it, George Szekeres and Esther Klein, ended up getting married. You can see a sketch proof of this result below.

Adding sides

The obvious next question is how many points you need to ensure that you can connect five of them to form a convex pentagon (five-sided figure). The answer is 9 (without three of them lying on the same line). Here are two examples:

To be sure you can draw a convex hexagon (six sides) you need 17 points. Here's an example:

How many points do you need to be sure you can draw a convex heptagon ($7$ sides), which has these points as its corners? The answer is that nobody knows. The same goes for $8$, $9$, $10$ or any number $n$ of sides. Erdős and Szekeres believed that given a natural number $n \geq 3 $, the number of points you need to ensure you can connect $n$ of them to form a convex $n$-sided polygon is $$1+2^{n-2}.$$ The result is true for $n=3$ (triangles), as in that case $$1+2^{n-2} = 1+2^{3-2} = 1+2 = 3.$$ It also works for $n=4$, $n=5$ and $n=6$, as $$1+2^{4-2} = 1+2^{2} = 1+4 = 5,$$ $$1+2^{5-2} = 1+2^{3} = 1+8 = 9,$$ and $$1+2^{6-2} = 1+2^{4} = 1+16 = 17.$$ But whether the result is true for $n>6$ is not known. Erdős and Szekeres were able to prove that the number of points you need to guarantee a convex $n$-sided polygon is always at least $1+2^{n-2}$ and they also proved that it is finite: in other words, by drawing enough points you can be sure that there'll be a convex $n$-sided polygon within them. What hasn't been proved is how much is enough.

The happy ending problem illustrates an interesting phenomenon: if a system is large enough (e.g. sufficiently many points) then you can hope to find some order within it (e.g. convex figures), even if the system as a whole is disordered. It's a phenomenon studied by an area of maths called Ramsey theory. You can find out more in the Plus article Friends and strangers.

Sketch proof of the happy ending theorem for n=4

Suppose you have five points in the plane. Let's first suppose that three of these points can be connected up to form a triangle that contains the two remaining points, call them $A$ and $B$, in its interior. The line that connects these two interior points cuts the triangle into two parts. One piece only contains one of the triangle's corners, and the other contains two: call these two corners $C$ and $D$. It's now not too difficult to convince yourself, using some elementary geometry, that the quadrilateral $ABCD$ (see the figure below) has no interior angles greater than $180$ degrees. This means that it is convex. What if there isn't a triangle that contains two of the five points in its interior? Then at least one of them lies outside any triangle you form with three of the points (see the figure below). You can form a quadrilateral from the three points of the triangle and the outside point, and again it's not too hard to show that all the interior angles of that quadrilateral are less than $180$ degrees, which means that it is convex.

---

About the author

Marianne Freiberger is Editor of Plus.