two-marbles puzzle followup

[xela]

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:

0. 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.)
1. 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 A₁, A₂, ... A_n until A breaks at A_b, at which point you test with marble B from A_b-1 1 to A_b-1.
2. 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 A_n and A_{n 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:

1. 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.
2. Drop the first marble from every third floor til it breaks, then test the intervening two floors with the other.
3. 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.
4. Drop the first marble from every 10^th 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
original:	b)
Comment:	Another error: written as 'n' to perpetuate the error from a; '>' rather than '>=' was a typo
Revised:	b)

(If it had been less than 25 years since the last time I did a mathematical proof, I'd prove those two statements; as it is I'm just going to assert that they are true and provable.)

So, can anyone think of any application for this observation, other than to this class of contrived puzzles?

Comments

[alierak.livejournal.com]

a) Not necessarily, you may use some n < t and still come up with a correct solution. This works because 100 isn't an exact triangular number; you can make the first test as low as the 9th floor and still need at most 13 further tests.

b) Notational error: you have to specify something that you're summing, so you'd want to show a "j" to the right of the sigma. Math error: I think you mean greater than or equal to.

[alierak.livejournal.com]

And on (b), no, again, n can be yet smaller and still come up with a correct solution. t, on the other hand, cannot.

[yakshaver.livejournal.com]

Yeah, I meant >=, not >. On the notation thing would $$\sum_{1}^{t} >= s$$ be correct? (Sigma notation isn't something I've ever seen much of, and the examples I could find are all doing more than summing a range of integers.)

[alierak.livejournal.com]

Sometimes people can be sloppy with the notation and still be understood, but I think what you want is $$\sum_{j = 1}^{t} j >= s$$, the point being to specify both a loop variable (j, going from 1 to t) and what to add to the sum on each iteration (j).