This is part of a series of articles that solves popular puzzles and demonstrates the applicability of the puzzle-solving hobby to everyday life. If you love puzzles like I do, and you have a favorite that I haven’t written about yet, please send it to me! I haven’t seen a new one in a long time, and I’d appreciate your message.
The Puzzle
There is a building 100 stories tall. You have a collection of glass marbles. You want to know what is the structural integrity of these marbles: from what height (from which floor) you would need to drop a marble in order to break it. The marbles are substantially identical, so you can assume that if one would break when dropped from a given height, so would any other. You may also assume, of course, that if a marble would break if dropped from a given floor, it would also break if dropped from any floor above that floor. Finally, there is an elevator that, due to its particular design, takes about as much time to travel to or from any given floor as to or from any other.
You don’t have enough information about the annealing process, etc., used to make the marbles to calculate a solution, so you are going to have to find an empirical answer. Fortunately, you can afford to break up to two of your marbles in pursuit of an answer. What is the most efficient way to find your answer?
Solving Discussion (Spoilers!)
If you had only one marble, the solution would be easy: just start at the first floor, drop the marble, retrieve it, then drop it from the second floor, then the third, and so on. In this scenario, you would expect to drop the marble an average of 50.5 times in order to find the right floor. (=(100+1)/2) See that equation? That’s a basic probability equation, used to calculate the expected value of (for example) a die roll. To calculate the average outcome of a die roll, you would add all the potential numbers and then divide by the number of numbers. So for a standard six-sided die, you would add 1+2+3+4+5+6 and then divide by 6. The result would be 3.5. The cool thing is that you can shortcut the process by leaving out all the numbers except the lowest and the highest. See, one plus six equals seven, and two plus five equals seven, and three plus four also equals seven. So just leave out all the stuff in the middle, reduce your divisor to two, and you’ll get the same answer. A mathematician named Friedrich Gauss is often credited for noticing this. The story goes that when Friedrich was a child, his teacher was frustrated by the task of occupying Friedrich’s mind, and assigned him to add together all numbers from 1 to 100, hoping that this would occupy him for a long time. However, Friedrich came back seconds later with an answer. Friedrich, having observed that 1+100=2+99=3+98=4+97=… and so on, simply multiplied 101 by 50, immediately coming up with the answer: 5,050. So anytime you need to average a long series of consecutive numbers, you can just do what Friedrich did and shortcut the process: add the highest number to the lowest, and divide by two.
Moving on: the presence of the second marble triggers a realization. You can break up the number of floors. For example, you might drop the first marble from the 50th floor, and then if it breaks start dropping the second marble at floor one, or if it doesn’t, start dropping the second marble at floor 51. This would be a better solution. How do we know it’s better? Under this revised solution, we now expect to drop the marble an average of 26.49 times. That’s a 1/100 chance that floor 50 will be the breaking floor, in which case we will drop the marble 50 times (first marble breaks at floor 50, second marble gets dropped at each floor 1 to 49 to confirm); a 49/100 chance that one of floors 1 to 49 will be the breaking floor, in which case we will drop the marble 2 to 50 times, with an average of 26; and a 50/100 chance that one of floors 51-100 will be the breaking floor, in which case we will drop the marble 2 to 51 times, with an average of 26.5. Do the math, and you get an expected drop count of 26.49.
Now let me introduce one more wrinkle: if we drop the marble from floor 50 and it doesn’t break, then we have 50 floors left and still two marbles. So rather than starting at floor 51 and continuing upward, we might repeat our method and drop a marble from floor 75. Then if it didn’t break, we might repeat our puzzle again and drop a marble from floor 87, and so on. At this point, the probability calculation is getting more complex, and it looks like this:
| Drop # | Floors Remaining | Floors to Skip | Drop Floor # | Expected Drops | Likelihood | Total |
| 1 | 100 | 50 | 50 | 26.48 | 0.5 | 13.24 |
| 2 | 50 | 25 | 75 | 14.96 | 0.25 | 3.74 |
| 3 | 25 | 12 | 87 | 9.42 | 0.12 | 1.13 |
| 4 | 13 | 6 | 93 | 7.33 | 0.06 | 0.44 |
| 5 | 7 | 3 | 96 | 6.67 | 0.03 | 0.2 |
| 6 | 4 | 2 | 98 | 7.00 | 0.02 | 0.14 |
| 7 | 2 | 1 | 99 | 7.00 | 0.01 | 0.07 |
| 8 | 1 | 1 | 100 | 8.00 | 0.01 | 0.08 |
| 19.04 |
So instead of 26.49, the average number of drops for this iterative process is 19.04. It’s better.
Now that you have a framework for analysis, the question therefore becomes, what is the most efficient way to split up 100 floors with two marbles? One solution I’ve seen goes like this: realize that the two marbles are basically two factors in a multiplication problem which must have as its product a number greater than or equal to 100, and the goal is to have the sum of the two numbers be as low as possible. If you look at a few possibilities, you’ll notice a pattern… 2 times 50 equals 100 and sums to 52; 4 times 25 equals 100 and sums to 29; 5 times 20 equals 100 and sums to 25… as the two numbers get closer together, their sum goes down. So in order to get the two numbers as low as possible, let’s make them the same. Find the square root of 100, which is 10. So 10 times 10 equals 100 and sums to 20 – your answer is to drop the first marble at floors 10, 20, 30, 40, 50, 60, 70, 80, 90, and 100, see where it breaks, and then run the marble up through the 9 floors below that floor. This solution has a pleasing simplicity and gives you an expected process run time of 10.9, calculated as follows:
| Drop # | Floors Remaining | Floors to Skip | Drop Floor # | Expected Drops to Find Result | Likelihood | Weighting |
| 1 | 100 | 10 | 10 | 6.4 | 0.1 | 0.64 |
| 2 | 90 | 10 | 20 | 7.4 | 0.1 | 0.74 |
| 3 | 80 | 10 | 30 | 8.4 | 0.1 | 0.84 |
| 4 | 70 | 10 | 40 | 9.4 | 0.1 | 0.94 |
| 5 | 60 | 10 | 50 | 10.4 | 0.1 | 1.04 |
| 6 | 50 | 10 | 60 | 11.4 | 0.1 | 1.14 |
| 7 | 40 | 10 | 70 | 12.4 | 0.1 | 1.24 |
| 8 | 30 | 10 | 80 | 13.4 | 0.1 | 1.34 |
| 9 | 20 | 10 | 90 | 14.4 | 0.1 | 1.44 |
| 10 | 10 | 10 | 100 | 15.4 | 0.1 | 1.54 |
| 10.9 |
… or, if you follow the iterative strategy, 10.81:
| Drop # | Floors Remaining | Floors to Skip | Drop Floor # | Expected Drops to Find Result | Likelihood | Weighting |
| 1 | 100 | 10 | 10 | 6.4 | 0.1 | 0.64 |
| 2 | 90 | 9 | 19 | 6.9 | 0.09 | 0.62 |
| 3 | 81 | 9 | 28 | 7.9 | 0.09 | 0.71 |
| 4 | 72 | 8 | 36 | 8.4 | 0.08 | 0.67 |
| 5 | 64 | 8 | 44 | 9.4 | 0.08 | 0.75 |
| 6 | 56 | 7 | 51 | 9.9 | 0.07 | 0.69 |
| 7 | 49 | 7 | 58 | 10.9 | 0.07 | 0.76 |
| 8 | 42 | 6 | 64 | 11.3 | 0.06 | 0.68 |
| 9 | 36 | 6 | 70 | 12.3 | 0.06 | 0.74 |
| 10 | 30 | 5 | 75 | 12.8 | 0.05 | 0.64 |
| 11 | 25 | 5 | 80 | 13.8 | 0.05 | 0.69 |
| 12 | 20 | 4 | 84 | 14.3 | 0.04 | 0.57 |
| 13 | 16 | 4 | 88 | 15.3 | 0.04 | 0.61 |
| 14 | 12 | 3 | 91 | 15.7 | 0.03 | 0.47 |
| 15 | 9 | 3 | 94 | 16.7 | 0.03 | 0.5 |
| 16 | 6 | 2 | 96 | 17.0 | 0.02 | 0.34 |
| 17 | 4 | 2 | 98 | 18.0 | 0.02 | 0.36 |
| 18 | 2 | 1 | 99 | 18.0 | 0.01 | 0.18 |
| 19 | 1 | 1 | 100 | 19.0 | 0.01 | 0.19 |
| 10.81 |
The thing is, you can immediately improve this solution to 10.74 by just changing the first drop floor to 11. In fact, by just experimenting a little, changing the first 6 drops to floors 11, 22, 33, 44, 55, and 66, you can get down to 10.44 drops. So there has to be a better answer.
So far, the best result I have found is to drop the first marble at floors 15, 28, 40, 50, 59, 67, 74, 80, 85, 89, 92, 95, 97, 99, and 100; yielding an expected drop count of 10.33. The calculation for which floor to drop it from is to divide the number of floors remaining by the log2 of the number of floors remaining. So if you have 100 floors remaining, the log2 of 100 is 6.64, 100 / 6.64 is 15, so you make your first drop from the fifteenth floor. Here’s how it breaks down:
| Drop # | Floors Remaining | Floors to Skip | Drop Floor # | Expected Drops | Likelihood | Weighting |
| 1 | 100 | 15 | 15 | 8.9 | 0.15 | 1.34 |
| 2 | 85 | 13 | 28 | 8.9 | 0.13 | 1.16 |
| 3 | 72 | 12 | 40 | 9.4 | 0.12 | 1.13 |
| 4 | 60 | 10 | 50 | 9.4 | 0.1 | 0.94 |
| 5 | 50 | 9 | 59 | 9.9 | 0.09 | 0.89 |
| 6 | 41 | 8 | 67 | 10.4 | 0.08 | 0.83 |
| 7 | 33 | 7 | 74 | 10.9 | 0.07 | 0.76 |
| 8 | 26 | 6 | 80 | 11.3 | 0.06 | 0.68 |
| 9 | 20 | 5 | 85 | 11.8 | 0.05 | 0.59 |
| 10 | 15 | 4 | 89 | 12.3 | 0.04 | 0.49 |
| 11 | 11 | 3 | 92 | 12.7 | 0.03 | 0.38 |
| 12 | 8 | 3 | 95 | 13.7 | 0.03 | 0.41 |
| 13 | 5 | 2 | 97 | 14.0 | 0.02 | 0.28 |
| 14 | 3 | 2 | 99 | 15.0 | 0.02 | 0.3 |
| 15 | 1 | 1 | 100 | 15.0 | 0.01 | 0.15 |
| 10.33 |
What I haven’t done yet is prove mathematically that this is the best possible solution. One day, when I feel like wringing more fun out of this puzzle, I’ll do that.
The Point
The hobby of puzzle-solving has a lot of real-world practicality. When you discover a solution for yourself, it’s like adding a tool to your mental toolbox. When you later encounter similar problems, the tool is there waiting to help you solve it.
This a search efficiency problem, and it deals more specifically with the concept of an index. If you’ve ever opened a dictionary or used a library, you’ve manually operated an index. If you’ve ever run a Google search, then you’ve benefited from the automatic indexing that Google’s computers are always doing. Google has not only solved this puzzle, it has solved the next several levels of this puzzle (i.e., what is the optimal number of marbles to use? what if there are 10,000,000,000 floors? what if you don’t have the elevator, but you have to walk up and down the stairs instead?) and trained massive server farms to execute the solutions and probably also to solve this type of puzzle on the fly.
Each marble is a metaphor for a level of indexing. Let’s say instead of floors on a building, you are looking for a word in a dictionary. Your first index is the tabs on the side of the dictionary that separate the words by their first letter. Your second index consists of the two words at the top of each page (e.g. “apple – art”) that tell you the ranges of words that appear on each page. Then your third index is the fact that the words on the page are in an order you understand, so you can quickly look over the page and find your word.
This puzzle, like others, has valuable real-world applications. In my computing career, I readily recognized the value of indexing when I saw process run times shrink from 28 hours to 7 minutes thanks to the addition of an index to a data set. Later, in my legal career, I was confronted with a stack of a few hundred unsorted documents, and separately a lengthy and unsorted list of long ID numbers. I needed to pull the documents that bore the listed ID numbers. I was able to realize that I could save myself a bunch of time by first sorting the documents by ID number, thereby allowing me to index the documents and vastly improve my average search time.
I hope this puzzle helps you as it has helped me.