Tuesday, August 25, 2009

The Broken Stick Revisited

In my earlier post The Broken Stick Experiment, I introduced a problem I had seen in a BLOSSOMS video lecture of the same name. The problem asks
If you break a stick randomly in two places, what is the probability that you can form a triangle from the three pieces?
If you watched the video or ran the simulation code I provided, you found out that the probability of forming a triangle by chance is 25%.

Reader Tom Raywood asks, "Do obtuse triangles count here, or is the solution limited to acute?" The answer to that question is that the solution accounts for triangles of all types, acute, obtuse, and even right triangles. When you break the stick randomly, any of the three are possible (although, as we'll see, right triangles are so unlikely that the probability of getting one randomly is effectively 0).

This question piqued my curiosity enough to investigate another related question.

What proportion of the resulting triangles from the broken stick experiment will be obtuse?

I decided to modify the simulation program to find out the answer.

The first question I had to answer was "How do you tell if a triangle is acute or obtuse?" The easy way is look at it and see if it contains one angle greater than 90° (the definition of an obtuse triangle). However, in the original experiment we only know the lengths of the three sides of the triangles, and none of the angles. It seemed unnecessary to compute all three angles just to see if the triangle was acute or obtuse, although this approach is not totally infeasible. Fortunately, there's an easier way.

We all know from the Pythagorean Theorem that for a right triangle

a2 + b2 = c2

That is, if one angle is exactly right (90°), the sum of the squares of the two sides adjacent to that angle will be exactly the same as the side opposite that angle.

But if the angle changes (while the two sides a and b stay the same length) then the relationship changes as well. If you open the angle up, side c (and its square) gets larger. If you close the angle, side c (and its square) gets smaller. Meanwhile, the sum of the squares of sides a and b stays the same. This leads to the following relationships for acute and obtuse triangles:

If the triangle is acute:
a2 + b2 > c2

If the triangle is obtuse:
a2 + b2 < c2

Using those relationships, I modified the simulation to count how many of the resulting triangles were acute, obtuse, and right triangles.
import java.util.Arrays;import java.util.Random;public class BrokenStickRevisited{ public static void main(String[] args) {     Random random = new Random();     int trials = 1000000;     int triangles = 0;     int acute = 0;     int obtuse = 0;     int right = 0;     double[] breaks = new double[2];     double[] sides = new double[3];     for( int i=0; i < trials; ++i )     {         breaks[0] = random.nextDouble();         breaks[1] = random.nextDouble();         Arrays.sort(breaks);         sides[0] = breaks[0];         sides[1] = breaks[1] - breaks[0];         sides[2] = 1.0 - breaks[1];         Arrays.sort(sides);         if( sides[2] < (sides[0] + sides[1]) )         {             triangles++;             double aSquared = sides[0] * sides[0];             double bSquared = sides[1] * sides[1];             double cSquared = sides[2] * sides[2];             if( aSquared + bSquared > cSquared )             {                 acute++;             }             else if( aSquared + bSquared < cSquared )             {                 obtuse++;             }             else // highly unlikely, but still...             {                 right++;             }         }     }     System.out.println("Triangles: " + triangles);     System.out.println("Acute: " + acute);     System.out.println("Obtuse: " + obtuse);     System.out.println("Right: " + right);     System.out.println("Trials: " + trials);     double p = (double)triangles / trials;     System.out.println("Proportion: " + p);     double pAcute = (double)acute / triangles;     double pObtuse = (double)obtuse / triangles;     System.out.println("Acute Proportion: " + pAcute);    System.out.println("Obtuse Proportion: " + pObtuse); }}
I let the simulation run for 1,000,000 trials to be sure I get a result accurate to three decimal digits. I ran the simulation several times, and never got a single right triangle. That's not surprising, since we knew the odds were quite against it from the beginning.

The proportion of triangles that were obtuse was 0.682, or about 68.2%. The rest (about 31.8%) were acute triangles. This seemed like a strange result. I was hoping for a nice even proportion like the 1/4 probability we got for generating a triangle from the first broken stick problem. It took a bit of exploration for me to explain the result. Read on if you're still curious.

In order to explain the odd proportion we got from the simulation, I need to start with the solution to the original problem. If we break the stick at two random points, x and y, the three resulting pieces will have lengths x, (y - x), and (1 - y) if x is to the left of y

and y, (x - y), and (1 - x) if x is to the right of y

The three pieces form a triangle if none of the pieces is greater than half the length of the stick. In other words, if

(y > 1/2) and (x < 1/2) and (y - x) < 1/2

when point x is to the left of point y (first image above), and

(x > 1/2) and (y < 1/2) and (x - y) < 1/2

when x is to the right of y (second image above). If we plot all six of these inequalities we get the area that represents the proportion of triangles formed from our broken stick.

The shaded regions representing the conditions that form a triangle add up to 1/4 of the total area, or a 0.25 probability of forming a triangle. Now all we need to do to explain the odd results of the second simulation is figure out how much of these shaded regions represent an obtuse triangle and how much represents an acute triangle.

In order to do that, we can plot the inequalities we used earlier that were derived from the Pythagorean Theorem. Since any of the three pieces of our broken stick could be the longest piece, and either break x or break y could be to the left of the other, we need to plot six different inequalities. We get these inequalities by substituting our stick lengths for the values a, b, and c in the Pythagorean Theorem.

Substituting each of the three lengths x, (y - x), and (1 - y) for each of the values a, b, and c in the Pythagorean equation

a2 + b2 = c2

gives us the following equations

x2 + (y - x)2 = (1 - y)2
x2 + (1 - y)2 = (y - x)2
(y - x)2 + (1 - y)2 = x2

Similarly, substituting the three lengths y, (x - y), and (1 - x) for the values a, b, and c gives the remaining three equations

y2 + (x - y)2 = (1 - x)2
y2 + (1 - x)2 = (x - y)2
(x - y)2 + (1 - x)2 = y2

Utilities like the Online Equation Solver or QuickMath's equation solver come in handy for solving the equations for y before plotting them in a spread sheet or on a graphing calculator. If you add the plots for the six new equations to the existing plot you should see something like the following illustration.

The small region in the center of each of the two triangles in the plot represent the probability of the broken stick forming an acute triangle. The remaining areas near the edges of the the triangles sum to the probability of forming an obtuse triangle. Using integration to find the area of the bounded areas shows that these values are within a small margin of error of the probability we arrived at using the simulation program. (This post is already a little long, so calculating the integral of the bounded areas is left as an exercise for the reader.)

Related: If you liked this post, Professor Gilbert Strang shows several different approaches to a very similar problem in another BLOSSOMS video lecture, Are Random Triangles Acute or Obtuse? In that lecture all random triangles are considered, not just those constructed from the pieces of a broken stick.

mWm said...

Amazing post and conclusions :)

You also have Wolfram|Alfpha to get those plots and equations solved.

Bill the Lizard said...

mWm,
I use Wolfram MathWorld all the time, so I don't know why I didn't think to try WolframAlpha. I just tried one of the equations from this post, and it looks to be better in a couple of ways. Not only does it plot the solution for you, it also allows you to plot inequalities. Thanks a lot for pointing this out, I'll definitely be using it in the future.

mWm said...

They did an amazing job with it. I use Mathematica allot on the university and then discovered WolframAlpha. Very useful.

Love your "puzzle" solvers. Keep up!

Edu said...

Hey,

I briefly glazed at first through your post and I saw that wonderful triangle. I was very amazed to realize that you get that wonderful shape just with the simple rule of the probability of getting an obtuse triangle.

Btw that is a triangle in hyperbolic geometry, maybe you can get something else trying to relate hyperbolic geometry and the broken stick problem. Also you can try it for a plane instead of a line, then you will get 3D forms and probably much more things to explore with (just some ideas).

Really good post, thx!