So Brad had a rule that whenever he got confused in his work, and things didn’t make sense anymore, it was time to go to lunch. After the lunch conversation got confusing, and things didn’t make sense anymore, it was time to go back to work.

Here’s something to work on if you have nothing better to do, or if you do have something better to do, but want to do this anyway.

There is a staircase with 100 stairs. You are given two glass balls and the task of determining which is the highest step they can be dropped from without breaking. What is the optimum method for determining this step?

Additional rules and clarifications.
1. The only experiment you may do is dropping the balls from a step and seeing whether they break.
2. Optimum in this case is defined as performing the least number of tests in the worst case scenario.
3. No matter what step the ball is dropped from it falls all the way to the bottom of the staircase.
4. If the ball breaks at step N, it breaks at all higher steps.
5. Once a ball is broken, it cannot be used in further tests. So if you break both balls without determining the answer, you lose.

If this puzzle was too easy for you, you can try the case where there are N stairs, or M balls, or both. I haven’t done these general cases, so I don’t know how hard they might be.

This entry was posted on Friday, September 14th, 2007 at 8:53 am and is filed under math, puzzle. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

If it breaks, go to Step 2. If it breaks there, it’s Step 1. If it doesn’t break at Step 2, go to Step 4 and repeat.

If it doesn’t break at Step 50, go to Step 75 and repeat the procedure (halving the distance to the top) until you break the first ball, then repeat the above paragraph.

This procedure’s worst case scenario (maximum number of trials) is 50, if the answer is Step 49 (50, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48).
Am I close?

There is a procedure with a much lower maximum number of trials.

Actually, I don’t think your procedure is accurate. If you drop on step 50 and the ball breaks, then step 2 and it doesn’t, then step 4 and it does. How do you know whether it would break on step 3?

Also, a further clarification. The ball might break when dropped from step 1.

See my earlier comment for the clarification that it might break when dropped from step 1.

If you start on step 3 and it doesn’t break, then go to step 6 and it breaks, your next drops should be step 4 and then 5 (can’t do 5 and then 4 because if it breaks on step 5, you’ll never know whether it breaks on step 4).

With your strategy, which is drop at step 3n until it breaks, then step 3n – 2 and step 3n – 1. The worst case scenario is that it first breaks on step 98 which requires 35 drops.

Here is an improvement to your strategy. Drop at each step 4, 8, 12, etc. If it breaks at step 4n, then drop at 4n – 3, 4n – 2, and 4n – 1. Worst case scenario is step 99 which takes 28 drops. This is still not optimal.

I think the key is that you will need to know if the ball breaks on step N and does not break on step N-1. In order to do that, you always have to have a ball left after you break the first ball. It seems to me that you would have to start on step 2 and increase in increments of 2.

Right that you need to know if it breaks on step N and not on step N-1. This means that if you break a ball, you have to go back to one step higher than the last step you didn’t break on and increase in steps of 1.

For example, drop your first ball on step 10 and it doesn’t break. Drop your second ball on step 20 and it breaks. Now you have to go back to step 11. Then increment by 1 until the second ball breaks or you reach step 19.

But this doesn’t mean that you always after to increase in increments of 2.

A clarification: you can’t actually see it breaking as it falls, can you? My first thought was to drop one from the top and note the step on which it broke.

1. Threaten Brad with a glass sphere to the head.
2. If he doesn’t give the answer, throw the sphere at his head. Yeah, it’ll break all right.
3. Threaten him again.
4. If he doesn’t give up the item again, throw the other sphere.
5. Tell him you have a third glass sphere. He’ll definitely tell the answer then.

