The happy ending problem

By 
Marianne Freiberger

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:

Triangles

Three points in the plane form a triangle (as long as they don't lie on the same line).

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:

Quadrilaterals

Some quadrilaterals.

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.

Non-convex quadrilateral

A non-convex quadrilateral.

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

Non-convex quadrilaterals

Given four points, it's not always possible to connect them up to form 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):

Quadrilaterals

Given five points (with no three lying on the same line), you can always find a convex quadrilateral which has four of them as its corners.

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:

Pentagons

Given nine points (with no three lying on the same line), you can always find a convex pentagon which has five of them as its corners.

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

Hexagon

Given 17 points (with no three lying on the same line), you can always find a convex hexagon which has six of them as its corners.

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$.
Proof

The triangle cut in two pieces.

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.
Proof

At least one point lies outside of the triangle.

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.
Proof


About the author

Marianne Freiberger is Editor of Plus.

Comments

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.

I think 180 was meant to be 360.

The internal angles of any convex polygon are at most 180, otherwise it would be concave.

No, each internal angle of any convex polygon is not at most 180 degrees. That would mean they could be 180 degrees. Every n-sided convex polygon has n internal angles, and each of them is less than 180 degrees. "At most" means "less than or equal to," and that is false here.