Good job. I didn't think anyone could beat 20 (or 19, whatever), but it
looks like there is indeed a way to beat it. But you have an "off by one"
error. Let's say you drop the first ball at 15, and it doesn't break, but
then you drop it at 29 and it does break. Then you would drop the second
ball at 16, 17, 18, etc. up to 28, which gives 13 extra drops in the worst
case, not 14.

   Also, if you drop it at 92, and it doesn't break, then you drop it at 99
and it does break, then you have a worse case of 93,94,95,96,97,98 or 6
extra drops. However, if you had dropped it at 92 and it didn't break, and
dropped it at 96, then your worst case would be 4 extra drops (93,94,95 if
it broke vs 97,98,99,100 if it didn't break), which is better than your 6.

   - Oliver

the only thing I can say is that we should minimize the average, not the
worst case. I assume in this case average is also smaller, but the fact
that we now have a variable step makes the problem more complicated

Good point.  But I don't think you've reached the optimum.

As I said elsewhere, I got sick of trying to work this out by hand, and threw
it on the computer.  I also wrapped a hill-climbing algorithm around that
calculation to see if I could get any closer to optimal solutions.  That isn't
guaranteed to find global optima (though it seems plausible since the search
space is smooth except for the jaggedness caused by integer rounding[*]), but
it does produce moderately interesting results.  I've run it with different
numbers of ball1-probes in the range 9 through 16.

The algorithm is trying to optimise the average number of throws, but I did
modify it to look for best worst-case instead (which is /much/ slower) and --
for the cases I checked (9 through 13) -- it does seem that the strategies with
the best average also have the best worst case.

The first thing is that (according to the algorithm), sqrt(N) is not the
optimum number of probes with ball 1 after all.  It seem that the best we can
do with 10 probes is:
{ 14 27 39 50 60 69 77 84 90 95 }      (NB: 1-based floor numbers!)
    mean:   10.34 (4.9 & 5.44)
    worst case: 14

That particular case is interesting, because the "optimum" solution is unique.
And it also follows exactly the (+14, +13, +12, ....) pattern.  In the other
cases there is no unique best solution, and also there are "glitches" in the
interval sequences.  In each case, though, there is a solution with only 1
glitch (or only a few when we are looking at longer probe sequence where we
need more glitches just to fit the entire sequence in).  It seems as if the
optimum "wants" to be a sequence like that, but it cannot always quite manage
it (if you see what I mean ;-)

Anyway, some more data.  The discovered "optimum" sequences of various lengths
are:

9:   { 5 29 42 54 64 73 81 88 94 }
    mean:   10.44 (4.54 & 5.9)
     worst case: 15

10: { 14 27 39 50 60 69 77 84 90 95 }
    mean:   10.34 (4.9 & 5.44)
    worst case: 14

11  { 14 27 39 50 60 69 77 84 90 94 97 }
    mean:   10.31 (4.96 & 5.35)
    worst case: 14

12:  { 14 27 39 50 60 69 77 84 89 93 96 98 }
    mean:   10.3 (5.02 & 5.28)
    worst case: 14

13:  { 14 27 39 50 60 69 77 83 88 92 95 97 98 }
    mean:   10.3 (5.09 & 5.21)
    worst case: 14

14:  { 13 25 36 46 55 63 71 78 84 89 93 96 98 99 }
    mean:   10.3 (5.53 & 4.77)
    worst case: 14

15:  { 13 25 36 46 55 63 71 78 84 89 93 96 98 99 100 }
    mean:   10.31 (5.54 & 4.77)
    worst case: 15

16:  { 13 25 36 46 55 63 70 76 82 87 91 94 96 97 98 99 }
    mean:   10.33 (5.71 & 4.62)
    worst case: 16

So 12 though 14 probes can all be used to create a strategy that requires an
average of 10.3 throws with a worst case of 14.  (BTW, there's no rounding in
the floating point numbers).

   -- chris

[*] FWIW, it does seem to converge on the same solution when started from
rather distant points in the search space -- but I only tried that once or
twice so it may be a coincidence.