Triangular sticks

[bonanova]

There is a standard problem that asks, if you randomly break a stick into three pieces, the probability that the pieces can form a triangle. The answer is not unique because there are different ways to randomly create three pieces. The method that is the most challenging to analyze breaks the stick at a random point, randomly chooses one of the pieces, and breaks it at a random point. If you can solve that puzzle you may have insight to solve the following variant:

Break a stick at a random point. Break both pieces at random points. Randomly discard one of the pieces. What is the probability the remaining pieces can form a triangle?

[CaptainEd]

The conditions for trianglehood are that

for sticks of lengths a, b, and c, a triangle results if

(a < b+c) AND (b < a+c) AND (c < a+b)

but you can rework that into

(2a < a+b+c) AND (2b < a+b+c) AND (2c < a+b+c)

let s be the sum a+b+c, then

(a < s/2) AND (b < s/2) AND (c < s/2)

In the case at hand, we have four sticks:

First, we pick p between 0 and 1.
Then, we pick q between 0 and p.
FInally, we pick r between 0 and (1-p).

Thus we have four sticks, of lengths q, (p-q), r, (1-p-r).

When we discard a stick of length x, the sum "s" is (1-x), so the triangle conditions become:

Discard Condition (each remaining stick must satisfy)
q < (1-q)/2
p-q < (1-(p-q))/2
r < (1-r)/2
1-p-r < (p+r)/2

As Bonanova said, I don't get the "Aha!" that causes this to look like the case of "Break once, break again."

[~andy~]

[spoiler spoiler=please use spoilers]100%

[hhh3]

hmm.. well..

a probability of 1 bcoz i cant think of a scenario where 3 pieces of a stick cant mak a traingle

[phil1882]

if a side is longer than the sum of the other two it doesn't form a triangle.

after writing a cpu program, i get roughly 23%.

[hhh3]

oh.. yes.. thanks phil1882... i didnt really think about ""if a side is longer than the sum of the other two it doesn't form a triangle.

"" now it jst bcame a lot more complicated than it first seemed

[~andy~]

Yes, your'e right Phil, i didn't think of that either, without working it out it has to be less than 25%

[Prof. Templeton]

the original problem, if I remember correctly, was more easily solved by evaluating points inside an equilateral triangle whose altitude represented the length of the stick. The three pieces would be the distance from the point to the three sides. A triangle can only be formed from the three pieces if two of them, when added, are not less then the third. The valid points inside the equilateral triangle where this occurs occupy 1/4 of the triangle (think Legend of Zelda Triforce). By discarding one of the pieces, I think we still have the same problem just with a smaller triangle. I will have to think about it more.

[CaptainEd]

I don't feel up to analyzing this right now, so here's the result of 1764 cases. 0.219387755

[bonanova]

Hint:

Solve these problems first:

1. Break the stick at two random points.
   
2. Break the stick at a random point. Break one of the pieces at a random point.
   

These can be solved in closed form; are they the same?

Verify the answers by simulation if you like.

[bonanova]

I don't feel up to analyzing this right now, so here's the result of 1764 cases. 0.219387755

That's close, Cap'n.

10x more cases should get you to 3-decimal-place accuracy.

[CaptainEd]

Thank you, bonanova. I've been feeling dumb and behaving lazy. You've prodded me, so I have an answer for the first of the two.

OK, I see how to analyze "two random breaks", with the following meaning:

pick two random numbers between 0 and 1, call them p and q.

If the stick were broken at those two points, it would become three sticks (assuming p=q is unlikely) of lengths

* min(p,q)

* 1-max(p,q)

* max(p,q) - min(p,q)

For what range of p and q would these three lengths satisfy the requirement that the largest is less than the sum of the smaller two?

The answer is two regions:

1) (q < 0.5) AND (p > 0.5) AND (q > (p - 0.5))

2) (p < 0.5) AND (q > 0.5) AND (p > (q - 0.5))

Their area totals 1/4 of the area from (0,0) to (1,1), so I claim the probability of two random breaks resulting in lengths that can make a triangle is 0.25.

I assume that it is NOT the same as that formed by one random break, followed by a random choice of sides and a random break confined to that side.

But I haven't analyzed that yet.

[bonanova]

Thank you, bonanova. I've been feeling dumb and behaving lazy. You've prodded me, so I have an answer for the first of the two.

OK, I see how to analyze "two random breaks", with the following meaning:

pick two random numbers between 0 and 1, call them p and q.

If the stick were broken at those two points, it would become three sticks (assuming p=q is unlikely) of lengths

