Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The following problem was brought to my attention by a doctoral dissertation on Mathematics Education, but - as far as I know - the solution remains unknown.

I have already asked this question on MSE, where the post has garnered 75 votes, but still no canonical answer in the more-than-half-year since it has been there.

Please add or suggest different tags if it seems warranted.


Randomly break a stick in five places.

Question: What is the probability that the resulting six pieces can form a tetrahedron?

Clearly satisfying the triangle inequality on each face is a necessary but not sufficient condition.

Furthermore, the question of when six numbers can be edges of a tetrahedron is related to a certain $5 \times 5$ determinant, namely, the Cayley-Menger determinant. (See, e.g., Wirth, K., & Dreiding, A. S. (2009). Edge lengths determining tetrahedrons. Elemente der Mathematik, 64(4), 160-170. A more recent article by these authors is cited in the comments below: Wirth, K., & Dreiding, A. S. (2013). Tetrahedron classes based on edge lengths. Elemente der Mathematik, 68(2), 56-64.)

Obviously, this problem is far harder than the classic $2D$ "form a triangle" one. I would welcome any progress on finding a solution or a reference to one if it already exists in the literature.

share|improve this question
2  
I assume that for the tetrahedron there is a difference between the marked (where you say which piece is which edge) and unmarked (where you don't) versions of the question. Which one do you mean? –  Igor Rivin Sep 23 '13 at 19:54
4  
Perhaps this phrasing is clearer: If you randomly choose five different points on the unit interval and cut at each of them, then you will end up with six pieces. What is the probability that such a process will yield six pieces that can somehow be assembled so that they are the edges of a tetrahedron? –  Benjamin Dickman Sep 23 '13 at 20:02
2  
I believe the problem in its original statement was meant only as a higher-dimension analogue of the 2D triangle one. Rephrasing from the linked MO post: "Pick five points uniformly at random on the stick, and break the stick at those points. What is the probability that the six segments obtained in this way form a tetrahedron?" –  Benjamin Dickman Sep 23 '13 at 20:19
5  
The unmarked problem looks much messier than the marked problem. Why not do the case where you specify where each piece goes first? –  Douglas Zare Sep 23 '13 at 22:28
7  
When I tried to solve the marked problem with a Monte Carlo method with $10^{11}$ samples, I got the answer $\frac1{79}$ with relative error of about $4\times10^{-5}$. The marginal expected length of any piece seems to be $\frac16$ (rel.err. $\pm10^{-4}$) with variance of about $\frac1{284}$ (rel.err. $\pm2\times10^{-4}$). Perhaps this might be helpful, especially if someone else checks this too. –  Kirill Sep 30 '13 at 4:23

1 Answer 1

This is far from a complete answer, but it may be helpful progress.

The marked problem, where the numbers are labeled, looks much simpler than the unmarked version. The region of lengths which can be assembled into tetrahedron in some order can be viewed as a union of $6!$ copies of the region for marked lengths, although this can be reduced by the symmetries of the tetrahedron. So, let's look at the simpler case of marked lengths.

There are linear conditions from the triangle inequality on each face of the tetrahedron, plus one quadratic condition from the positivity of the square of the volume. Ignoring the quadratic condition gives us an upper bound on the probability the edges form a tetrahedron.

The collection of $12$ triangle inequalities and one equation, that the sum of the lengths is $1$, produces a $5$-dimensional polytope $P$ which I analyzed with the help of qhull. Given the simplicity of the result, perhaps there is a way to read off the structure more directly. There are $7$ vertices. Four of these vertices give $1/3$ length to the $3$ edges meeting at a vertex, and $0$ length to the other three edges forming a triangle. Three of the vertices give $1/4$ length to a cycle of length $4$, and $0$ length to two opposite edges. If the tetrahedron includes faces with lengths $\lbrace a, b, c \rbrace$ and $\lbrace a, d, e \rbrace$ then the vertices include $(0, 0, 0, 1/3, 1/3, 1/3)$ and $(0, 1/4, 1/4, 1/4, 1/4, 0).$ With only $2$ more vertices than the dimension, the combinatorial structure of $P$ is relatively simple, and is determined by the fact that the convex combination (in fact average) of $4$ vertices equals a convex combination of the other $3$ vertices. Much as the bipyramid in $3$ dimensions can be triangulated with either $2$ or $3$ tetrahedra, $P$ can be triangulated with either $3$ or $4$ symmetric simplices. $P$ is related to the normal disks in a tetrahedron.

The volume of $P$ is $1/54$ of the volume of the simplex of edge lengths summing to $1$. This gives an upper bound on the probability that breaking a stick into marked lengths produces the edge lengths of a tetrahedron, although this is far from the $1/79$ observed numerically by Kirill. It is interesting that the quadratic condition rules out a large fraction of the lengths which satisfy the triangle inequalities.

I think the quadratic condition can be added by considering how the surface intersects the tetrahedra of one of the triangulations of $P$. This is much simpler than taking the intersection of a quadratic inequality with an arbitrary polytope.

share|improve this answer
    
I referred to the last condition as quadratic, but it is higher order. –  Douglas Zare Jan 7 at 23:20
    
I will be interested if there is a way to put in the last condition, and how far down this might bring the bound. It is clear to me that an explicit answer is very hard come-by! Thank you for giving the problem some thought. –  Benjamin Dickman Jan 8 at 15:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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