Monday, February 27, 2017
Random Triangles and Pillow Problems for Insomniacs
by Jonathan Kujawa
While laying in bed on the night of January 20, 1884, Lewis Carroll conjured up the following puzzle:
Three Points are taken at random on an infinite Plane. Find the chance of their being the vertices of an obtuse-angled Triangle.
That is, since any three points on a sheet of paper can be connected to form a triangle, what's the likelihood that one of the angles is more than ninety degrees if you pick those points at random?
If you only know Lewis Carroll from Alice in Wonderland you may be surprised that his thoughts turned to mathematics. In fact, his day job was to be a mathematician at Christ Church college in Oxford under the name Charles Dodgson. In addition to his more famous works of fiction, he was known for writing several mathematical texts. When teaching linear algebra I always take a day to talk about Dodgson Condensation .
One of the books he wrote is Curiosa Mathematica, Part II: Pillow Problems Thought Out During Wakeful Hours. It is the compendium of 72 math problems Dodgson pondered and solved while waiting to fall asleep. Helpfully he also gives the date he dreamt up the problem and the solution he devised. Go here if you'd like to take a look at the other 71 problems.
The Obtuse Triangle Problem is No. 58. Before we take a look at his solution we should step back a minute. What does it mean to pick three points at random? Like most politicians' speeches, it sounds good but falls apart under the slightest scrutiny. Are we to pick x and y coordinates for each of these points? Alternatively, we could pick an angle between 0 and 360 degrees and a distance and, starting at the origin, take the point at that angle and distance. Or, since all we care about is the resulting triangle, maybe we should randomly pick an angle between 0 and 180 degrees, pick two side lengths at random, and make the triangle made by drawing two sides of those lengths with that angle between them. I'm sure we could come up with a dozen different ways to randomly pick a triangle.
If a random triangle was a random triangle, and if the world was fair and just, then the odds of an obtuse triangle would be the same regardless of our method. Sadly, the world is neither fair nor just. It will matter how we choose to pick a random triangle .
Mathematicians know from centuries of painful experience that the slightest sloppiness at the beginning can lead to huge problems down the road. Before we worry about picking points on a two-dimensional plane, let's look at what should be an easier, one-dimensional problem:
If you break a stick of length one in two places, what is the chance that the three pieces can be used to make a triangle?
Certainly if you break it so that there is one really long piece and two stubby bits, then you won't be able to make a triangle. But you can also see that if the pieces are roughly equal in length then you'll be able to make a triangle with them. So what is the probability you'll be able to make a triangle?
Aggravatingly the answer is: it depends. The good news is that it isn't hard to tell if you can make a triangle or not. Everybody knows that going straight along one side will always be shorter than taking a detour around the other two sides. That is, if the three pieces have lengths a, b, and c, then in a triangle you have to have a+b ≥ c, a+c ≥ b, and b+c ≥ a. It turns out that the converse is also true: if you have lengths a, b, and c which satisfy these three inequalities, then you can form a triangle. That is, you can form a triangle if and only if all three side lengths are less than 1/2.
Say you break the stick at x and y, where these are numbers between 0 and 1. Then the side lengths are x, y-x and 1-y . Plotting the possible pairs of x's and y's where all three side lengths are less than 1/2 gives the green region:
Calculating areas we see that the chance of forming a triangle is 1/4.
However, that is not the only way of breaking a stick into three. You could instead pick a point a random and break the stick there. Then randomly pick one of the two halves and break it at some random spot. If anything, this is the more realistic scenario if you were to break a stick with your bare hands. In any case, a similar analysis shows that breaking a stick into three pieces in this way allows you to form a triangle 1/6 of the time. I find it horrifying that two reasonable approaches led to dramatically different outcomes . These sorts of unintuitive results convinced me that probability was not my natural mathematical habitat.
This has shades of the famous Monty Hall problem: Imagine you are a game show contestant. There are three doors but only one has a prize behind it. You start by picking one door at random. Since the host knows where the prize is, she opens one of the other two doors and shows you that it is empty. The host then gives you the opportunity to either stick with your initial choice or switch to the other closed door. Should you stand pat, switch, or does it not matter? It isn't obvious at first, but it turns out that there is a 1/3 chance that your door has the prize and a 2/3 chance the other closed door has the prize. You should switch!
In the case of the pillow problem, Dodgson calculated that the probability of having an obtuse triangle is
That is, using Dodgson's method of picking three points at random leads to an obtuse triangle approximately 2/3 of the time. On the other hand, Richard Guy showed that several other reasonable methods lead to an obtuse triangle 3/4 of the time !
I learned about the Obtuse Triangle Problem during a talk by Jason Cantarella at the Joint Meetings in January. The Joint Meetings is the jumbo annual meeting of mathematicians organized by the AMS, MAA, ASL, AWM, NAM, and SIAM. Dr. Canterella is a mathematician at the University of Georgia and his research is at the interface of geometry with other subjects. We came across him more than a year ago here at 3QD when we talked about his work on knots.
In this case Dr. Canterella was talking about his joint work with Tom Needham, Clayton Shonkwiler, and Gavin Stewart. You can read their paper here. In it they take a different approach to the Obtuse Triangle Problem. Namely, they instead consider the question of randomly picking three side lengths which sum to 2 . By doing an elementary change of variables they show that the choice of three side lengths which forms a triangle is the same as choosing an x, y, and z which satisfy x2+y2+z2=1. That is, they show that picking the three side lengths of a triangle is the same as choosing a point on the sphere.
This is great! Instead of picking three points in the plane, we are now randomly picking a single point on the sphere. This eliminates many of the pesky issues of ambiguity. Even better, a sphere has a natural geometry we can exploit. For example, any two points are connected by a shortest path, often called a great circle . You see these when you take intercontinental flights. The long, arcing path of your flight on the map is actually the shortest route once you take into account the curve of the Earth. You can use this page to draw great circles of your own.
In their formulation, the Obtuse Triangle Problem becomes a question of identifying the points on the sphere which correspond to triangles with an obtuse angle and then computing the fraction of the sphere covered by these points. Cantarella, Needham, Shonkwiler, and Stewart do exactly this. If you choose a triangle at random using their method the chance of an obtuse angle is
There are a couple of reasons their approach is particularly pleasing. First, they take into account the can of worms discussed in . Second, we can make use of the geometry of the sphere. Since every point on the sphere corresponds to a triangle, journeys around the sphere are journeys through "triangle space". In particular, great circles give us a way to talk about shortest paths between any two triangles.
Even better, their approach generalizes to other polygons. A triangle is a polygon with three sides. To be slightly fancy, the authors are identifying each triangle with a point in the Grassmannian space Gr(2,3). In a similar way, they can match polygons with n sides with points in the space Gr(2,n). Like the sphere, these spaces have natural ways of measuring distance. This lets the authors study "hexagon space" and "octagon space". You can do cool things like take the shortest path from the letter A to the letter Z in "decagon space":
Or pick a random 20,000 sided polygon:
You can find these animations and more at Clayton Shonkwiler's webpage. He regularly creates cool math animations and I highly recommend you follow him on twitter.
 A nifty method for computing determinants of matrices which, sadly, is hardly ever discussed nowadays. It plays a key role in the 1990s proof of the Alternating Sign Conjecture.
 Also, the probability of an obtuse triangle should be scale invariant. That is, it shouldn't matter if our x and y coordinates are in inches, miles, or lightyears. Or if we turn our head at a 37-degree angle, or look at the plane from above or from below. This is another can of worms we won't open (for now).
 Image from Bill the Lizard at mathoverflow.net. The symmetry of the picture comes from the fact that either x or y could be the smaller number. We did the case when x is smaller (i.e. to the left) of y. If y is smaller, then the side lengths are y, x-y, and 1-x.
 To read more about this problem, check out Martin Gardner's column on the topic. He also discusses the problem of picking a random chord on a circle in which three reasonable methods yield three different outcomes!
 We came across Richard Guy's Law of Small Numbers here at 3QD a few months ago.
 To make the math nicer they assume their stick has length 2. This doesn't have any effect on the outcome.
 Unless, of course, they are exactly antipodal.
Posted by Jon Kujawa at 12:55 AM | Permalink