| I allege that with n sticks, the probability that an n-gon can be
formed is:
1 - n/2^(n-1)
Can I convince you of this?
First let's tighten up the problem. Let's assume that there are
n-1 independent identically distributed random variables, uniformly
distributed between 0 and 1. Call these x_i, where i=1..n-1. Let's derive
n-1 other variables y_i, where i=1..n-1, such that {x_i} = {y_i}, and
y_i >= y_(i-1) for all i= 2..n-1. Ie. y_i are the *ordered* x_i.
Derive *another* set of n variables z_i, with z_1 = y_1, z_i = y_i - y_(i-1)
for i=2..n-1, and z_n = 1 - y_(n-1).
These z_i are the lengths of the sticks that we get. Gee, all that
notation! All I'm saying is pick n-1 points independently in the unit line,
and define the lengths that way. Oh, yes, without loss of generality, we'll
take the primordial stick to be of length 1.
(There are other different interpretations of "randomly breaking a
stick", which would lead to different answers. Eg: break the stick in two,
pick a bit, and break that in two).
Now when can we *not* form a triangle. Exactly when for some I,
z_I > �. One thing makes things easier for us: z_I > � & z_J >� => I=J,
because the length of our stick is 1. I claim that the probability that
Z_I > � is 1/2^(n-1). From this, the result we're looking for follows
immediately.
The really neat proof involves drawing an n-1 dimensional "cube", where
each side corresponds to on of the x_i varying from 0 to 1. Then I cut it
into (n-1)! segments, like an orange (eg ordinary 3-dimensional cube splits
into six segments). Each cut contains the major diagonal, and is along the
hyperplane x_i = x_j, for some i. (I hope I mean hyperplane: I mean a
surface of dimension one less than that of the space were in: ie. line in
2-space, a plane in 3-space, etc...)
In any one segment, S, the x_i have a constant ordering, so we can
assign y_i to the axes, for that segment only. (Forget about all the other
segments for a minute). The hyperplane z_I = � is parallel to the two
hyperplanes z_I = 1, which is a single point,P, in S, and z_I = 0, which
is one of the boundaries of S. z_I = � lies exactly halfway between the other
two hyperplanes. z_I = � therefore splits S into 2 portions, and by simple
congruence, the ratio between the size of the portion containing P and the size
of the whole of S, is 1/2^(n-1).
This is true for all S, and for all I, so by summing we get the desired
result.
For those who are trying to follow I suggest that you draw pictures
for n=3 and 4 to see what I'm getting at. Each segment is a simplex
(line segment, triangle, tetrahedron ...) with n vertices and n boundary
hyper-planes. The permissible region for forming a triangle with the n sticks
is the simplex "with each of the corners snipped off, half way down" and so
is a region with at most 2*n bounding hyperplanes, and exactly n*(n-1)/2
vertices. So for instance with n=3,4, the permissible region in each segment
is a triangle, octohedron, respectively.
Returning to the sticks: the formula gives us that for n=3,4,5 the
probability of the sticklets triangulating is �,�,11/16, respectively. The
probability converges rapidly to 1 as n increases, as expected.
Andrew.
|