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.

Figure Out The Number Of Digits In Gigantic Numbers

In science and math, you often run across numbers that are too big to be written in standard form. They are usually written in scientific notation, but they are also sometimes written as a number to a certain power. For instance, one might say that there are 2²⁰ outcomes of the flipping of twenty coins rather than saying 1.049x10⁶ ways.

By using that power, your information is likely more accurate. However, this power does not tell you much about the number. Most of us would have no idea if 2²⁰ is in the thousands, millions, billions, etc. at the first glance.

First, lets ask a question. What is the common logarithm of a number, or what can you gather from it? Well, the common logarithm is the power that ten has to be raised to to obtain that number. For instance:

log(100) = 2

log(5000) = 3.69897

log(6283185) = 6.79818

What do you notice about these numbers? It's not clear at first, but count the number of digits in each of the inputs. You will find that the common log is always just a little bit below that number. In fact, to figure out the number of digits in a number, all you have to do is take the common log and round up to the nearest integer.

How can this be used to find the number of digits in a power? Interestingly enough, there is a logarithmic identity stating that the log of a number raised to the power is equal to the power times the log of the number. For example,

log(27) = 3log(3)

ln(32) = 5ln(2)

log(2²⁰) = 20log(2)

Look at the last example there. We just simplified the gigantic 2²⁰ to a reasonable looking 20log(2), which is the formula to figure out the number of digits it has. In other words, the number of digits in 2²⁰ is just 20log(2) rounded to the nearest integer. Plugging this into a calculator tells you that the log is 6.0206, meaning that there are seven digits in the number. If you multiply it out, you will find that 2²⁰ = 1048576, which does indeed have seven digits. 

So whenever a type of problem pops up with a power of this sort, try to determine how many digits it is. Chances are you will gain a much better understanding of the statistic when you perform this quick calculation.

Math in the News: The Influences of Politics

Though mathematics is normally a pretty concrete subject, people's intuition for it is not. Probability and statistics in particular is a very difficult area for us to grasp, as you've seen with the Monty Hall Problem I talked about a few weeks ago.

Here is another example of mathematical aptitude being influenced by an outside source, but this time, it is not just a matter of lack of skill or desire to be correct. It is also influenced sometimes by political views, as Kevin Drum shows in this news article. Check it out!

http://m.motherjones.com/kevin-drum/2013/09/politics-destroys-math-ability

Isosceles Triangle Theorem

The field of geometry is comprised of many different types of questions. Some are construction based, such as “what is the area of this circle?” On the other hand, many are proof based, like “why are these two triangles congruent?” This is slightly different from the proofs I normally discuss; proofs I normally post are very generalized theorems while these questions are more similar to a specific algebra or arithmetic problem.

When writing a geometric proof, many different theorems come into play. One must use the generalized theorems, properties, and postulates to arrive at a conclusion. Let’s try a simple proof just to demonstrate the nature of these theorems. Let’s prove that triangle ABE is congruent to triangle CDE.

First, we would say that it is given that segment AC is parallel to segment BD and that segment AB is parallel to segment CD. We would then say that ABCD is a parallelogram by the definition of a parallelogram (which requires two sets of parallel sides). The definition of a parallelogram also requires AB and CD to be congruent. The vertical angle theorem can be used to say that angle AEB is congruent to angle CED. The alternate interior angle theorem says that angle ABE is congruent to angle DCE. The angle-angle-side triangle congruence postulate then concludes that triangle ABE is congruent to triangle CDE.

As you can see, there are many steps in this proof, and each one uses a different definition, theorem, or postulate. In high school geometry classes, students are told these theorems and postulates, and expected to memorize them for future examples. This makes geometry boring and pointless, when it can be quite fascinating. A way to easily spice up geometric proofs is to actually prove the theorems before they are used in class. If Euclid could do it, then we can do it.

A fun one to prove is the Isosceles Triangle Theorem. This theorem states that when a triangle has two congruent sides, it also has two congruent angles. This can be proven in a similar way as the congruent triangle question I posed earlier. Take an isosceles triangle:

If you were to bisect that top angle, it would create two new triangles. Since the original triangle is isosceles, it is given that the top left segment is congruent to the top right segment. The definition of a bisection (cutting an angle in half) states that the left part of the top angle is congruent to the right part of the top angle. The reflexive property of congruence states that the middle segment is congruent to itself. By the side-angle-side triangle congruence postulate, the left triangle is congruent to the right triangle. And finally, by CPCTC (common parts of congruent triangles are congruent), the bottom left angle is congruent to the bottom right angle.

This sort of geometric proof language sounds extremely long and boring. However, finding uses for it such as proving the Isosceles Triangle Theorem can make it a little more fun. Among many things, I think that schools should teach the reasons behind these theorems to make it more logical and fun to apply them to class.