?

Log in

   Journal    Friends    Archive    Profile    Memories
 

Dropping the Balls - Problem-A-Day

joshua_greenOct. 24th, 2009 10:28 am Dropping the Balls

You have two crystal balls and an N-story building (N a positive integer) with windows on each floor.  If you place a crystal ball on the ground, nothing will happen, but if you drop one off the roof, it will shatter upon hitting the ground.  Your goal is to find the highest floor from which you can drop a ball out the window and not have it shatter (or show that no such floor exists).  To do this, you will drop balls out of windows and see what happens.  Naturally, if a ball doesn't shatter, it can be used in later drops, but once a ball shatters it is no longer useful.  Subject to these limitations, you'd like to minimize the maximum number of drops you might have to make.  What will your strategy be, and what's the maximum number of drops you might have to make?

20 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:nahtmmm
Date:October 24th, 2009 04:20 pm (UTC)
(Link)
Of course, I could put on a physicist hat and make a few rough estimates of quantities, but I expect that that would defeat the point of the question.


Obviously, given that it is an N-story building, the worst-case scenario (due to either starting at the bottom and going up or starting at the top and going down) would be that I have to drop a ball at each floor: N drops. (The roof, I just noticed, is already accounted for.)

I can guess what the best strategy might be, but I'll leave that for others to think about.

The problem could probably also be considered in a few other ways.
For example: supposing I have to go down to ground level to get another ball, whether or not the one I just dropped broke. Suppose further that the elevator is out, each story of the building is of equal height, and I am far more interested in minimizing my stair-climbing than in minimizing the number of broken crystal balls. Does my best strategy change?
From:joshua_green
Date:October 24th, 2009 04:30 pm (UTC)
(Link)
Starting at the bottom and working up indeed allows you to get by with at most N drops.  However, if you start at the top and work your way down, you could run out of crystal balls before learning the answer.

Yet another variation is to assume some distribution of the correct answer and then ask to minimize the expected number of drops.
From:devitojason
Date:October 24th, 2009 06:07 pm (UTC)
(Link)
Just a start, but here's a slightly better strategy than simply starting on floor one and dropping them (I don't think it's even close to optimal....)

Drop ball A on the even numbered floors (starting at 2) until it shatters. Assuming it shatters on floor 2k, drop ball B on floor 2k-1. If it shatters, then floor 2k-2 is the highest you can safely drop a ball out if. If it doesn't, floor 2k-1 is the highest.

This uses k + 1 drops.

A slightly better solution (I think) is to drop ball A off at floor N/2 (rounded somehow, if necessary). If it shatters, drop ball B, starting at floor one, until it shatters. If it doesn't shatter, drop ball A off at floor 3N/4 (again, rounded somehow). Rinse repeat.

This strategy less effective than the first strategy if lucky floor is between 1 and N/2, and more effective than the first strategy if the lucky floor is between N/2 and N, and becomes more and more effective the closer the lucky floor is to the top.

I think there must be some uniformly better solution, though.
From:mathic
Date:October 24th, 2009 07:34 pm (UTC)
(Link)
This is certainly equivalent to the 'game' where your friend picks a number from {1,2,...,N} and you try to guess it where at each guess the friend tells you whether you're right, or if it's higher or lower than your guess.

The most optimal method I ever knew for that was to split the list in half, (pick say, ceiling(N/2)) and if you're right, hurrah, otherwise your number is necessarily in a 'half size' partition, and you apply this halving method repeatedly until you find it.

The number of steps for an N story building is n, where 2^n ≤ N < 2^(n+1)
From:mathic
Date:October 24th, 2009 07:35 pm (UTC)
(Link)
The *worst case scenario* number of steps...
From:joshua_green
Date:October 24th, 2009 07:37 pm (UTC)
(Link)
The problems aren't equivalent.  Here, you can only get away with two drops above the desired floor; after that, you won't have any more crystal balls to test with!
From:mathic
Date:October 24th, 2009 07:39 pm (UTC)
(Link)
oh... very first line... heh, whoops
From:mathic
Date:October 24th, 2009 07:54 pm (UTC)
(Link)
Alright, expanding on devitojason's idea, we can actually partition more than just evens/odds, but any number of floors (by 3s,4s, etc..).