We are trying to find a step X, where 1 leq X leq 100 (I get an error if I use the equal and less than symbols). So if I randomly pick a step Y from [1,100] then half the time X gt Y and half the time X < Y. If Y gt X, then I have to start at one and make X more steps. If Y < X, then I can pick another random step Y’ and repeat. In the second step, if Y’ gt X, then I have to take X – Y more steps. Each time, I add a step and am able to calculate how many steps it took in the event that the sphere breaks (half the probability for each repetition.

The average number of steps = 1 + 1/2*Avg(X) + 1/4(1 + 1/2*Avg(X – Y)) +1/8(1 + 1 + 1/2*Avg(X – Y’)) + …

Now I need to evaluate the averages. Assuming a uniformly distributed X, Avg(X) = 50.5. I think Avg(X – Y) is going to be Avg(X)/2, and since Y’ is from the interval (Y,100], maybe is Avg(X)/4. In that case:

Avg(S) = 1 + 50.5/2 + 1/4(1 + 50.5/4) + 1/8(1+1+50.5/8)+…
Avg(S) = SUM of i from 0 to INF (i + 50.5/2^i)/2^i

I have no idea what that evaluates to and my Mathematica license has expired.

The average number of steps method I proposed is a bit easier to solve: FLOOR(Avg(X)/2) + 1 = 26.

I suppose that if I were thinking like a mathematician, I’d try to establish how I would prove that given number of steps was a minimum, and use that to construct my method.

Generalizing Brian’s second suggestion (which Brad started to do), there are several strategies with worst-case outcomes of 19 steps. One such worst case scenario is 12, 24, 36, 48, 60, 72, 84, 96, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95. For the strategies of starting at n, incrementing by n until a break at m n, then evaluating (m-1)n+1, +2, … you get the same worst possible outcome — that is, 19 test drops — for n=8 … 13.

Brad, I’m assuming 19 isn’t the best possible worst possible outcome (so to speak) and we need to take a different tack?

Testing both extremes, if it breaks at 14, 1-13 gives a total of 14. If it breaks at 99, then you’ve used 11 and it takes 3 to rule out 96-98.

I figured the step size had to change, thank Brian for going for decrementing steps! Also, I don’t know how to prove this is the best possible, other than to say that 13 doesn’t work with the same trick because it doesn’t get to 100 (i.e. there are more than 13 terms in the sum, which by then are incrementing by 1 or actually decrementing).

The general solution is that N drops covers any number of “steps” in the range from 1/2 N (1 + N) to 1/2 N (1 + N) – 6. The last three steps are always by 3+2+1 so in some cases you can determine the breakpoint with fewer than N steps, but only if it breaks near the top.

Thanks, Andy — I realized 14 was better shortly after I wrote (I was biking through traffic, obviously the best moment to daydream about a math problem 😉 ). Brad, is there a way to show you can’t do better?

Starting at step n has a worst case scenario >= n. You can show that in order to have just = , the sum from 1 to n must be greater than the number of steps.

Another way to put it, step 14 is where the worst case scenario changes from occuring if the ball breaks or if it doesn’t break on the first step.

[…] crowd is at it again with another puzzler/brain teaser/new-age company interview question about marbles and stairs. Spoilers included in the comments so only read the initial post if you actually want to puzzle […]

Here’s my solution:

Start at Step 50.

If it breaks, go to Step 2. If it breaks there, it’s Step 1. If it doesn’t break at Step 2, go to Step 4 and repeat.

If it doesn’t break at Step 50, go to Step 75 and repeat the procedure (halving the distance to the top) until you break the first ball, then repeat the above paragraph.

This procedure’s worst case scenario (maximum number of trials) is 50, if the answer is Step 49 (50, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48).

Am I close?

There is a procedure with a much lower maximum number of trials.

Actually, I don’t think your procedure is accurate. If you drop on step 50 and the ball breaks, then step 2 and it doesn’t, then step 4 and it does. How do you know whether it would break on step 3?

Also, a further clarification. The ball might break when dropped from step 1.

Well, start at Step 3. If it breaks, go to Step 2. If it breaks, it’s Step 1. Repeat for 6, 9, and on up. Maximum number of trials: 33.

(I’m assuming “it doesn’t” or “it always does” aren’t acceptable answers.)

See my earlier comment for the clarification that it might break when dropped from step 1.

If you start on step 3 and it doesn’t break, then go to step 6 and it breaks, your next drops should be step 4 and then 5 (can’t do 5 and then 4 because if it breaks on step 5, you’ll never know whether it breaks on step 4).

With your strategy, which is drop at step 3n until it breaks, then step 3n – 2 and step 3n – 1. The worst case scenario is that it first breaks on step 98 which requires 35 drops.

Here is an improvement to your strategy. Drop at each step 4, 8, 12, etc. If it breaks at step 4n, then drop at 4n – 3, 4n – 2, and 4n – 1. Worst case scenario is step 99 which takes 28 drops. This is still not optimal.

I think the key is that you will need to know if the ball breaks on step N and does not break on step N-1. In order to do that, you always have to have a ball left after you break the first ball. It seems to me that you would have to start on step 2 and increase in increments of 2.

The generalization would be that if you had M balls, you could use steps of M. Doesn’t seem very elegant.

Right that you need to know if it breaks on step N and not on step N-1. This means that if you break a ball, you have to go back to one step higher than the last step you didn’t break on and increase in steps of 1.

For example, drop your first ball on step 10 and it doesn’t break. Drop your second ball on step 20 and it breaks. Now you have to go back to step 11. Then increment by 1 until the second ball breaks or you reach step 19.

But this doesn’t mean that you always after to increase in increments of 2.

A clarification: you can’t actually see it breaking as it falls, can you? My first thought was to drop one from the top and note the step on which it broke.

No, it breaks when it hits the ground. This is not an outside the box puzzle, or a physics trick puzzle.

1. Threaten Brad with a glass sphere to the head.

2. If he doesn’t give the answer, throw the sphere at his head. Yeah, it’ll break all right.

3. Threaten him again.

4. If he doesn’t give up the item again, throw the other sphere.

5. Tell him you have a third glass sphere. He’ll definitely tell the answer then.

We are trying to find a step X, where 1 leq X leq 100 (I get an error if I use the equal and less than symbols). So if I randomly pick a step Y from [1,100] then half the time X gt Y and half the time X < Y. If Y gt X, then I have to start at one and make X more steps. If Y < X, then I can pick another random step Y’ and repeat. In the second step, if Y’ gt X, then I have to take X – Y more steps. Each time, I add a step and am able to calculate how many steps it took in the event that the sphere breaks (half the probability for each repetition.

The average number of steps = 1 + 1/2*Avg(X) + 1/4(1 + 1/2*Avg(X – Y)) +1/8(1 + 1 + 1/2*Avg(X – Y’)) + …

Now I need to evaluate the averages. Assuming a uniformly distributed X, Avg(X) = 50.5. I think Avg(X – Y) is going to be Avg(X)/2, and since Y’ is from the interval (Y,100], maybe is Avg(X)/4. In that case:

Avg(S) = 1 + 50.5/2 + 1/4(1 + 50.5/4) + 1/8(1+1+50.5/8)+…

Avg(S) = SUM of i from 0 to INF (i + 50.5/2^i)/2^i

I have no idea what that evaluates to and my Mathematica license has expired.

The average number of steps method I proposed is a bit easier to solve: FLOOR(Avg(X)/2) + 1 = 26.

I suppose that if I were thinking like a mathematician, I’d try to establish how I would prove that given number of steps was a minimum, and use that to construct my method.

Mathematica says SUM of i from 0 to INF (i + 50.5/2^i)/2^i = 69.333…

So it looks like the average number of steps is not only easier but much smaller.

ps – it looks like some characters might have been dropped from your post, so maybe this isn’t the sum you intended.

Generalizing Brian’s second suggestion (which Brad started to do), there are several strategies with worst-case outcomes of 19 steps. One such worst case scenario is 12, 24, 36, 48, 60, 72, 84, 96, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95. For the strategies of starting at n, incrementing by n until a break at m n, then evaluating (m-1)n+1, +2, … you get the same worst possible outcome — that is, 19 test drops — for n=8 … 13.

Brad, I’m assuming 19 isn’t the best possible worst possible outcome (so to speak) and we need to take a different tack?

Wait, I can get it down to 18. Here’s how:

Start at 18. If it breaks, incrememt by ones from 1 to 17. Worst case: 18.

If it doesn’t break, go to 18 + 17 = 35. If it breaks, evaluate 19… 34. Worst case: 18

If it doesn’t break, to to 18 + 17 + 16 = 51. Worst case: 18

And so on…

You get the idea. But I’m not sure how to prove if this is the best I can do.

Why 18? how about 14?

This gets closest to 100 without going over:

Table[Sum[(14 – n), {n, 0, i}], {i, 0, 10}] =

{14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99}

Testing both extremes, if it breaks at 14, 1-13 gives a total of 14. If it breaks at 99, then you’ve used 11 and it takes 3 to rule out 96-98.

I figured the step size had to change, thank Brian for going for decrementing steps! Also, I don’t know how to prove this is the best possible, other than to say that 13 doesn’t work with the same trick because it doesn’t get to 100 (i.e. there are more than 13 terms in the sum, which by then are incrementing by 1 or actually decrementing).

The general solution is that N drops covers any number of “steps” in the range from 1/2 N (1 + N) to 1/2 N (1 + N) – 6. The last three steps are always by 3+2+1 so in some cases you can determine the breakpoint with fewer than N steps, but only if it breaks near the top.

Nice work, despite the Mathematica notation.

Thanks, Andy — I realized 14 was better shortly after I wrote (I was biking through traffic, obviously the best moment to daydream about a math problem 😉 ). Brad, is there a way to show you can’t do better?

Starting at step n has a worst case scenario >= n. You can show that in order to have just = , the sum from 1 to n must be greater than the number of steps.

Another way to put it, step 14 is where the worst case scenario changes from occuring if the ball breaks or if it doesn’t break on the first step.

[…] crowd is at it again with another puzzler/brain teaser/new-age company interview question about marbles and stairs. Spoilers included in the comments so only read the initial post if you actually want to puzzle […]