[eranki]

Asymptotically, the question with more coconuts is more interesting. I haven't verified this for sure (there are some assumptions), but:

With the "naive" asymptotically correct solution (go up a constant number k of floors, then linearly search the remainder), two coconuts gives us a worst case cost of:

n/k + k

minimize for k, we get a cost of

2n^(1/2)

With 3 coconuts, we have

n/k + 2k^(1/2)

minimize for k, we get

3n^(1/3)

What happens when we get log(n) coconuts?

log(n)n^(1/log(n))

= O(log(n))

Sweet! So at least we can see that it converges to binary search as we add coconuts.