Conference rusure::math

    I assume that by random is meant that all possible breaking points
    of a rod are equally probable for each act of breaking the rod.  To
    simplify the mathematics, assume that the original rod has length 1.

    Let the length of the rods at the end of the first break be z and
    1-z, where Z=U(0,1).  To simplify further, we choose to keep the
    rod of length z and break the rod of length 1-z.  This is the same
    as picking one of them with equal probability because of the
    symmetry of the uniform distribution.  Now, we break the rod of
    length 1-z randomly into lengths x and y where x+y=1-z
    (or, z=1-x-y).

    To have a valid triangle (I'm including the degenerate cases, but
    the answer is the same if you exclude them), we must have the
    following conditions satisfied:

	x+y >= z,
	x+z >= y, and
	y+z >= x

    Substituting z = 1-x-y into the above inequalities and including
    the conditions imposed by the problem that we not have negative
    rod lengths, we derive:

	x+y >= 0.5
	0 <= x <= 0.5
	0 <= y <= 0.5

    This inequality describes a triangle and its interior in the x,y plane
    that has vertices at (0,0.5), (0.5,0), and (0.5,0.5).  Call this filled
    triangle A.

    Now, x+y = 1-z so for a given z, possible rod breakages lie
    on the line segment from (0,1-z) to (1-z,0), call it line segment
    B.  The probability of getting a triangle when z is known is simply
    the ratio of the length of the line segment that passes through
    filled triangle A (call it line segment C) to the length of line
    segment B.  When z > 0.5, this ratio is 0.  The length of line
    segment B is easily calculated to be (2^0.5)*(1-z).  The length of
    line segment C is (2^0.5)*z.  So the probability of forming a
    triangle for a given z is: z/(1-z).  Integrating:

	( 0.5
	|
	|   z/(1-z) dz  =  ln 2 - 0.5
	|
	) 0

    gives the probability of getting a triangle.

    Re:              <<< Note 1274.0 by AIAG::GREEK "Rad haps, dude!" >>>

>You take a rod of arbitrary length and drop it on the ground, where it
>breaks into two random pieces.  You pick up one of the pieces at random
>and drop it again, where it, in turn, breaks into two random pieces.
>What is the probability that you can form a triangle with the three
>resulting pieces?

    Assume first that "randomly" above means that that the break is
    uniformly distributed across the length of the rod. Start for
    convenience with a rod of unit length.  The first break  divides the
    rod into pieces of length x and 1-x.  Choose the piece x for the second
    break, which divides it into y and x-y.  
    
    From the description of the problem, it follows that the point x,y
    which defines the break lies inside a triangle on the x-y plane, given
    by
    
    	x>0 , x<1 , y<x
    
    Note in passing that the false assumption that the two breaks are
    uniformly distributed in this triangle would have made the problem a
    lot simpler.
    
    The conditions that the three pieces y, x-y, 1-x form a triangle are
    
    	x-y < y + 1 - x
    	y < 1 - x + x - y
    	1 - x < y + x - y
    
    After some algebra these become
    
    	x > 1/2
    	y < 1/2
    	y > x - 1/2
    
    The first condition says that there is a probability 1/2 that the x
    break satisfies the condition.  This is reasonable, since if x is less
    than 1/2, there is no way we can break it to make a triangle.
    
    The probability that y satisfies the second two inequalities for a
    given x (assumed > 1/2 ) is given by the ratio of line segments
    [x-1/2,1/2] and [0,x] 
    
    	P( tri | x ) = ( 1/2 - (x-1/2) ) / x = (1-x)/x
    
    The probability that a triangle can be formed, given that x > 1/2, is
    given by the integral of the probability above from 1/2 to 1.  This is 
    
    	P( tri | x>1/2 ) = ln(2) - 1/2
    
    The answer to the problem is 
    
    	P( tri ) = P( tri | x>1/2 ) * P( x>1/2 )
    
    		 = ( ln(2) - 1/2 ) * 1/2 
    
    		 = 0.0965736 approx
    
    This probability is surprisingly small, so it is worth asking why.  On
    the first break x has to be greater than 1/2.  And for x close to 1/2,
    the second break is very likely to lead to a triangle.  But as x gets 
    closer to 1, the second break is very unlikely to lead to a triangle. 
    So triangles come mostly from the case where x is greater than 1/2 but
    not too much greater.
    1, it becomes very unlikely that you 

	Computer simulation suggests ln 2 - 1/2 as in reply .1,
	as opposed to one-half of that as in reply .2.

	Dan

    Hey, Dan, you're supposed to offer Wally a bet in situations like that...
    
      John

    Re .3 & .1
    
    Agreed. The first thing I did before even thinking the problem, was to
    create simulation.
    
    Results for example with 1000000 iterations:
    193172
    193026
    193321
    193107
    
    Algorithm could be something like this:
    a = rnd
    If a > .5 it won't work
    c = .5 - rnd*(1-a)
    If (c<0) or (c>a) it won't work
    Else we got it! B^}
    
    Toffe