* min(p,q)

* 1-max(p,q)

* max(p,q) - min(p,q)

For what range of p and q would these three lengths satisfy the requirement that the largest is less than the sum of the smaller two?

The answer is two regions:

1) (q < 0.5) AND (p > 0.5) AND (q > (p - 0.5))

2) (p < 0.5) AND (q > 0.5) AND (p > (q - 0.5))

Their area totals 1/4 of the area from (0,0) to (1,1), so I claim the probability of two random breaks resulting in lengths that can make a triangle is 0.25.

I assume that it is NOT the same as that formed by one random break, followed by a random choice of sides and a random break confined to that side.

But I haven't analyzed that yet.

Good one. Yes and yes.

Your approach should serve well for the second case as well.

[CaptainEd]

If we break the stick and then choose either piece for a further break: let's call the original break point P. and the length of the other piece is (1-P).

We can break the short end or the long end.

(a) If we break the short end (that is, if p < 0.5) , we are guaranteed to have no triangle, as the long end would be larger than the sum of the other two sides.

So half the time, we will certainly have NO triangle.

(b) If we break the long end (that is, if p > 0.5), we will have a triangle exactly when neither piece is as long as half the original length.

Let's grab a random number Q from 0 to P,

So the left end of the long end is of length Q, the right end of the long end is P-Q.

To compute this, for each P between 1/2 and 1, we need to evaluate

(i) the range of possible Q

(ii) in what fraction of that range is neither piece as long as 1/2.

Q ranges from 0 to P the acceptable range is (P - 1/2 , 1/2), because

If Q is less than P-1/2, then P-Q > 1/2, so no triangle.

Similarly, if Q is greater than 1/2, then no triangle.

More concretely,

