89
$\begingroup$

There is a standard problem in elementary probability that goes as follows. Consider a stick of length 1. Pick two points uniformly at random on the stick, and break the stick at those points. What is the probability that the three segments obtained in this way form a triangle?

Of course this is the probability that no one of the short sticks is longer than 1/2. This probability turns out to be 1/4. See, for example, problem 5 in these homework solutions (Wayback Machine).

It feels like there should be a nice symmetry-based argument for this answer, but I can't figure it out. I remember seeing once a solution to this problem where the two endpoints of the interval were joined to form a circle, but I can't reconstruct it. Can anybody help?

$\endgroup$
4
  • $\begingroup$ This seems to be related to a recent math.stackexchange question: math.stackexchange.com/questions/72977/… $\endgroup$ Nov 2, 2011 at 16:10
  • $\begingroup$ This problem was presented to me a couple of days ago. I just wrote a little blog post explaining my solution, which ends with a symmetry argument. $\endgroup$
    – aioobe
    Dec 30, 2015 at 20:36
  • 5
    $\begingroup$ so here is the simple solution - divide a line into 6 parts of length 1/6 each. without loss of generality, the largest broken part will be greater than or equal to 1/3. So the largest part can lie in segments 3,4,5 or 6. Only 1 of these 4 portions will result in a triangle (since segments 4,5,6 will result in largest part being > 1/2). Ergo, 1/4 probability. $\endgroup$ Feb 10, 2016 at 12:32
  • $\begingroup$ Here's a nice argument: Let the length of the pieces be x, y, and 1-x-y. To form a triangle, each of x,y, and 1-x-y must be less than 1/2. A triangle is not formed iff the two cuts are on the same side of a midpoint. The probability that a given cut is on right side of the midpoint is 1/2, so the probability that both cuts are on the right side is simply 1/2 * 1/2 = 1/4. Imagine the two cuts as three cuts on a circle, where one of the cuts is to straighten it out. All three pieces have 1/4 probability of being longer than half. Hence, probability of triangle formation is: 1 - 3*1/4 = 1/4. $\endgroup$
    – kushal
    Nov 27, 2021 at 6:46

13 Answers 13

120
$\begingroup$

Here's what seems like the sort of argument you're looking for (based off of a trick Wendel used to compute the probability the convex hull of a set of random points on a sphere contains the center of the sphere, which is really the same question in disguise):

Connect the endpoints of the stick into a circle. We now imagine we're cutting at three points instead of two. We can form a triangle if none of the resulting pieces is at least 1/2, i.e. if no semicircle contains all three of our cut points.

Now imagine our cut as being formed in two stages. In the first stage, we choose three pairs of antipodal points on the circle. In the second, we choose one point from each pair to cut at. The sets of three points lying in a semicircle (the nontriangles) correspond exactly to the sets of three consecutive points out of our six chosen points. This means that 6 out of the possible 8 selections in the second stage lead to a non-triangle, regardless of the pairs of points chosen in the first stage.

$\endgroup$
2
  • 4
    $\begingroup$ That doesn't seem like the argument I remember, but it's satisfying nonetheless. $\endgroup$ Oct 23, 2009 at 2:47
  • $\begingroup$ For the above-mentioned result about spheres, see math.stackexchange.com/questions/1400/… $\endgroup$
    – ACL
    Nov 23, 2011 at 8:28
65
$\begingroup$

Consider an equilateral triangle with altitude 1. It is not hard to show that if you choose a point randomly in this triangle, the distances to the three sides gives the same distribution of lengths that you obtain by breaking a stick at two random points. Now, the locus of points for which no distance is longer than 1/2 is the smaller equilateral triangle formed by joining the midpoints of the edges, which has area 1/4 that of the original triangle.

triangle figure

