Puzzle – Break a stick to get a triangle
April 2, 2010 – 9:26 pmI read somewhere this is a Google interview question: Let’s say you drop a stick, breaking it randomly in 2 places, leaving you with 3 smaller sticks. What’s the probability you can make a triangle out of the 3 sticks?
There are a number of ways to tackle this, including this very elegant solution: http://www.cut-the-knot.org/Curriculum/Probability/TriProbability.shtml. For the less elegantly inclined (and those as unlikely as me to be working at Google any time soon), here’s another way:
The first insight is that what you want to avoid is ending up with one really long stick and two short sticks – you need the shorter sticks to have a combined length greater than the longer stick. This effectively means that if you think about the stick as having two halves, then the two breaks need to be on opposite halves. The probability of the breaks being on opposite sides of the original stick is 50%.
The second insight is that when the breaks are on opposite halves, if you start from the outer ends of the original stick and measure the distance to each break, the sum of those two distances needs to be greater than 1/2 the length of the original stick. Otherwise we’d end up with two short sticks having a combined length less than the remaining stick. What’s the probability of this? The probability that two random numbers from 0 to .5 add up to more than .5 is 50%
So that’s a slightly long-winded way of arriving at the answer – which is that you have a 50% * 50%, or 1 in 4 chance, that you’ll be able to make a triangle.