when P is nearly 1 (let's say 1 - eps), then this range is (1 - eps - 1/2, 1/2) = (1/2 - eps, 1/2).

In other words, Q ranges from 0 to 1-eps, but the acceptable range is of length eps.

On the other hand, when P is nearly 1/2 (let's say 1/2 + eps), then this range is (1/2 + eps - 1/2, 1/2) = (eps, 1/2).

In other words, Q ranges from 0 to 1/2 + eps, and the acceptable range is of length 1/2 - eps)

So as P goes from 1/2 to 1, the area of Q forms a trapezoid with altitudes ranging from 1/2 to 1 => average altitude of 3/4.

And the acceptable range (the range where the sides could form a triangle) ranges from 0 to 1/2 => average altitude of 1/4.

So the probability of making a triangle by breaking the long end is (1/4) / (3/4) = 1/3.

And, since we only break the long end half the time, the probability of making a triangle is 1/6.

So now I have to figure out the OP--randomly break the stick, then randomly break each piece. Discard one piece. Next time...

[bonanova]

If we break the stick and then choose either piece for a further break: let's call the original break point P. and the length of the other piece is (1-P).

We can break the short end or the long end.

(a) If we break the short end (that is, if p < 0.5) , we are guaranteed to have no triangle, as the long end would be larger than the sum of the other two sides.

So half the time, we will certainly have NO triangle.

(b) If we break the long end (that is, if p > 0.5), we will have a triangle exactly when neither piece is as long as half the original length.

Let's grab a random number Q from 0 to P,

So the left end of the long end is of length Q, the right end of the long end is P-Q.

To compute this, for each P between 1/2 and 1, we need to evaluate

(i) the range of possible Q

(ii) in what fraction of that range is neither piece as long as 1/2.

Q ranges from 0 to P the acceptable range is (P - 1/2 , 1/2), because

If Q is less than P-1/2, then P-Q > 1/2, so no triangle.

Similarly, if Q is greater than 1/2, then no triangle.

More concretely,

when P is nearly 1 (let's say 1 - eps), then this range is (1 - eps - 1/2, 1/2) = (1/2 - eps, 1/2).

In other words, Q ranges from 0 to 1-eps, but the acceptable range is of length eps.

On the other hand, when P is nearly 1/2 (let's say 1/2 + eps), then this range is (1/2 + eps - 1/2, 1/2) = (eps, 1/2).

In other words, Q ranges from 0 to 1/2 + eps, and the acceptable range is of length 1/2 - eps)

So as P goes from 1/2 to 1, the area of Q forms a trapezoid with altitudes ranging from 1/2 to 1 => average altitude of 3/4.

And the acceptable range (the range where the sides could form a triangle) ranges from 0 to 1/2 => average altitude of 1/4.

So the probability of making a triangle by breaking the long end is (1/4) / (3/4) = 1/3.

And, since we only break the long end half the time, the probability of making a triangle is 1/6.

So now I have to figure out the OP--randomly break the stick, then randomly break each piece. Discard one piece. Next time...

You are in the right ball park, but a little low.

Ask where the longer stick must be broken given the first break was at f < .5.

Then average the probability of that second break for 0 < f < .5.

[brifri238]

I have run two simulations, each over 1,000,000 runs.

The first simulates the scenario where one stick is randomly broken and then one of the resulting two sticks is randomly choosen and then randomly broken.

The second scenario simulates where the stick is randomly broken and each of the two resulting sticks are then randomly broken and then one of the resulting four sticks is randomly choosen and thrown away:

Scenario 1: Probability of Sucessful Triangle: 0.19378

Scenario 2: Probability of Sucessful Triangle: 0.19371

Assuming my simulations are correct, it practically makes no difference which scenario is choosen

Edited November 9, 2012 by brifri238

[CaptainEd]

You are in the right ball park, but a little low.

Ask where the longer stick must be broken given the first break was at f < .5.

Then average the probability of that second break for 0 < f < .5.

Some day, when I look back on this, I'll laugh. But right now, my ability to do word problems is not very satisfying. I believe I did exactly what you advised, I clearly graphed some points randomly generated according to this approach, I saw a graph in which the probability is exactly 1/3, yet my Excel spreadsheet continues to show numbers larger than 1/3, as you said (and presumably, as brifri238 says). Thanks in advance for my education in mathematical thinking!

[CaptainEd]

I think I've calculated the second case properly, though it would be gilding the lily to call my calculus proficiency merely "rusty".

Rather than randomly generating a place to break the stick, I'll integrate over all break points.

However, we don't want to break the short stick, as it will never lead to a triangle.

So, let p be the length of the long half of the stick. That is, 1/2 < p < 1.

Then break p at q.

The possible range of q is 0 < q < p, but the admissible range of q is (p-1/2) < q < 1/2, because

if q > 1/2, then q is too long, and

if q < p-1/2, then p-q is too long.

So the admissible fraction is of length (1/2 - (p-1/2)) / p.

So we want integral (1/2 - (p - 1/2))/p from p = 1/2 to 1.

= integral (1-p)/p from p = 1/2 to 1.

= integral (1/p) - integral (1), from p=1/2 to 1

= [ integral (1/p) from p=1/2 to 1 ] - 1/2

= ln(1) - ln(1/2) - 1/2

= 0 +.69315 -.5 = .19315

I sort of expected it to be twice this, so I may have either missed a factor of two, or done something totally irrelevant. Please let me know.

But .19315 fits in with my crude probabilistic simulations, and is close (but not close enough, I fear) to brifri238's results.

Edited November 20, 2012 by CaptainEd

[bonanova]

You got it.

Kudos for hanging in with it.

The missing factor 2 comes when you recognize the integration range is 1/2.

You have to divide by that to get the average over that range.

I didn't notice till now that grifri238's result is a little high..

I got:

After a first break at point a <.5. the second break must be in the central region of width a within the larger [1-a] piece. If you average a/(1-a) over all values of a from 0 to .5 you get

-1 + 2log2 = -1 + 1.386294361... = 0.386294361... Half that is 0.1931471806...

I have not analyzed the variant mentioned in OP.

I'm waiting for the 'aha!' Moment that reduces it to this case.. http://brainden.com/forum/public/style_emoticons/#EMO_DIR#/smile.png

[bonanova]

The conditions for trianglehood are thatfor sticks of lengths a, b, and c, a triangle results if

(a < b+c) AND (b < a+c) AND (c < a+b)

but you can rework that into

(2a < a+b+c) AND (2b < a+b+c) AND (2c < a+b+c)

let s be the sum a+b+c, then

(a < s/2) AND (b < s/2) AND (c < s/2)

In the case at hand, we have four sticks:First, we pick p between 0 and 1.Then, we pick q between 0 and p.FInally, we pick r between 0 and (1-p).Thus we have four sticks, of lengths q, (p-q), r, (1-p-r). When we discard a stick of length x, the sum "s" is (1-x), so the triangle conditions become:Discard Condition (each remaining stick must satisfy) q < (1-q)/2 p-q < (1-(p-q))/2 r < (1-r)/2 1-p-r < (p+r)/2As Bonanova said, I don't get the "Aha!" that causes this to look like the case of "Break once, break again."

Very nice Cap'n!