$\endgroup$
5
  • 13
    $\begingroup$ I can't quite see this statement that isn't hard to show. Hint? $\endgroup$ Jun 3, 2011 at 14:14
  • 1
    $\begingroup$ @Qiaochu: Suppose you know the length ℓ of one of the three pieces. What is the distribution of the remaining two? In the triangle version, this corresponds to keeping the middle point the same height above the base, which yields a uniform distribution from 0 to 1−ℓ of the length of the second piece. In the original question, this corresponds to keeping the length of one of the three intervals fixed, and it is easy to see that this gives a uniform distribution on the length of the other two intervals. $\endgroup$
    – Peter Shor
    Jun 4, 2011 at 11:22
  • 1
    $\begingroup$ @Qiaochu (continued): In this case, the knowledge of the marginal distribution of the other two pieces, given the length of one, determines the distribution. You can see this because the stochastic process of holding the length of one edge fixed, then randomly selecting the lengths of the other two, and then repeating with the length of a different edge fixed, is essentially the same as the Metropolis algorithm for uniformly sampling points inside the triangle. $\endgroup$
    – Peter Shor
    Jun 4, 2011 at 11:22
  • 3
    $\begingroup$ @Qiaochu: The distances correspond to the barycentric coordinates of the point. More generally, choosing a point uniformly in a $k$-simplex corresponds to independently uniformly choosing $k$ points in the unit interval and using the resulting $k+1$ interval lengths as barycentric coordinates. $\endgroup$
    – joriki
    Mar 9, 2013 at 1:54
  • 4
    $\begingroup$ @QiaochuYuan Just take the three vertices of the triangle to be $e_i$, $i=1, 2, 3$ in $\mathbb R^3$. $\endgroup$
    – Fan Zheng
    Nov 27, 2015 at 6:44
50
$\begingroup$

A triangle is possible iff no part is $>{1\over2}$. With probability ${1\over2}$ both cuts are on the same side of the midpoint $M$, in which case no triangle is possible. If the cuts $x$ and $y$, $\ x < y$, are on different sides of $M$ then with probability ${1\over 2}$ the point $x$ is further left in its half than $y$ is in the right half. In this case there is no triangle possible either. It follows that only ${1\over 4}$ of all cuts admit the forming of a triangle.

$\endgroup$
1
  • 2
    $\begingroup$ Some other solutions are ingenious but this one is the SIMPLEST(!). Well done. $\endgroup$
    – Wlod AA
    Feb 13, 2019 at 5:02
21
$\begingroup$

Is the argument you remember along the lines of: picking three points on a circle, what is the probability they lie in the same semicircle?

The problem is discussed here:

http://godplaysdice.blogspot.com/2007/10/probabilities-on-circle.html

$\endgroup$
1
  • 143
    $\begingroup$ This would be the part where I, somewhat embarrassedly, point out that I wrote that. $\endgroup$ Oct 23, 2009 at 4:13
12
$\begingroup$

Yes, here's a nice and beautiful argument!

First you should draw a picture of axes a and b. You're asked to select uniformly a point in the square [0,1]x[0,1]. Now because of the symmetry (sic!) it's equivalent to choosing the points a and b uniformly in the triangle cut from the square by b > a.

So you're actually uniformly selecting a point inside triangle defined by lines a>=0, b<=1, 'b>=a'.

Now let's find the conditions to be able to make a triangle of short sticks. We should have a + (1-b) > b-a, b-a + (1-b) > a and b > 1 - b which indeed, as you say, boils down to

b > 1/2,  a < 1/2,  b-a < 1/2  

It remains to note that those lines create inside the big triangle a small triangle which is similar to big but with all lengths 1/2 of the big, so this small triangle has area of exactly 1/4 of original!