The first step will be to go up every n-th floor and see where the ball breaks. Then you have an area from the (n-1)-th floor to the n-th floor where you know the limit is, so the second step would be to go up one by one until the second one breaks in this area. The optimal method would then be a combination of maximizing and minimizing n then.. (i.e. we want to do as few as possible moves in the first step, while also as few as possible in the last step.)

I believe this would come down to finding k such that k^2 ≤ N < (k+1)^2, and letting n = k.
From:joshua_green
Date:October 24th, 2009 08:10 pm (UTC)
(Link)
This is definitely getting closer (in your formula, k = N), but you can do better.
From:patrickwonders
Date:October 25th, 2009 05:49 am (UTC)
(Link)
My strategy is that I will drop a ball from the k-th floor. If it shatters, then I will start from the first floor with second ball and continue up until the k-1-th floor. If it didn't shatter, then I will drop a ball from the 2k-th floor. If it shatters, then I will start from the k+1-th floor and go up to the 2k-1-th floor one at a time until I find the breaking point.

The worst case is when the first break is at floor(n/k)*k. In that case, I have to do floor(n/k) drops of the first ball and k-1 drops of the second ball.

Now, the only question is... what is the optimal k? It is either floor(sqrt(n)) or ceil(sqrt(n))... whichever minimizes floor(n/k) + k - 1. I suspect there is some argument by which I could assure that ceil(sqrt(n)) is always as good or better than floor(sqrt(n)) (or vice versa), but it's not clear to me at the moment, so I'd just check both. An empirical test of the first 10,000 numbers shows that ceil(sqrt(n)) does at least as well (and sometimes better than) floor(sqrt(n)).
From:joshua_green
Date:October 25th, 2009 06:29 am (UTC)
(Link)
That (essentially) was my initial solution.  However, the problem as was originally posed to me focused on the specific case N = 105.  Thus, I had to wonder why that particular number was used, and more detailed analysis uncovered a better solution.
From:patrickwonders
Date:October 26th, 2009 02:32 am (UTC)
(Link)
Yes... after submitting this solution, I was thinking... well... I already know with my strategy, it's going to take 19 moves to do a 100-story building. Knowing that, I can start on the 18-th floor and that's got to be better than starting on the 10th floor.

So... yes... now that I've played with it again, I believe I want the smallest k such that n is less-than-or-equal to k(k+1)/2 + 1. So, I want k = ceiling( sqrt( 2n - 7/4 ) - 1/2 ). Then, I try the k-th floor. If it breaks, I try each floor from 1 to k-1 in turn. If it doesn't break, I try k + (k-1). If it breaks, I do (k+1) up to (k-2) one by one. Etc. The most I will have to do is k+1 drops.
From:mathic
Date:October 25th, 2009 08:34 am (UTC)
(Link)
Ah yes,

Let f(m) = floor(sqrt(m)) and notice if

n^2 ≤ m < (n+1)^2 = n^2 + 2n + 1,

then f(n^2) = n iff n = m^2 + r, where 0 ≤ r < 2n + 1.

Now let g(m) = ceil(sqrt(m)) and notice

g(n^2) = n + 1 iff m = n^2 + s where 0 < s ≤ 2n + 1

So floor((n^2 + a)/f(n^2 + a)) + f(n^2 + a)
= floor( (n^2 + a)/n ) + n when 0 ≤ a < 2n + 1
= floor( n + a/n ) + n

and floor((n^2 + a)/g(n^2 + a)) + g(n^2 + a)
= floor( (n^2 + a)/n ) + n if a = 0
or floor( (n^2 + a)/(n+1) ) + n + 1 if 0 < a ≤ 2n + 1

