Friday, May 27, 2005

String Puzzle

I found mention of this on Eric Maino's old blog (link):

You are given lengths of string that will always burn in 60 minutes from one end to the other. You have been tasked with measuring 45 minutes using these string how would you do it? Now imagine that the strings will burn from one end to the other in 60 minutes but they will not always burn at the same rate. Sometimes the strings will burn faster or slower at parts. How would you measure the time now?

I had not seen this puzzle before today, and since it's the day before a holiday weekend, and I'm working instead of taking my assigned company holiday, I thought that I'd give myself a break, eat some peanut M&M's, and think up a solution (pretending all-the-while that I'm at the mothership in Redmond with some uber-cool geek [oxymoron] interviewer waiting for my answer).

My solution to the first scenario is to simply cut 1/4 of the length off, and start burning from one end. The assumption here is that the string burns at a constant rate. To find the 1/4 length, fold the string in 1/2, and then in 1/2 again. If you can't cut, then just start the burn at the 1/4 mark, and the flame should go in two directions (towards each end). When the longer segment finishes burning, that should be 45 minutes.

For the second scenario, a constant burn rate cannot be assumed. This means that if you start burning a string from one end, it will reach the middle point at a different time than if you started from the other end. But, if you burn both ends at the same time, then when the flames meet and burn out, you should be at 30 minutes (regardless at what point in the string that event takes place).

If you started burning a second string from only one end when you lit the first string, then you know that regardless of how much of the second string is burned up at the end of 30 minutes, that you'll have 30 minutes left to go. Using the same principle as the first string, light the other end of the second string at the 30-minute mark, and when the flames meet and extinguish, then you should be at the 45-minute mark.