$\endgroup$
4
  • $\begingroup$ "First, the way you define the probability, because of the symmetry (sic!) it's equivalent to first choosing first point a uniformly and then second point b uniformly on [a, 1]." I don't think that this is the case. In the original problem, the probability that there was a piece longer than 1-epsilon decayed like C/epsilon^2 as epsilon tended to 0 (a necessary condition is that no cut lies in (epsilon, 1-epsilon). In your model, it decays like c/epsilon (a sufficient condition is to have A larger than 1-ep). $\endgroup$ Oct 23, 2009 at 4:35
  • $\begingroup$ Yes, you were right to point my mistake. The geometric picture is correct, but I referred to it incorrectly. Will edit. $\endgroup$ Oct 23, 2009 at 15:57
  • 5
    $\begingroup$ Just rephrasing your argument: One can partition the 2-dim simplex, defined by x>=0, y>=0, z>=, x+y+z=1 into 4 identical triangles defined by adding the conditions: 1) x>=&frac12; 2) y>=&frac12; 3) z>=&frac12; 4) x<=&frac12; and y<=&frac12; and z<=&frac12; of which the 4th is the event that you can form a triangle. $\endgroup$ Nov 4, 2009 at 4:09
  • $\begingroup$ Great way to say it indeed. $\endgroup$ Nov 4, 2009 at 20:59
9
$\begingroup$

One reference for a solution to this problem is Carlos d'Andrea and Emiliano Gomez, "The broken spaghetti noodle", American Mathematical Monthly 113 (2006), p. 555, JSTOR, author's website (Wayback Machine). More generally the probability that an interval broken at n-1 points chosen uniformly at random is broken into pieces which can be rearranged to form an $n$-gon is $1 - n/2^{n-1}$.

$\endgroup$
3
  • $\begingroup$ There's something missing in your last sentence: $1-n/2^{n-1}$ is the probability of what event? $\endgroup$ Jun 25, 2010 at 20:00
  • $\begingroup$ Mark, thanks! That's what I get for writing MathOverflow answers on an iPhone. (I was flipping through an old issue of the Monthly and wasn't near a computer.) $\endgroup$ Jun 26, 2010 at 0:48
  • 1
    $\begingroup$ Both Kevin Costello's argument and mine can be adapted to give the $1-n/2^{n-1}$ answer in the general case. $\endgroup$
    – Peter Shor
    Jun 4, 2011 at 15:40
8
$\begingroup$

It seems natural to rephrase the question in terms of barycentric coordinates in a triangle. These coordinates are numbers $x$, $y$, $z$ in the interval $[0,1]$ satisfying the equation $x+y+z=1$. We are looking for triples $(x,y,z)$ of such numbers satisfying the three triangle inequalities $x \le y+z$, $y\le x+z$, and $z\le x+y$. Replacing the relations "$\le$" by "$=$", we get line segments joining the midpoints of the edges of the triangle. These line segments cut the triangle into four congruent subtriangles. The central one of these four subtriangles is the region where all three triangle inequalities hold, and this region has area equal to one quarter of the area of the big triangle.

This is essentially the same argument as in the answers by Peter Shor and Ilya Nikokoshev, particularly in the reformulation of the latter answer in Ori Gurel-Gurevich's comment

$\endgroup$
6
$\begingroup$

More analytical option;

Without loss of generality assume that i) the stick is the $[0,1]$ interval, ii) and the first breaking point $x$ is chosen uniformly randomly in $[0,0.5]$. Now for each $x$ the next point $y$ should be in $[0.5,x+0.5]$ to guarantee the triangle. The probability of such choice is $x$. Then one can apply Bayes with $f(x)=2$ and $f(y|x)=x$: $$ \Pr\{\text{Triangle Making} \}=\int_0^{0.5} {2}{x}dx=\frac{1}{4} $$

$\endgroup$
2
  • 4
    $\begingroup$ what is f here? Please explain a little the application of Bayes theorem. $\endgroup$
    – Supriyo
    Aug 10, 2014 at 8:19
  • $\begingroup$ This was my solution: easy, direct, and not much risk to be wrong with "equivalence" reasoning. But I don't know anything about Bayes' theorem. After searching a bit, this seems like the law of total probability applied to a continuous distribution (here, uniform). But perhaps that's an equivalent way of saying things. $\endgroup$
    – vinc17
    Mar 28, 2020 at 22:17
