Happy End Problem

As this is the last post of the year, I thought it would be appropriate to end with a post on the "Happy End Problem." I will explain the problem, which is pretty cool in itself, and then talk a little bit about the history behind it.

The initial question was if any five points were placed on a plane with no three of them in a straight line, will four of those points always form a convex quadrilateral? For example, in the following image:

The following convex quadrilateral can be formed:

Will this always work? As usual, I encourage you to grab a scrap piece of paper and try out a few examples. Have fun with it. Get creative! You will end up finding that no matter how you position the five points, you cannot get a combination without a convex quadrilateral.

Why is this true? In fact, there is a very easy way to prove it. Let's analyze three cases.

The first case is the top left one in the red, where the five points form a convex pentagon. In this instance, connecting any four of the points will form a convex quadrilateral by nature.

The second case is the top right one in the blue, where one point is located in between the four outside points. The illustration shows the inside point being included in the quadrilateral, but it could have just as easily been made as just the four outside points. This will continue to work for any combination of this nature by logic.

The third case is the bottom one in the yellow, where two points are enclosed in a triangle. When you draw a line between the two center points, two of the outside points will end up on one side and one will be on the other. Using the two outside points as your third and fourth vertices will form a quadrilateral without flaw.

Now, you might be wondering if one can prove a similar case with a convex pentagon. Could it be done with six? Seven? Eight? Turns out, nine points are required for it to work every time. As you can see below, eight points is just one too few.

What about convex hexagons? Or heptagons? Or octagons? Or chiliagons (1000-sided polygons)? Well, what many mathematicians will do from here is look for a formula to figure out how many points are required for a given n-gon. We know that for a triangle (n = 3), just 3 points are needed (all triangles are convex). For a quadrilateral (n = 4), we proved that 5 points are needed. For a pentagon (n = 5), I mentioned that 9 points are needed. Do you see the pattern?

3, 5, 9, ...

It is not easy to spot at first, but what if I subtract one from each of those terms:

2, 4, 8, ...

They are all now powers of two! This pattern seems to fit the formula A_n = 2^n-2 + 1. Plugging six in for n would give:

A₆ = 2^6-2 + 1
A₆ = 16 + 1
A₆ = 17

This formula predicts that seventeen points would be required for a hexagon. Mathematicians would then work to try to prove that this is the case. Further, they would try to prove that for any value of n, the A_n formula holds true.

George Szekeres (1911-2005; a Hungarian-Austrailian mathematician and analytical chemist) and Esther Klein (1910-2005, another Hungarian-Austrailian mathematician) worked together to prove that all values of n will have a finite A_n output (there will be a number of points that creates the ability for a convex n-gon to be formed), but they could not get this bound down to the formula above. Soon after this proof was published, Szekeres and Klein married each other, which inspired the name "Happy End Problem."

Paul Erdös (1913-1996; a Hungarian mathematician), possibly one of the most influential of the twentieth century), was able to prove successfully that with 71 points, a hexagon can always be drawn.

Sixty years later, Ronald Graham (born 1935; a Californian mathematician) and his wife, Fan Chung, decided to take a swing at the problem. While on a plane ride to a math conference in New Zealand, they were able to lower Erdös's bound to 70 points, which doesn't sound like much, but it brought the problem back into the minds of mathematicians. It was also ironic that another achievement pertaining to the Happy End Problem was from a couple.

Daniel Kleitman (born 1934; an applied mathematician at MIT) and Lior Pachter (born 1972; an Israeli mathematician and molecular biologist at Berkeley College) worked together to lower the upper bound to 65 points. The number was then lowered to 37 points, and has yet to be lowered further.

Although lots of progress has been made on this problem, the overarching proof still has not yet been found. There has been no counterexample to the A_n formula, and there has certainly been no guaranteed formula to generate the future values. People often wonder what a mathematician actually does for his/her job. A big part of it is trying to figure out the answers to these unsolved problems, which can often be understood by the average person. Try playing around with it and you might make a discovery too.