Will the glass ball break?

Question

Before you stands a building with N-floors. On each floor there is an open window. You have two identical glass balls. If you were to drop a ball out the window onto the ground below, it might or might not break.

Your goal is to determine the highest floor for which dropping a ball out the window results in the ball not breaking. You can continue dropping the balls out the window as long as at least one of the balls remains intact.

Example: You go to floor 1 and drop a ball. It doesn't break so you go to floor 2 and try again. This time it breaks so you can no longer use that ball. But you still have 1 ball left so you continue until that ball is broken. By the time the second ball breaks, you should know the answer (if not then the strategy is invalid).

The question: What is the most efficient strategy for determining said highest floor? For this question, the most efficient strategy is the one which yields the smallest average number of total drops over all possible highest floors for the building.

Example continued: If the building has 100 floors, the strategy described would require X + 1 drops where X = the highest floor's number. Summing over all possible X we would get 5050 so the average is 50.5 drops.

Note: It is possible that a drop from floor 1 results in a broken ball. It is also possible that a drop from the top floor results in an unbroken ball.

An answer will only get a green check if it is both correct and clearly explained.

Special aside: This is my first time posting a puzzle here. I tried to be clear and concise but please let me know about anything I need to clarify.

Is this question a duplicate? There are certainly similarities between this and the puzzle proposed here: Dinosaur egg drop. However, that puzzle specifies the number of floors and total number of drops. My question asks to generalize the number of floors and does not specify the number of drops, only that you can continue as long as at least one glass ball is intact. Additionally, I do not see the correct answer to this puzzle on that puzzle. Some of the answers and reasoning there are definitely similar to what I am looking for but none of those would get the green check from me on this puzzle.

Answer 1

Strategy

My thoughts on the matter, (probably insufficient to earn the green check of approval).

The strategy I would employ would be to drop it every $\sqrt{n}$ floors and then starting from the floor above the last one it didn't break it at, drop it successively higher by one floor.

Why this strategy?

Well this means the searching for the location in both "halves" of the search are isomorphic, searching $\sqrt{n}$ spots for the first break. You expect to find your spot in ~$\sqrt{n}+1$ drops as the first search would take on average $\sqrt{n}/2 +1/2$ drops and the second search would also take $\sqrt{n}/2 +1/2$ drops.

Well I might come back to improve my answer but that is far as I am going for now.

Hypothesis: for $K$ balls and $n$ floors, ~ ${n^{1/k}} + log(n) term$

3 ball example with 100 floors: break it into segments of roughly $100^{1/3}$ floors, so 4.64, then cluster these by groups of roughly 4.64 groups.This is 21.5 floors per cluster. So this would take on average lets say, 3 guesses to find the right super cluster, 3 guesses to find the fight group of 4.64, then 3 guesses to find the exact spot for an approximation of 9 guesses expect for 3 balls 100 floors.
(worth noting using the first ball for a drop in the middle then using groups of 7 on the remaining chunks also seems like it would have an expected of 9)

Answer 2

Number the floors $1$ to $N$. Let $E_{N,b}$ denote the expected number of drops the optimal strategy takes for an $N$-floor building, starting with $b$ glass balls. This means that $E_{1,b}=1$, and $E_{N,1}=\frac{1+2+\dots+(N-1)+N+N}{N+1}=\frac{N(N+3)}{2(N+1)}$.

Suppose the first floor you drop from is floor $f$. The ball will break with probability $\frac{f}{N+1}$, in which case you will have $f-1$ floors to search with only one ball. The ball will be intact with probability $\frac{N+1-f}{N+1}$, wherein you will have $N-f$ floors to search with two balls. Since you want to choose the value of $f$ which minimizes the expected number of drops, it follows that $$ E_{N,2}=1+\min_{1\le f\le N}\left(\frac{f}{N+1}\cdot E_{f-1,1}+\frac{N+1-f}{N+1}\cdot E_{N-f,2}\right) $$ This gives a recursive formula which allows you to compute $E_{N,2}$, combined with the base cases in the first paragraph. I doubt there is a nice, closed form formula for all $N$.

Answer 3

I would have added this as a comment to Mike Earnest if I could have.

It appears that E(N,2) reaches its minimum with a f at N/2.

Does this mean that the strategy ought to be begin at floor N/2, plus or minus .5 for N odd? If the 1st ball breaks then begin with floor 1 for the 2nd ball. If the ball does not break, follow the same strategy using floor N/2 +1 as your 1st floor.

For the 100 floor example, we would drop the first ball at floor 50. If it failed to break we would then use floor 75 as our next drop, etc.

Answer 4

If the number of floors is of the form (K)(K+1)/2, the worst-case number of drops may be reduced to K marking the top floor of the building, the floor below that, the floor two down from that, three down from that, etc. until one reaches the base of the building, and trying marked floors starting with the lowest (marked) one until a ball breaks, then starting at the floor above the previous marked floor (or the ground floor if it broke on the first marked floor) and trying every floor until the ball breaks or all floors below the next marked one have been tried.

With six floors, for example, one would mark floors 6, 5, and 3, and then try those in order (3,5,6). If the ball breaks at 3 (first drop), drops at 1 and 2 (two more) will reveal the breaking point. If it breaks at 5, one more drop (at 4) will reveal the breaking point. If the ball didn't break before 6, that will be the last drop required (whether the ball breaks or not). With ten floors, one would mark 10, 9, 7, and 4. With fifteen, 15, 14, 12, 9, and 5. The more tests one does before breaking the first ball, the fewer one will need to do afterward to find the exact breaking point.

