A Triangle from a Stick

A famous problem in probability is this: Suppose you randomly¹ break a stick in two places. You will get three smaller pieces of stick. What is the probability that you can form a triangle using these pieces?

One interesting thing about this problem is that depending on how you visualize breaking the stick, you get different probabilities.

In this post, we will see two such scenarios. We will also see how we can confirm our answers using Python simulations.

First Scenario

A simple way to break a stick into two is to randomly make two cuts and pull the pieces apart only after both the cuts have been made. The cuts may be like the following:

Or the cuts may be in the opposite order, where Cut 1 comes after Cut 2. Remember that this is possible because we are making both the cuts uniformly at random.

We can assume the length of the stick to be some \(L\). But for computing the probabilities, we can assume, without loss of generality, that the stick is of unit length. Assuming the first cut is at position \(x\) and the second cut is at \(y\), the stick with the cuts would look like something like this:

Or like this:

Now how do we proceed to compute the probabilities? I will give a hint: for three lengths to be the lengths of sides of a triangle, the sum of any two of the lengths should be greater than the third length. (Why this condition is necessary and sufficient? If one side is longer than the other two sides added together, think about how you would draw the triangle using the longest side as the base.)

If you want to give a shot at solving the problem by your own, now is a good time.

In the first case, the lengths of the pieces are \(x\), \(y-x\), and \(1-y\). When we apply the above hint for all the three possible combinations, we get \(x < \frac{1}{2}\), \(y > \frac{1}{2}\), and \(y-x < \frac{1}{2}\). Similarly, for the second case, when \(x > y\), we get \(y < \frac{1}{2}\), \(x > \frac{1}{2}\), and \(x-y < \frac{1}{2}\)

Computing the actual probability is quite easy at this point. Both \(x\) and \(y\) could have any value from the range \([0, 1]\). Out of those we are only interested in those values which satisfy the above conditions. We can use a graph to figure out the proportion of \((x, y)\) which satisfy the triangle property.

In the graph, region (the dashed triangle at the top left) contains the values of \(x\) and \(y\) which form a triangle for the first case. That is, here \(x < \frac{1}{2}, y > \frac{1}{2}\), and \(y-x < \frac{1}{2}\). Similarly, in region B, \(y < \frac{1}{2}, x > \frac{1}{2}, x-y < \frac{1}{2}\). So all the cuts represented in regions A and B form a triangle. And the probability of such cuts is simply the ratio of the areas of regions A and B with the total area. As both regions are just simple right triangles, we can quickly see that the areas of both A and B is \(\frac{1}{8}\). So the total area we are interested in is \(\frac{1}{4}\). Since the total area of the square is just 1, the probability of the cuts forming a triangle is just \(\frac{1}{4}\).

If you are convinced by the argument in the last paragraph, great! In any case, it would be great to be able to conduct some experiment to confirm our calculations. One way to do that would be to take lots of sticks, break them randomly and see whether we are able to form triangles in roughly a quarter of cases. But that is difficult – not just because of the physical exertion involved, but to actually break a stick uniformly at random is difficult for humans. We tend to break sticks more towards the middle. So we go for the better option and ask Python to do the hard work for us.

Python is great for simulating random experiments. In this case the program is particularly simple: all we need to do is to generate two random numbers in the range of \([0, 1]\). These numbers represent our cuts and we can check whether we can form a triangle using them. If a triangle can be formed, we increment a counter. Finally we can take the ratio of the successful instances to the total number of trials to get an estimate of the probability. Now here is the code:

import random as rand

def istriangle(a, b, c):
    return a + b > c and a + c > b and b + c > a

def break_one_stick():
    x, y = rand.uniform(0, 1.0), rand.uniform(0, 1.0)
    if x > y:
        x, y = y, x
    return istriangle(x, y - x, 1 - y)

def count_triangles(num_trials):
    num_triangles = 0
    for i in range(num_trials):
        if break_one_stick():
            num_triangles += 1
    return num_triangles

if __name__ == '__main__':
    trials = 100000
    triangles = count_triangles(trials)
    print("Estimated probability = {0:0.4f}".format(triangles/trials))

For me this code returns 0.2489, 0.2502 etc on different runs. This is a nice confirmation of the mathematical answer.

Second Scenario

Now consider another way to break a stick: you make one cut and take out the first (left) piece. Then you make a cut on the remaining second (right) piece. What is the probability that the three pieces you get in this manner form a triangle?

Here we know that \(y\) is greater than \(x\). So the lengths of the pieces are \(x, y-x, 1-y\). By the triangle condition, we get \(x < \frac{1}{2}\), \(y > \frac{1}{2}\), and \(y - x < \frac{1}{2}\). Rearranging the last equation we get \(y < x + \frac{1}{2}\). In other words, \(x\) ranges from \(0\) to \(\frac{1}{2}\) and \(y\) ranges from \(\frac{1}{2}\) to \(x + \frac{1}{2}\).

Therefore, for any first cut \(x\) with \(x < \frac{1}{2}\), if the second cut \(y\) is from the interval \((\frac{1}{2}, x+\frac{1}{2})\), we will get a triangle. Now, in this scenario, \(y\) is guaranteed to be in the interval \((x, 1)\). Also, as \(x\) is less than \(\frac{1}{2}\), the required interval \((\frac{1}{2}, x+\frac{1}{2})\) is a subset of the interval \((x, 1)\).

Thus for a given \(x\), the probability of \(y\) being in the required range is the ratio of the length of the rquired range to the length of the whole range i.e., \(\frac{x}{1-x}\). Here \(x\) can be any number between \(0\) and \(\frac{1}{2}\). To compute the total probability, we need to integrate with respect to \(x\).

\[\text{Pr(triangle)} = \int_0^{\frac{1}{2}} \frac{x}{1-x} dx\]

This is an easy to evaluate integral which turns out to be exactly \(\ln{2} - \frac{1}{2}\), or approximately \(0.1931\). I am amazed that a problem as simple as this should have an expression involving the natural logarithm as an answer.

Anyway, let us now turn to Python for confirmation. Only one function need to change from the previous code. Here it is:

def break_one_stick():
    x = rand.uniform(0, 1.0)
    y = rand.uniform(x, 1.0)
    return istriangle(x, y - x, 1 - y)

Yes, in fact, the function is now simpler in a sense because we no longer have to check which of \(x\) and \(y\) is larger.

For me, the simulation gives answers like \(0.1931\), \(0.1943\), \(0.1935\), which are very close to the analytical answer.

These two are not the only scenarios possible, by any means. One can think up lots of other ways of cutting a stick. Once the first cut is made, the bigger of the two pieces can be selected for the next cut. Or, the piece for the second cut can itself be selected based on a coin toss. I think all of these scenarios can be solved similarly. In any case simulation of all the scenarios is very easy using Python.