Monday, May 16, 2011

An exercise with bottles

One last question before I take a break from this flurry of posts  - You are hired by a bottle manufacturing plant, and inducted into its testing department, which happens to be a 55 floor building. Your manager gives you the unenviable task of determining the lowest floor from which if dropped, a bottle would break.  He gives you two identical bottles to expriment with. Devise an optimal scheme which needs you to drop the bottle fewest number of times before determining the lowest floor from which it would break .

I have a few hints here. Please use them wisely, and refer to them only if you need to -

Hint 1 - The brute force method would involve using only one bottle . Drop it from each floor starting from the first. As soon as it breaks when dropped from a certain floor, you have the answer. However, whenever it does not break, you have to go back to the ground floor to fetch the bottle , and repeat the experiment from the next floor. This is the reason your manager, a benevolent man, has given you an extra bottle to play with.  Note that if you were to use only a single bottle , the worst case scenario would be when it breaks when dropped from the 55th floor.

Hint 2 - One way of using the second botttle is this - Drop the first bottle from the odd numbered floors - 1, 3, 5, 7 etc... Assume it does not break when dropped from the 29th floor, but does break when dropped from the 31st floor. Now,  you can use the second bottle and drop it from the 30th floor. It if breaks, 30 is your answer, else 31 it is ! Note that the worst case scenario here is when 54th floor is the lowest one from which it breaks.  But , you now have to drop the bottle roughly only half the number of times (compared to the previous case)  before arriving at the solution for the worst case scenario. But can you improve on this scheme ?

Hint 3 - What if we dropped the first bottle from every third floor - 1, 4, 7, 10 ... etc ?

Hint 4 - Last hint ! A good solution would involve multiple worst case scenarios instead of just one !  Do share your ideas !

Note - Apparently blogger has some issues, which have caused some comments to disappear ! Hopefully, in time they will reappear.

Solution - The idea is to systematically 'construct ' multiple worst case scenarios. This can be done as follows -

Drop the first bottle from the 10th floor. It is breaks, we need to start dropping the second bottle from the 1st floor to determine the lowest floor from which it breaks. The worst case scenario would be when that happens to be floor 9. In that case, we have dropped bottles a total of ten times - The first bottle was dropped once, and the second one was dropped nine times.

If the first bottle does not break when dropped from the 10th floor, drop it from the 19th floor. If it breaks, start dropping the second bottle from the 11th floor. In the worst  case scenario, which is Floor 18 in this case, you would have dropped the first bottle twice, and the second bottle 8 times - Again totalling to dropping the bottles 10 times.

Proceeding in this way, if the first bottle does not break when dropped from the 19th floor, try floor 27 next. The key idea is this - To arrive at another worst case scenario, we are dropping the first bottle one extra time, so the second one should be dropped one less time.  So the first one needs to be dropped on floors 10, 19, 27, 34 etc....

The first 10 numbers adds to 55, so I chose the building to have 55 floors. I haven't check the corner case to see if it works for 55. Else , solution would change to 11, 21, 30, 38 etc.... In that case the solution can 'support' a larger number of floors in the building.

Do let me know if you have other/better solutions..

5 comments:

  1. hmm... my first thought was binary search. However, that will not be feasible with the 2 bottle limit. Hint 2 is more appropriate. I cannot think of a better method.

    Rafiki (For some reason my google account is acting up)

    ReplyDelete
  2. Anonymous - Binary search is actually a very good thought, but yes it won't work here with 2 bottles. I've added another hint:-)

    ReplyDelete
  3. Start from 28th(half of 1+55) floor.If it does'nt break go to 42nd(average of 29 and 55) and experiment with the other bottle.If it doesn't break still,collect both bottles from the ground floor,try from 49th(midway between 43 and 55) and then from 52nd and if not finally from 55th.
    At any stage described above ,if the bottle breaks, go down midway and try. If it breaks go midway up to the next stage point and repeat going midway and trying.

    ReplyDelete
  4. Thanks for posting the solution! I actually thought of dropping the bottle every 10th floor - 10, 20, 30, 40, 50, and eventually 55. But obviously, the number of times the bottle is dropped increases based on different worst-case scenarios, so I didn't post the thought :). The answer is a reminder that one should adapt the solution to different scenarios of the same problem. Very relevant to real world problems to which we rigidly apply the same template of solutions without thinking a little differently.

    ReplyDelete
  5. Neeraja - You should've posted your thoughts ! You were close to the solution:-) Doesn't matter if its not fully right or complete ! Do post your ideas in future even if you are not sure. Others could possibly build upon them :-) True, I think this is a nice problem that involves slightly different thinking !

    ReplyDelete