It remains to compare these functions. Certainly if a = 0 they match, so what about from 1 to 2n + 1?

floor( n + a/n ) + n
= 2n if 0 < a < n
or 2n + 1 if n ≤ a < 2n
or 2n + 2 if a = 2n or 2n + 1

floor( (n^2 + a)/(n+1) ) + n + 1
= 2n if 0 < a < n
or 2n + 1 if n ≤ a ≤ 2n
or 2n + 2 if a = 2n + 1

where the only discrepancy is at a = 2n (or equivalently, if n = b^2 - 1 for some integer b). So the values of both are the same unless n is of the form b^2 - 1, when using the ceiling function is more optimal.

(Before clicking post comment, here's to hoping I made no html errors >_< *ponders nervously*)
From:mathic
Date:October 25th, 2009 09:08 am (UTC)
(Link)
then f(n^2) = n iff n = m^2 + r, where 0 ≤ r < 2n + 1.

then f(n^2 + r) = n iff 0 ≤ r < 2n + 1

g(n^2) = n + 1 iff m = n^2 + s where 0 < s ≤ 2n + 1

g(n^2 + s) = n + 1 iff 0 < s ≤ 2n + 1
From:rmjarvis
Date:October 25th, 2009 07:10 am (UTC)
(Link)
I present without proof the maximum number of drops required is:

ceil((sqrt(8N+1)-1)/2)

For N = 105, x = 14.

Actually, this is when the roof isn't assumed to be a fail. If the roof is known to be a fail, use N-1 in place of N.
From:joshua_green
Date:October 25th, 2009 03:14 pm (UTC)
(Link)
I wasn't counting the roof as a story, so I'm pretty sure your answer is correct (at least, that's the answer I got).  The actual original version I read had 106 stories but there it was given that a ball dropped from the 106th floor would break.  It's probably not necessary to specify what happens on the roof; one only needs to know the number of (consecutive) floors of unknown status.
From:rmjarvis
Date:October 25th, 2009 05:36 pm (UTC)
(Link)
Good point. I guess the roof isn't usually counted as a story in an N-story building. (e.g. My 3-story house also has a roof above the top floor.)
From:devitojason
Date:October 25th, 2009 06:21 pm (UTC)
(Link)
So I understand that "drop at ceiling(sqrt(n)) until shatters, then drop at one floor intervals until shatters" (or maybe with floor[sqrt(n)] - I didn't read carefully enough ;-) ) is the best strategy among strategies like "Drop ball A at certain intervals, once it shatters, drop ball B one floor at a time".

But, is it necessarily the best strategy among all strategies? I cannot think of a better strategy, but that certainly isn't grounds for saying there are no better strategies ;-)
From:mathnerdguy
Date:October 25th, 2009 08:01 pm (UTC)
(Link)
Let H(d,b) be the maximum height you can "solve" by starting with b balls and performing d drops. Specifically, H(d,0)=0, and H(0,b)=0.

Then if you're given b balls and d drops, you can't drop the egg from any higher than H(d-1,b-1)+1, since if it breaks you're stuck. So you must drop the egg from H(d-1,b-1)+1 (dropping it any lower doesn't help you). Then if it doesn't break, you can solve the rest only if you have H(d-1,b) floors left. That is, the maximum height you can solve with b balls and d drops is

H(d,b) = H(d-1,b-1)+1+H(d-1,b)

which we can rewrite as

H(d,b)+1 = (H(d-1,b-1)+1) + (H(d-1,b)+1)


This together with the boundary conditions gives us that

H(d,b)+1 = ∑k≤b C(d,k).



Combinatorially speaking, this is the number of subsets of a set of size d of size at most b. This is in one-to-one correspondence with the possible outcomes of d drops with b balls. You can actually see immediately that you can't solve a building higher than this, because there are N+1 possibilities to distinguish between, so you need at least N+1 possible outcomes.
From:devitojason
Date:October 25th, 2009 08:42 pm (UTC)
(Link)
Clever, I like it.