## Thursday, April 22, 2010

### Critical Height

You have an infinite supply of crystal balls that you take into a building with 1000 stories.

There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.

How many trials minimum do you need in order to determine the critical height?

Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?

Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?

Note that the two advanced versions are two different questions and thus beget two different strategies.

Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.

Solution to advanced version #1:
http://dharmath.blogspot.com/2010/04/solution-1-critical-height.html

1. critical heightnya pasti integer kah ?
kalau ya, jawabannya floor (lg 1000) + 1 = 10 --> lg = log base 2 pakai binary search biasa
kalau ga, ya jawabannya dlm range =p

1. kalau k>=10, tetep 10; kalau k<10, use the first k-1 in the binary search until you're left with a range of length x (kalau k = 1, x=1000; k = 2, x = 500, k = 3, x = 250; etc until k = 9, x = 3), terus mulai satu2 dari lantai paling bawah sampai break / sampai top of the range, totalnya (x+k-1)

2. @Raymond:

From physics, we know that the critical height is not always integer, but I guess we're asking for the floor that contains the critical height, so assume that it's an integer for now.

Binary search is correct, easy enough.

As to your attempt at the advanced version, please see the clarification above. With your strategy, if the critical height is at floor 499, and you have 2 balls, the first ball would break at floor 500, and then you'd try the second ball from floor 1,2,3,...,499. This is quite a bad worst-case. The point of advanced question #1 is to determine the strategy to minimize the worst-case scenario.

For advanced question #2, I agree that your strategy is sensible and it's quite a good answer actually. I'm just not sure that it's optimal :D

3. Hmm well, for the case of 2 balls, let's say we drop ball 1 from floor k :
*IF ball 1 does break, then we're left with k-1 floors below floor k to check with only 1 balls, this takes k-1 attempts at the worst case ( we really need to check one by one from the 1st floor to make sure 100% we find the correct answer with just 1 ball).
*On the other hand, if ball 1 doesn't break, then we're left with 1000-k floors above floor k to check with only 1 balls. By the same reasoning, this takes 1000-k attempts.

Hence, we need at least X = 1+max(k-1,1000-k) attempts for a strategy where we drop ball 1 at k-th floor. If k<=500, X = 1+(1000-k) and the min for X in this range is when k = 500 -> X = 501. While if k > 500, X = 1+(k-1) and the min for X in this range is when k = 501 -> X = 501.

In general, for k = 2 and n floors, the answer would be 1 + floor (n/2).

Now when we're moving for k = 3, after we drop the 1st ball, we're left (again) with 2 parts (below and above), and since we're considering the worst case, we take the largest of the two and do 1 + floor (interval/2) attempts as it's optimal for 2 balls. Thus to minimize the largest of the two, we try to make the two parts as similar as we could, i.e. : floor (n/2) and ceil(n/2).

I believe one can do a little bit of induction routine here to check that this strategy works for all k = 1 to 9.

Justru yang part 2 nya rasanya cukup sulit, krn dah bicara mengenai EXPECTED number of trials. Jadi walau misalkan k = 10 selalu bisa disolve dalam 10 trials dengan binary search (and sometimes less) bisa aja ada strategy lain yang mungkin worst casenya > 10, tapi expectedya lebih kecil dari binary search karena banyak case yang bisa disolve dengan sedikit bola (well if what you meant by expected is sum of probability times number of trials here).

4. Quote :
*On the other hand, if ball 1 doesn't break, then we're left with 1000-k floors above floor k to check with only 1 balls. By the same reasoning, this takes 1000-k attempts.

Not correct.... if ball 1 doesn't break, you are left with 1000-k floors but you still have 2 balls to use, you don't have to resort to "linear" approach just yet.

5. oops right, sry I'll fix it =p