Although this approach minimizes the worst-case number of drops, it doesn't minimizes the average. One may achieve an average of N drops if there are N(N-1)+1 floors by marking the top floor, then the floor below, then the floor two floors below that (as above), but below that progressing further one should go down four floors, then six, eight, ten, etc. In that case, if the first ball breaks on drop N-I, one will need an average of I additional drops to determine the exact breaking point (cases that take less than I will balance those that take more).

Answer 5

With 2 balls, the strategy seems to be to use the first to determine a window of contiguous possibilities, and the second to step through the window one at a time. This answer mainly tackles the case where the windows are of fixed size, and leaves it to others to make comparisons with the efficiency of algorithms that don't assume windows of fixed size.

If we assume fixed-sized windows of $w-1$ possibilities, we have $N/w$ attempts with the first ball and at worst $w-1$ attempts with the second. On average, we would require half of those attempts in the case of each ball. We therefore want to minimise $(N/w + w-1)/2$, which (by setting its first derivative to 0 and confirming the second derivative is positive) happens when $N = w^2$. This requires a total of $\sqrt{N}$ drops on average.

So the strategy is to start at floor $\sqrt{N}$ and keep dropping the first ball every $\sqrt{N} + 1$ floors until it breaks or until you run out of floors. If it breaks, go down to the floor above the penultimate attempt, and try every floor with the second ball. If the first ball didn't break (and there aren't another $\sqrt{N} + 1$ floors to go), start with the floor above the last attempt and check every floor from there with either ball. (Rounding $\sqrt{N}$: either way will work - round down to do one extra drop with the first ball and round up to do one extra drop with the second, though you probably need to be consistent if you modify the algorithm to use variable window sizes.)

---

Note 1: if we move to variable-sized windows, then observe that after the first drop (if the ball doesn't break), the problem reduces to an identical problem on a building with $N - \sqrt{N}$ floors. If we take the square root of that number as the number of floors to skip for the next attempt, we pair fewer drops of the second ball with more drops of the first ball. The last two floors will be tried one at a time.

Note 2: the constant window solution independently brings out the $\sqrt{N}$ factor like Going hamateur's answer, while the variable window comment is reminiscent of supercat's answer, though the step sizes are different.

Answer 6

If we have $x$ balls and $N$ floors, let the floor we throw the first one be $y$. It'll either break or stay intact. If the former happens, we'll have $x-1$ balls and $y-1$ floors. If the latter happens, we can go upstairs and have $x$ balls and $N-y$ floors.

Balls...................Floors...............Floor to try

$x$.........................$N$.....................$y$

$x-1$..................$y-1$................$z$

$x$........................$N-y$................$t$

Let's say it breaks all the time. Calling our custom operation retrieving $y$ from $x$ and $N$ #, it can be represented like this:

1 # (... $x-2$ # ($x-1$ # ($x$ # $N$))...)

If it never breaks, we can represent it like:

...(($N$ - ($x$ # $N$)) - ($x$ # ($N$ - ($x$ # $N$))))...

If it doesn't, we go higher and higher (let's say, from $t_1$ to $t_k$) until finally one breaks. Each gap between two consecutive $t$s must allow for one less moves with $x-1$ balls than the previous gap. When all the $k$ moves are made, we end up making $k+1$ moves. If the $t_k$th floor is too high but the one before isn't, we shouldn't need an extra move, which means they're consecutive floors. The first gap must allow for $k-1$ moves.

If it breaks, the number of moves we make with $x-1$ balls and $y-1$ floors must be $k$.

If we call the custom operation retrieving the greatest number of floors requiring a given number of moves ♦, then:

$0 ♦ (x-1) + 1 ♦ (x-1) + 2 ♦ (x-1) + ... + n-1 ♦ (x-1) + n < N =< 0 ♦ (x-1) + 1 ♦ (x-1) + 2 ♦ (x-1) + ... + n ♦ (x-1) + n+1$

$m ♦ 1 = m$, so we can start from it using induction. The floor we have to begin with is $n ♦ (x-1) +1$, and then we have can follow the table at the beginning.

If we have no fewer balls than $ceil[log_2N$], we can use binary search.

Answer 7

I'll just throw out a quick answer of $\frac{K \times N^{1/K}}{2}$ where K = balls, N = floors

For N = 100, K = 2, this gives an answer of 10, or $\sqrt{100}$ that others have given.
For N = 1000, K = 3, this gives an answer of 15.
For N = 10000, K = 4, this gives an answer of 20.

Effectively, the fastest way to partition the building is to take the Kth root, but since you have equal probability of testing each value in a root ($\frac{1}{2}$ factor), and you have to repeat over K roots, you get your formula.

Answer 8

Solution for the Two Glass Balls problem

Two Glass Balls

I am in a 100-story building. I have with me two glass balls. I know that if I throw the ball out of the window, it will not break if the floor number is less than X, and it will always breaks if the floor number is equal to or greater than X. Assuming that I can reuse the balls which don't break, find X in the minimum number of throws.

Solution

Suppose we have a strategy with N throws. Then the floor is defined by two numbers: the throw in which the first ball breaks, and the throw in which the second ball breaks. The sum of these two numbers should be less than or equal to N. Hence, the number of floors we can distinguish is the number of different pairs of such numbers, which is equal to N(N+1)/2. This number should be more than 99. Hence, we need at least 14 throws.

Now we would like to build a strategy. To decide the floor for our first throw, we observe that if the ball breaks we need to decide between the leftover floors in 13 steps. Which means, to maximize our choices for the case when it doesn't break, we need to use all the opportunities. That is, we should throw the ball from the 14th floor first. If it breaks, we use the second ball starting from the first floor up.

The second throw should be from the 14 + 13 = 27th floor. And so on.