John Fremlin's blog: Dropping two bowling balls

Suppose you have two bowling balls and a one-hundred storey building. For some reason you wish to discover the lowest floor you can throw the balls from to have them break. What is the maximum number of throws you need to determine this?

I came across this puzzle on Chung-chieh Shan's blog, who got it from Jesse Farmer who was posed it as an interview question. The answer surprised me and looking more closely into it, some beautiful number sequences are involved. The terrible bowling ball analogy conceals some pretty mathematics.

Once you have broken one ball by throwing it from floor i, you may need to test each floor one at a time from the lowest possible floor up to floor i-1. If you didn't break the first ball by throwing it from floor i, you can restrict your search to the floors above i.

Suppose that the balls could break when dropped from the ground floor, but will definitely break from the top floor. Counting the ground floor as 0, the answer lies in the range 0-99.

Let c(n,b) be the maximum number of throws you need to determine the minimal breaking floor given you have where n > 0 is the number of storeys to your building and b gt; 0 the number of balls. As argued above, c(n,1) = n and certainly c(0,b) = 0. Suppose you have multiple balls and throw one out of floor i, labelling the ground floor as floor zero. Either it broke, in which case you are reduced to the problem with i floors and b-1 balls, or you know that the minimal breaking floor is higher, and you are reduced to the problem with n-i-1 floors. So c(n,b) = 1+min_i(max(c(i,b-1),c(n-i-1,b))).

I guess part of the motivation for this as an interview question was to check you knew dynamic programming. Chung-chieh Shan demonstrates some impenetrably concise Haskell, but I don't think it can be extended neatly to the two dimensional case (involving more balls). Maybe a more advanced Haskellian or Haskellite will enlighten me. . . Anyway here's my Lisp.

(defun c (n b)
  (let ((table (make-array (list (1+ n) b) 
			   :element-type 'fixnum 
			   :initial-element 0)))
    (macrolet ((cc (x y) `(aref table ,x (1- ,y))))
      (loop for n upto n do ;;; b = 1 case
	    (setf (cc n 1) n))
      (loop for b from 2 upto b do 
	    (loop for n from 1 upto n do 
		  (setf (cc n b)
			(1+
			 (loop for i below n 
			       minimizing 
			       (max 
				(cc i (1- b)) 
				(cc (- n i 1) b)))))))
      (values (cc n b) table))))

The shape of the answer is counter-intuitive to me, maybe partly because we are looking at a worst-case rather than average case. If you had an unlimited supply of balls then clearly the answer is ceiling(log2(n)) throws as you obtain only one bit of information from each throw. This easily bounds the number of balls to be considered.

However, what is the best floor to throw the first ball off when you have only two balls left? It turns out you often have quite a lot of choice. As the function c increases only slowly with n and is in integer increments, you have a fairly free reign as you drop the ball.

The step points where increasing the building by one storey costs another throw were the key for me to get to grips with the problem. By considering the inverse function, which turns out to be easy to calculate in the two ball case, we can readily arrive at a much cleaner solution.

Given c throws, how tall a building can you solve with certainty n(c,b)? First, in the one ball case you have to play safe so n(c,1)=c and trivially n(1,b)=1. Now for the induction step, considering throwing a ball out of floor i: if the ball does not break then you have eliminated i+1 floors, otherwise you are fine provided that you can solve the problem for i floors with your remaining balls and throws. Trivially, dropping back to the one ball case cannot make things better and eliminating more floors cannot make things worse and could be better, so in the two ball case the answer is easy: throw at level i = c-1. The throw eliminates c floors and resolves to n(c,2) = n(c-1,2)+c — that is, just a sum of the ball-breaking cases. We've found the triangular numbers, n(c,2) = c(c+1)/2!

This gives us a way to analytically calculate the inverse function we found before with dynamic programming: c = sqrt(2n + 1/4) - 1/2, but note that this is only true for the n at step points; at other ones the value given for c is not an integer and too low; so you must take the next highest integer. The function in Lisp is

(defun c2(n)
  (ceiling (- (sqrt (+ (* 2 n) 1/4) ) 1/2)))

I think that's much neater than using dynamic programming. However, extending to the multi-ball case is not tidy, as far as I can see.

PS. Now it seems that, reading their answers, Chung-chieh Shan and Jesse Parker came up with an uglier formula because they use a slightly different definition where they consider c(n=1) to be 0, not c(n=0) to be 0. I figure my way is prettier and a strong endorsement for numbering the ground floor as zero. . .