After puzzing over it for a while, I realized that I included the factor of 
1/2 twice, once in the limits of integration and once in the P( x>1/2 ).

The P( tri | x>1/2 ) should have been the integral given divided by the integral
of 1 over the same limits, or 1/2.

    My simulations of the problem show a probability of a triangle as being
    almost exactly 0.25.
    
    In the simulation, I generate two random numbers (0<rnd<1) indicating
    the two break points, b1 and b2 (b1<b2). I then calculate the lengths
    of the three segments formed: (0,b1), (b1,b2), and (b2,1). I count a
    successful triangle if no segment length is greater than 0.5.
    
    The BASIC program follows.
    
    /Dwayne
    

	randomize
	sample_size=100000
	triangles=0
	for i=1 to sample_size
	    b1=rnd
	    b2=rnd
	    if b1>b2 then	! force b1 to be less than b2 by swapping
		t=b1		! them if necessary.
		b1=b2
		b2=t
	    end if
	    segment1=b1
	    segment2=b2-b1
	    segment3=1-b2
	    ok=1		! assume a successful triangle
	    if segment1>0.5
	    then
		ok=0		! rotten triangle
	    end if
	    if segment2>0.5
	    then
		ok=0		! rotten triangle
	    end if
	    if segment3>0.5
	    then
		ok=0		! rotten triangle
	    end if
	    triangles=triangles+ok
	next i
	print
	print "% Triangles = ", triangles/sample_size*100
	end

>    My simulations of the problem show a probability of a triangle as being
>    almost exactly 0.25.
>    
>    In the simulation, I generate two random numbers (0<rnd<1) indicating
>    the two break points, b1 and b2 (b1<b2). I then calculate the lengths
>    of the three segments formed: (0,b1), (b1,b2), and (b2,1). I count a
>    successful triangle if no segment length is greater than 0.5.

	This is not the same problem.   You choose two breakpoints randomly.
The problem under discussion pick one breakpoint randomly, then picks 
one of the two pieces randomly, then picks a second breakpoint on that.

	The problem *you* have addressed with your simulation was treated
in this notesfile about 18 months ago, if my mempry serves me correctly,
and was generalized to n breakpoints.   Implicitly or explicitly, a
barycentric representation is necessary to address the problem.

Cheers,
Andrew.

His program could be modified to do that easily enough, correct?

john

	Re: -.1, yes sure it can be changed.

	Reading through -.2, I think I was a little sharp.   But this is
a problem which notoriously confuses people.   Martin Gardner made an
error in solving this problem when he announced it years ago in the
Mathematical Games column of the Scientific American.

	Another generalization to the problem could be:

	Suppose a stick is broken into six pieces, randomly somehow.

		(1) What is the probability that they can be re-assembled 
		into a tetrahedron? 

		(2) It may be possible that the sticks can be assembled in
		a number of different ways, M.   What values can M take?

		(3) What is the probability that the sticks can be assembled
		in Mmax ways, where Mmax is the maximum value that M can
		take.

Regards,
Andrew.

.10> "Reading through -.2, I think I was a little sharp."
    
    No offense taken. I understand the distinction.
    
    /Dwayne
    

.10>	Reading through -.2, I think I was a little sharp.  
    
    Come on, we all KNOW you're sharp, Andrew...

>        <<< Note 1274.8 by HERON::BUCHANAN "combinatorial bomb squad" >>>
>                           -< not the same problem >-
    
>	The problem *you* have addressed with your simulation was treated
>in this notesfile about 18 months ago, if my mempry serves me correctly,
>and was generalized to n breakpoints.
    
    Can anyone point me to the note referred to here please?
    
    Thanks
    
    Dick

>    Can anyone point me to the note referred to here please?
>    Dick

	967.   Nostalgia!

Andrew.