A few days ago I posted this puzzle:
You have two identical marbles and access to a 100 story building with windows that open on each floor. What is the minimum number of trials [later addition: in which you can be certain of finding the highest floor from which a dropped marble will not break, whichever floor it is] of dropping a marble from a window necessary to determine the highest floor at which a marble will not break? Describe the the procedure. You may destroy both marbles in the process.
Drop the first marble from floor 14, then from floor (14 14 - 1 =) 27, (27 14 - 2 =) 39, etc. — 50, 60, 69, 77, 84, 90, 95, 99 — until it breaks, then the other marble from the intervening floors. This has a worst case of 14 trials.
There seem to be two necessary insights for finding the correct solution; maybe three if you're a programmer:
- Binary search is not optimal. (This is the optional programmer insight — by which I mean that binary search is such a well-trodden mental path for programmers that it may in effect put blinders on them. The first words out my mouth when I heard the problem were "Well, binary search isn't going to work," and I suspect that has to do with my not really being much of a programmer.)
- The optimum solution is going to involve dropping the first marble (A) at fairly large intervals until it breaks, and then dropping the other marble (B) on the intervening floors between A's last safe drop and its failure. Or, to put it another way, test A at fairly large intervals A1, A2, ... An until A breaks at Ab, at which point you test with marble B from Ab-1 1 to Ab-1.
- To minimize the total number of trials, the number of B trials necessary must decrease by one for each A trial completed; therefore the interval between An and An 1 must decrease by one on each iteration. I consider this the key insight; at any rate, when I had it, a couple of minutes into thinking about the problem, I knew I had the right method and finding the correct answer was just a matter of arithmetic.
The incorrect answers people submitted fell into four groups:
- Drop the first marble from every other floor until it breaks, then drop the second from the floor below. This approach produces a worst-case of 51 trials.
- Drop the first marble from every third floor til it breaks, then test the intervening two floors with the other.
- Trisect the search space iteratively (i.e. test with the first marble 1/3 of the way up the untested floors (i.e. at floors 33, 55, 70, 80 ...) until it breaks, then test the intervening floors one at a time with the second marble. This has a worst-case of 34 trials.
- Drop the first marble from every 10th floor until it breaks, then drop the second from the intervening floors. This produces a worst case of 19 trials.
I wrote the insights section above before receiving any attempted solutions, so I feel a little vindicated by how well the incorrect solutions mesh with the insights.
Mistake i seems to me to show a failure to grasp insight 0 — indeed, it shows a fair amount of creativity in forcing the problem into a shape that allows binary searching to work on it. It is, however, more clever than useful. Why not take the straightforward approach and drop the first marble from floor 50? Your worst case is still 51 trials, but your average will be far smaller. (Admittedly, optimizing for the average number of trials is not a goal of the puzzle.)
Mistake ii and iii seem to show a grasp of insight 0, and mistake iii modifies the familiar technique of binary search in an interesting way to deal with two pointers. Mistake ii's worst case is 36 trials; mistake iii's is 33.
Mistake iv shows a grasp of insight 1. (It may or may not also show a grasp of insight 0; as I said above, I'm not sure insight 0 is required if your training hasn't provided you with a certain set of mental blinders.) I suspect that once you've thought of this solution, you're not likely to find the correct solution unless someone tells you it's wrong. The one thing I can think of that might make you suspicious of it the fact that the worst case is 19 not only if you drop the first marble every ten floors until it breaks, it is also the worst case for dropping it every 8, 9, 11, or 12 floors. It might (or might not) strike one as unlikely that the optimum solution could be achieved so many different ways.
I noticed two properties of the solution that are generalizable to other problems of this type (assuming there is any such thing). Let s be the size of the search space (in this case, 100 stories); let t be the maximum number of trials necessary to find the answer within the search space; and let n be the site of the first trial. Then:
Edit: There were initially two statements below, 'a' and 'b'; turns out I screwed each one up in different ways. What follows now for each how I originally posted it, a comment on why it's wrong, and the correct version. Sigh. I know I tend to make mistakes in my writing when the hard part's done, but I still missed these til alierak pointed them out.
|Original:||a)||t = n|
|Comment:||Arg. Braino: the correct observation is|
|Revised:||a)||t >= n|
|Comment:||Another error: written as 'n' to perpetuate the error from a; '>' rather than '>=' was a typo|
So, can anyone think of any application for this observation, other than to this class of contrived puzzles?