6
$\begingroup$

Here's how I explained it in my blog post a few years ago, as a step in solving a related 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$

x to the left of y

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

x 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.

plot of inequalities

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.

$\endgroup$
2
  • $\begingroup$ This seems to be the solution which is linked in the question. (But it is definitely better to have it posted also here, in the case of link rot.) $\endgroup$ Jul 15, 2016 at 20:14
  • $\begingroup$ @MartinSleziak Ah, you're right. I could have saved myself the trouble if I'd bothered to read the linked solution (or if it had been posted as part of the question). $\endgroup$ Jul 15, 2016 at 20:48
4
$\begingroup$

The problem is indeed choosing uniformly randomly two points $x,y$ on the interval $[0,1]$ such that the length of each sub-interval is less than $\frac{1}{2}$. This is equivalent to probability that two points chosen uniformly randomly on the interval $[0,1]$ fall into the interval $[0,\frac{1}{2}]$ which is $\frac{1}{2}\times\frac{1}{2}=\frac{1}{4}$.

To see this, it is clear that one point, say $x$, should be in $[0,\frac{1}{2}]$ and another one, say $y$, in $[\frac{1}{2},1]$. Now translate $y$ backward by $\frac{1}{2}$ to the point $y'$. Now $y'<x$ for the desired event, i.e., for the case of having the length of each sub-interval less than $\frac{1}{2}$. This means each desired event is equivalent to having two points in $[0,\frac{1}{2}]$ and translate the first one by $\frac12$.

$\endgroup$
4
$\begingroup$

Let AB be the stick. WLOG we may assume AB=1(Since the probability won't depend on the length of AB). Let the points at which the stick is broken be P and Q.

$AP=x$, $PQ=y$ and $QB=z$.

Since $0\leq AP,PQ,QB \leq 1$ we need to consider all the points inside the $1\times 1\times 1 $ cube. Furthermore the points lie on the x+y+z=1 plane.

x+y+z=1 plane(click on the link to see the image of the plane)

On applying the triangle inequalities (i.e $x+y>z,y+z>x\text{ and }x+z>y$) we find that the net area of points satisfying the condition of forming a triangle is the shaded potion.

Shaded Area(Click on the link to see the shaded area)

Since the points $J,K,I$ are the midpoints of the sides of the of the triangle ACE.The probability = $\dfrac{\text{Area of }\Delta JKI}{\text{Area of }\Delta ACE}=\dfrac{1}{4}$

$\endgroup$
2
4
$\begingroup$

A proof without words that Pr(x < 1/2, y < 1/2, z < 1/2 given that x + y + z = 1) = 1/4 is as follows:

enter image description here

$\endgroup$
-1
$\begingroup$

SOLUTION USING ONLY ORIGINAL LINE: Call the end points A and B and the midpoint M. Let N be the midpoint of MB. Call P the first random point and Q the second. In full generality, we can consider P as lying between M and B. On AM, let H be the point for which HP is half the length of the original stick. For the 3 sticks to make a triangle, it is necessary and sufficient that the total length of any 2 sticks be greater than the third. Therefore no piece can exceed half the length of the original stick. That tells us immediately that Q cannot lie on AH or PB, immediately eliminating half the possible points for Q. Likewise all points on MP are also eliminated. Only points on HM qualify as possible Q points. If we let AB=1, the probability that the 3 sticks can form a triangle is then the average length of HM for all Ps. Note that if P=N, the midpoint of MB, then HM=MP, so the qualifying HM points comprise 1/4 the length of the stick and p=1/4 that a triangle can be formed after randomly choosing a Q for this P. Similarly, for every P to the right of N there is a matching P an equal distance to the left of N, so that the average probability (HM length) for these two Ps is 1/4. That yields an overall average probability for all Ps of 1/4.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.