2024-04-14
You have a stick. Randomly break it into three pieces. What is the probability that the three pieces can form a triangle?
This is a classic interview question, at least in certain circles at a particular time in history. I remember it vividly because, despite first seeing it as a student in Martin Gardner* and knowing the answer, I failed to produce a convincing mathematical argument when I was asked this as an interview question years later! (Instead I wrote pseudocode to get the answer through simulation, which must have satisfied my interviewers; I worked there for four years.)
This problem is fun because it has two different interpretations that lead to different answers. The first interpretation lends itself to a geometric solution; there are a couple of ways to tackle it, and I thought this would be a good example for experimenting with browser-based diagramming tools in the style of TikZ. The second interpretation of the problem is trickier to analyze — I repeatedly ran in to the same error as Gardner as I worked on writing it up, and I think that even Gardner’s “corrected” explanation is not correct — it looks like a case of getting the right answer through the wrong reasoning. The explanation for the second interpretation below is different, and longer, than Gardner’s, but at least I convinced myself!
Select two points independently, uniformly at random, on the stick, and break it at those two points.
In this case, we’ll turn the problem into a geometric construction by showing that “randomly breaking the stick into three pieces” is one-to-one with randomly selecting a point within an equilateral triangle.
Take the three pieces of the stick and arrange them into a “Y” so that one end is touching and they’re separated by angles of 120°. Note that if you draw a perpendicular line at the end of each stick, it creates an equilateral triangle that circumscribes the pieces. (You can be certain it’s equilateral by examining any of the three quadrilaterals — interior angles must sum to 360°, and there are two 90° angles and one 120° by construction, forcing the last one to be 60°.) The altitude and area of this triangle are determined by the sum of the length of the pieces (Viviani’s theorem), so the triangle is the same regardless of how the original stick is broken. Going the other way, suppose you start from the equilateral triangle and randomly select a point within it. Draw the distances from the point to each side, and break the stick accordingly. So, “breaking the stick randomly into three pieces” is the same as randomly selecting a point within an equilateral triangle with an altitude equal to the length of the stick.
The three pieces can themselves be formed into a triangle if and only if the sum of the lengths of any two pieces is greater than the third. So note that if the selected point \(P\) is more than half of the altitude from the bottom of the triangle, the condition can’t hold — one piece is using more than half of the total length. And this argument applies equally to each corner or base of the triangle. So the only region within the triangle that satisfies the condition is a smaller inverted triangle, itself equilateral:
In other words, the overall triangle is divided into four parts, and the condition holds in one part, so the answer to the original question is ¼.
OR! Breaking the stick is one-to-one with selecting \(x\), \(y\), \(z\) at random subject to the constraints that \(x+y+z=1\) and all are positive, which is the same as picking a point at random on the simplex. For the condition to hold, all three must also be less than ½. Intersecting the simplex with the three planes thus defined gives the shaded region.
Select a point at random and break the stick. Select one of the two pieces at random; select a new point at random on this piece and break it again.
Make the first break, and let \(x\) be the length of the left-hand piece. Now we randomly select a piece for the second break, and then randomly select a breakpoint. The total probability that we can form a triangle at the end is
P(break left) P(triangle | left) + P(break right) P(triangle | right)
P(break left) and P(break right) are both \(\frac{1}{2}\). To calculate the other terms, look at P(triangle | right) first. Assume that we select the right-hand piece for the second break, and let \(y\) be the length of the middle piece after the second break. Now we have three pieces with lengths \(x\), \(y\), and \(1-x-y\). The question is, what’s the probability that the choice of \(y\) allows us to form a triangle? The size of the set of possible choices for \(y\) is \(1-x\), and to form a triangle we need all three of the triangle conditions to be true:
\[\begin{align}x+y &> 1-x-y\\ x+1-x-y &> y\\ y+1-x-y &> x\end{align}\] Or,
\[\begin{align}y &> -x + \frac{1}{2}\\ y &< \frac{1}{2}\\ x &< \frac{1}{2}\end{align}\]
Visually:
The vertical line shows the possible choices for \(y\) given a particular value of \(x\), and the heavy vertical line shows those choices that lead to a triangle. So in other words, for any particular value of \(x\), the probability that the choice of \(y\) leads to a triangle is \(\frac{x}{1-x}\). To get the total probability, integrate this expression over the possible values of \(x\). Note that, when \(x > \frac{1}{2}\), the probability that the choice of \(y\) leads to a triangle is \(0\) (since it violates the third inequality), so the integral should only be evaluated up to \(\frac{1}{2}\).
\[\int_0^{1/2} \frac{x}{1-x} dx = \ln(2) - \frac{1}{2}\]
Call this value \(p_\Delta\). A similar argument shows that P(triangle | left) is also \(p_\Delta\), and so the final answer, using P(break left) P(triangle | left) + P(break right) P(triangle | right), ends up being \(\frac{1}{2} p_\Delta + \frac{1}{2} p_\Delta\), and so the grand total final answer is at last
\[p_\Delta = \ln(2) - \frac{1}{2} \approx 0.19315\]
Always the quickest way to get the answer.
from random import random
def sample():
x1 = random()
x2 = 1 - x1
if random() < 0.5:
cut2 = x1 * random()
a = cut2
b = x1 - cut2
c = x2
else:
cut2 = x2 * random()
a = x1
b = cut2
c = x2 - cut2
return (a, b, c)
def check_sample(a, b, c):
return (a + b) > c and (a + c) > b and (b + c) > a
tmp = []
for _ in range(100_000):
tmp.append(check_sample(*sample()))
sum(tmp) / len(tmp) # >>> 0.19345