Jump to content
BrainDen.com - Brain Teasers
  • 0

Triangular sticks


bonanova
 Share

Question

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?

Link to comment
Share on other sites

19 answers to this question

Recommended Posts

  • 0

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

  • Upvote 1
Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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 by brifri238
Link to comment
Share on other sites

  • 0

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!

Link to comment
Share on other sites

  • 0

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 by CaptainEd
  • Upvote 1
Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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!

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...