Saturday, July 30, 2005

It's math puzzle time again.

Good Lord, it seems like forever since we've had a math-type puzzle so, without further ado: Given two points selected entirely at random on a stick, if you break the stick at those two points, what are the odds that the resulting three pieces can form a triangle?

Solutions accepted starting Saturday at noon. Until then, keep it to yourself.

OPEN FOR SOLUTIONS. Once you solve this one, we'll move on to the next one.

: The correct answer is 1/4, and the best way to figure this out is to solve the problem in two stages.

Say the stick is 1 "unit" long. First, it should be obvious that you can build a triangle iff (if and only if) none of the resulting three pieces is longer than .5 units. And the only way that can happen is if the two randomly-selected points lie on opposite sides of centre, and the chance of that is 1/2. So far, so good? But, of course, that's not enough. (This first observation means that you can at least claim that the probability is no better than 1/2.)

In addition to both points lying on opposite sides of centre, it should be obvious that they can't be further apart than .5 units as well. If your randomly-selected points were, say, .1 and .9, it's clear you'd be hosed. So this means you have to further calculate the odds that the two points are within .5 of each other.

Effectively, this is solving a new, second problem. The first problem was, what are the odds that the points are on opposite sides of centre? And we've already solved that: 1/2.

The second problem: Given that the points are already on opposite sides, what are the odds that they're within .5 of each other? Turns out, that's also 1/2. (That second part is left as an exercise for the reader, but Jeff in the comments section does a pretty good job of explaining it.)

Ergo, the final probability is the product of those two values: 1/2 x 1/2 = 1/4.

(The ambitious might want to read more here.)


M@ said...

I think I've got this one. Glad to have another math problem! One of the last ones had everyone in my office talking for some time.

CC said...

Hmmm ... which one was that? It's been a while.

Jon Dursi said...

Huh; I get 1/8, which is much lower than I would have expected. Do I have to show my work?

CC said...

"Do I have to show my work?"

Well, since 1/8 is wrong, that might be a good idea.

Jon Dursi said...

I'd disagree; if 1/8 is wrong, then it's probably a terrible idea to show my work.

Nonetheless, wrestling a little with the triangle inequality convinced me that you can get a triangle as long as no piece of the broken stick is longer than 1/2 (in units of the original length).

The probability of the two end pieces being less than 1/2 is easy to calculate, if the positions were uniformly randomly distributed; they're 1/2 each. The middle piece, the length of the middle piece is 1 - the sum of two iid uniform random variables, and so is also uniformly random, and should also be ~1/2. That gives a total probability of 1/8.

I'm not surprised my answer isn't quite right, because I was a little sloppy about the probability of that middle piece; but I'd be surprised if the answer was badly wrong, because I double checked my answer by monte carlo, and looked to see what breaks successfully satisfied the triangle inequality, and got about 1/8, which `emboldened' me to post my answer -- perhaps falsely, as it turns out.

AWeb said...

The prob is 1/2.
Using the same starting point as JD above, where a triangle is possible as long as no stick is longer than 1/2 (which is true).

Say the stick is 1 unit long.
Randomly select the first point. Define X to be the distance between this point and the nearest side. At this point there are two sticks, one of length X (less than 1/2), and one of length 1-X (more than 1/2).

2 ways a triangle cannot be formed:

1)If the next point selected is on the short stick, no triangle can be made. THe prob of this is X, the proportion of the original length the short stick represents.

2)If the next point is on the other stick, but more than 0.5 away from the first point, no triangle can be formed. The chances of this are 0.5-X, calculated by : prob of hitting long stick =1-X. Prob of being more than 0.5 away from first point = 1-X - 0.5 (as 0.5 of the long stick is not in the "no triangle zone").

Add the two probs above (they define non-overlapping sub-events that completely (I think) make up the total event) to get the total. X + (0.5 -X) = 0.5. It's easier to see with a diagram, but I'm pretty sure this is right.

Once you figure out the no stick longer than 1/2 rule, it seems intuitively like the answer should be smaller. But that's probability for you.

Ah, math puzzles. Thanks CC

Jeff said...

Okay, if any piece is more than half it can't make a triangle at all, because the other two sides won't reach. At the 50% mark, any where you break the the remaining piece, you make an infinitely small triangle, so there is a 100% chance. As your 'set aside' piece becomes smaller and smaller, the portion of the larger piece that can sustain a break to form a triangle, becomes smaller and smaller as well, until it approaches zero as well. In fact, the portion of the larger stick, that can sustain a break to form a triangle, is EXACTLY, the size of the set aside piece. Thus as you progress down the stick the portion changes linearly..

the average of 100% and 0% is 50%.. and 50% of the time you can't make a triangle anyway.. 1/2 x 1/2 is 1/4. Thats the odds, one quarter of the time.