Your task is to determine, with as few drops as possible in the worst case, the highest floor F such that a ball dropped from floor F does not break.
(A drop from any floor higher than F will always break the ball.)
Solution:
Let T(b, r) be the maximum number of floors that can be resolved using b balls and at most r remaining drops. One final drop either leaves the ball intact (so we can still use b balls and now have r − 1 drops) or breaks it (leaving b − 1 balls and r − 1 drops). Hence
T(b, r) = 1 + T(b, r − 1) + T(b − 1, r − 1), with T(0, r) = 0, T(b, 0) = 0.
Solving this recurrence gives
T(b, r) = \(\displaystyle \sum_{i=0}^{b} \binom{r}{i}\).
Therefore, if we are allowed r drops we can cope with at most \(\sum_{i=0}^{m} \binom{r}{i}\) floors. Conversely, the minimum worst-case number of drops, call it k, is the smallest integer satisfying
\(\displaystyle \sum_{i=0}^{m} \binom{k}{i} \;\ge\; n.\)
Strategy (constructive): keep two counters, b (balls left, initially m) and r (drops left, initially k). After having already proved safe the highest floor saf, compute
step = 1 + \(\displaystyle \sum_{i=0}^{b-1} \binom{r-1}{i}\).
Move up step floors from saf and drop a ball there.
- If it breaks, set b ← b − 1; if it survives, set saf to that floor. In both cases set r ← r − 1 and repeat until either all floors are resolved or no balls remain.
This procedure guarantees that no matter how the drops turn out we will never require more than k drops, and k is the smallest number for which such a guarantee is possible. Hence the puzzle’s answer is:
Minimum worst-case drops = smallest k with \(\sum_{i=0}^{m} \binom{k}{i} \ge n.\)
Examples:
- m = 1 (one ball): need k = n drops → linear search.
- m = 2, n = 100: smallest k is 14 (since 14·15/2 = 105 ≥ 100).
Thus the presented strategy is optimal.
Comments (6)
This strategy is following on from the solution for 2 crystal balls, and aims to minimize the maximum (i.e. worst case scenario) no. of orbs dropped.
Starting form the first ball, each ball is dropped at intervals from the bottom until it breaks - when it breaks, the second ball is then dropped at intervals within the previous interval, and so on.
In order to minimize the maximum no. drops required, the worst case scenario for each interval must be 1 less than the worst case needed in the previous interval. This must be true for all intervals of all balls.
Part 1)
Strategy with 2 balls and n floors:
Let the worst case no. balls needed for the first interval from the first ball be a,
the worst case for each interval is therefore: a, a-1, a-2..etc..a-a
The number of floors n is therefore:
n=a+a-1+a-2+...+1 (using sum of arithmetic series)
n=a(a+1)/2
Solving this for a (with a rounded up) gives the maximum number of drops needed, and also the size of each interval to drop from.
Part 2)
strategy with 3 balls and n floors:
Now the intervals from the first ball are spit again into intervals by the second ball. Again let the worst case for a first ball interval be a.
The size of the first interval, from part 1), is therefore: a(a+1)/2
Since the worst case must decrease by 1 each time, the successive interval sizes are therefore: a(a+1)/2, (a-1)a/2, (a-2)(a-1)/2....etc.
The number of floors, n, is therefore:
n=a(a+1)/2+(a-1)a/2+(a-2)(a-1)/2+...+(a-a)(a-a+1)/2
This is actually the sum of the triangle numbers, each having the formula (r)C(2), where (x)C(y)=x!/y!(x-y)!
Therefore, the sum can be written as:
n=sum of (r+1)C(2) from r=1 to r=a
Using pascal's triangle, where each number represents
(row number-1)C(position in row-1), one can show that this is equal to (a+2)C(3) by looking at the relationship between the 3rd and 4th diagonal columns.
n=(a+2)C(3)
The strategy for 3 balls therefore requires solving for a (rounding up), and dropping the first ball at interval sizes a(a+1)/2, (a-1)a/2, (a-2)(a-1)/2....etc.
For example with 100 floors, a=8, the interval sizes are therefore: 36, 28, 21, 15, and 1st ball is dropped at floors: 36, 64, 85, 100.
The secondary intervals for the second ball are calculated like in part 1).
Part 3)
Strategy with m balls and n floors:
From part 1) and 2), one can deduce the general equation:
n=(a+m-1)C(m) (where a is the worst case of the smallest interval)
This equation can be proved by induction, using part 1)&2) as a base case:
Assume that n=(a+k-1)C(k) is true, where k is the number of balls
For k+1 balls, the number of floors, n, is the sum of all the interval sizes.
The worst case of each interval is determined with k balls, so the size of each interval is (a+k-1)C(k).
Since the sum of (x+y-2)C(y-1)=(x+y-1)C(y), as given by pascal's triangle, the number of floors covered by k+1 balls is:
(a+k+1-1)C(k+1)
Since this is true for k=2, the equation n=(a+m-1)C(m) holds true for all cases.
Therefore, one need to solve the equation for a, and drop the first ball at intervals: (a+m-2)C(m-1), (a+m-3)C(m-1)...etc.
The subsequent ball intervals are calculated in a similar method.
However, it should be noted that the first interval should never be dropped past the halfway point, so if a first interval calculation gives a value larger than n/2, then drop at n/2.
This method would give the maximum no. drops as a+m-2, however, this does not work for large m, where the first interval would become greater than n/2.
Here's a simple strategy:
The minimum number of required ball drops, M, for N floors is
M = log2 (N + 1), rounded up to the closest integer
EXPLANATION:
We will use 15 floors as our starting example. (it would probably be unreasonable to expect a crystal ball to survive from this height, but the mathematical formula at the end should be valid for any number of floors).
The fastest approach is to use binary splitting, thereby minimising the number of balls required. (This is akin to Bubblesort in computer programming).
15 is one less than 16.
Half of 16 is 8, so that is the first drop height.
If the first ball does not break, then go to 8 + 4 = 12th floor
If the ball does break, then go to 8 - 4 = 4th floor
Etc...
This diagram illustrates the order of floor heights to drop from, starting from N = 8:
..............................................15
............................................../
...........................................14
.........................................../..\
........................................./....13
.......................................12
....................................../...\....11
...................................../.....\../
..................................../.......10
.................................../...........\
................................../.............9
................................./
...............................8
.................................\..............7
..................................\.........../
...................................\.........6
....................................\....../..\
.....................................\..../....5
........................................4
..........................................\....3
...........................................\../
.............................................2
..............................................\
...............................................1
This shows that for N = 15 floors, M = 4 ball drops are required (maximum).
Similarly, N = 7 requires M = 3 ball drops
and N = 3 requires M = 2
and N = 1 requires M = 1
The relationship is simple:
2^M = N + 1
In other words, the minimum number of required ball drops is
M = log2 (N + 1), rounded up to the closest integer :D
If we have insufficient N, then applying the same strategy will help us eliminate the most floors, until balls are depleted.
And that's it.
Fri Jun 24, 2016 7:43 am by HariKrishnan
You have m crystal balls to test.You must determine the highest floor of a n-story building from where if a crystal ball were dropped, it would not break. What will your strategy be?
Assumptions:
All crystal balls are uniform.
The result of a ball drop is binary, either it doesn't break, or it shatters into fine dust.
Or, to address the question more accurately (based on the logic given above):
N = 2^M - 1
Where N = the maximum number of floors
and M = the number of crystal balls
bathfilms, your strategy would be correct if we were trying to minimize the number of ball drops needed given an infinite amount of balls.
However, the question is asking for the best general strategy given a finite amount of balls m. When M > log2 (N + 1), binary splitting is indeed most efficient, but when M < log2 (N + 1), it is not.
For example, one cannot use binary splitting for 2 balls and 100 floors. (I have replied to your post on that also).
Thank you Dzallen. I agree.
Please see my response on other posting.
:)
I want to break as few crystal balls as possible - those things are expensive! just start on floor one and go up one at a time until it breaks
Add a Comment or Suggest an Answer