Category: puzzles

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.

Today’s post addresses three puzzles that are all similar to the recent “Three Slips of Paper” puzzle: Monty Hall, Bertrand’s Boxes, and The Three Prisoners.  They are as follows:

Monty Hall

This puzzle is named for an old American television game show called Let’s Make a Deal, and more particularly for its host, Monty Hall.  On that game show, contestants were sometimes presented with three doors, each with a prize behind it, and asked to pick a door (numbered 1, 2, or 3); the contestant would then receive whatever prize was behind the door.  It might be something really nice, like a car, or it might be something less desirable, like a cheap coupon.  The puzzle goes like this:

You’re a contestant on a game show.  The host presents you with three doors to choose from, and informs you that behind the three doors are a goat, another goat, and a new car – but of course he doesn’t tell you which is behind which door.  You are going to pick a door, but then before you see what’s behind that door, the host (who knows what’s behind all the doors) will open another of the doors to reveal a goat.  You will then have the option to either take whatever prize is behind the door you initially chose, or you can switch to the other still-unopened door and take whatever prize is behind that door.  How can you maximize your odds of getting the car?

It was popularized by Marilyn vos Savant.

Monty Hall Solution

First off, obviously when you pick a door the first time, your odds of picking the door with the car are one in three.  The “trick” of this puzzle comes when the host then subsequently reveals one of the goats.  A lot of people, upon first confronting this puzzle, think that the reveal increases the odds of finding the car to one-half; they figure that once the goat is revealed, each of the remaining doors has a one-in-two chance of hiding the car.  That reasoning, however, ignores the contestant’s act of selecting a door.  See, that first contestant-selected door had only a one-in-three chance of concealing the car, so when the host opens one of the other doors to reveal a goat, that collapses the remaining two-thirds probability that the car was not behind the contestant-selected door into the remaining unselected, unopened door.  To prove it, here’s the decision tree:

 

Bertrand’s Boxes

Bertrand’s Boxes is named for Joseph Bertrand, who published it in his book Calcul des probabilités, published in 1889.

You are confronted with three boxes: one that contains two gold coins, a second that contains one gold coin and one silver coin; and a third that contains two silver coins.  You select a box at random and draw a coin at random from that box.  The coin happens to be gold.  What are the odds that the remaining coin in the box is also gold?

Bertrand’s Boxes Solution

Having just seen the Monty Hall puzzle, you probably figured out pretty quickly that the answer is two-thirds.  However, most people seeing this puzzle for the first time figure that drawing a gold coin narrows the puzzle down to two boxes, one of which contains two gold coins, and they’ll figure the odds are one in two.  As with other similar puzzles, however, the answer is readily discernible using a decision tree:

Just eliminate the possibilities that didn’t happen, then do the math on the remaining possibilities.

The Three Prisoners

The Three Prisoners puzzle was published in Martin Gardner’s Scientific American column in 1959.  I grew up on Martin Gardner’s books of puzzles, and thoroughly loved them.  Here’s his formulation:

“Three prisoners, A, B and C, are in separate cells and sentenced to death. The governor has selected one of them at random to be pardoned. The warden knows which one is pardoned, but is not allowed to tell. Prisoner A begs the warden to let him know the identity of one of the others who is going to be executed. ‘If B is to be pardoned, give me C’s name. If C is to be pardoned, give me B’s name. And if I’m to be pardoned, flip a coin to decide whether to name B or C.’

“The warden tells A that B is to be executed. Prisoner A is pleased because he believes that his probability of surviving has gone up from 1/3 to 1/2, as it is now between him and C. Prisoner A secretly tells C the news, who is also pleased, because he reasons that A still has a chance of 1/3 to be the pardoned one, but his chance has gone up to 2/3. What is the correct answer?”

I would add one more key piece of information: the warden agrees to Prisoner A’s proposal and does not lie.

The Three Prisoners Solution

Prisoner C is correct in his thinking; based on this new information, Prisoner C’s odds of being pardoned are two-thirds.

As in the Bertrand’s Boxes puzzle, just draw out the decision tree, then eliminate the possibilities that didn’t happen.  In the puzzle scenario, the warden said that Prisoner B would be executed, so this eliminates the scenarios wherein he said that Prisoner C would be executed.  That leaves two possibilities: one in which the warden says that Prisoner B will be executed and Prisoner A gets pardoned (one-in-six overall chance) and one in which the warden says that Prisoner B will be executed and Prisoner C gets pardoned (one-in-three overall chance).  Because the warden’s statement eliminated all other possibilities, add up the odds and divide out to determine that, where the warden says B will be executed, C has a two-thirds chance of being pardoned.

Of course the odds would be different if the warden had, entirely of his own volition and without any structure, simply announced that Prisoner B would be executed.  In that scenario, there would then be a 50% chance each for A or C to be pardoned.  The critical element of the puzzle is that the warden agrees to follow the system set out by Prisoner A.

The Point

It’s good to look at these three similar puzzles together because it emphasizes the fact that the solution to a seemingly esoteric and obscure situation can be applied to other challenges in life. Even though the decision trees for these three puzzles are drawn differently, they are mathematically the same.  The different decision trees represent different valid ways to approach the same basic puzzle.  Once you have internalized the way of solving these puzzles, you can be on the lookout for other opportunities to gain valuable information in life by carefully applying reason to the facts available to you.

These are also interesting puzzles to look at together with the preceding “Three Slips of Paper” puzzle, even though they are not identical to that one, because the fundamental thought process is the same. Once you know how to solve these information-probability puzzles, they’re a breeze.

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

I have seen this puzzle in many different places, but this particular phrasing is taken (with minor edits for clarification) from the Car Talk radio show.

“Three different numbers are chosen at random, and each is written on one of three slips of paper. The slips are then placed face down on the table. The objective is to choose the slip upon which is written the largest number.

Here are the rules: You can turn over any slip of paper and look at the amount written on it. If for any reason you think this is the largest, you’re done; you keep it. Otherwise you discard it and turn over a second slip. Again, if you think this is the one with the biggest number, you keep that one and the game is over. If you don’t, you discard that one too, and you’re stuck with the third.”

At first glance, you might think the odds of getting the highest number are one in three. But I wouldn’t be bothering to write this down if it were that simple, would I?

Solving Discussion

Any time you’re trying to maximize an outcome, your go-to tool should be a decision tree. They cover these things in business classes. It’s like a flow chart that reads left-to-right. Here’s what the decision tree looks like if you keep the first piece of paper you pull:

Assigning a value of “1” to a “win” where you found the highest number, and a value of “0” to a “loss” where you are stuck with one of the lower numbers, the expected value of this strategy is 0.333…. Which is just a fancy way of saying you have a one in three chance of getting the highest number this way.

Now, this becomes a pretty simple puzzle because there are really only three other strategies possible within the framework of the rules:

1. Discard the first number you pull and keep the second.
2. Discard the first and second numbers you pull and keep the third.
3. Discard the first number you pull, look at the second number, and then decide whether to discard the second number and pull the third.

You can reason out pretty readily that options 1 and 2 are not different from just keeping the first piece of paper you pull. Option 3, however, is interesting because there’s a choice involved. Does that choice make a difference? If you want to work it out yourself, go ahead; this page will still be here. If not, read on…

The winning strategy for solving this puzzle is to pull a number at random, look at it, discard it, and pull a second number. Then, if the second number is higher than the first, keep it. If the second number is lower, discard it and keep the third and final number. Here’s the decision tree:

So if you discard the first number you pull, there is a one-in-three chance that it was the biggest number and you lose. There is also a one-in-three chance that it was the middle number. If it was the middle number, and the second number you pull is the highest number, then by following the strategy you will keep it and you will win. If the second number you pull in this situation is the lowest number, then by following the strategy you will discard it and pull the third number, which will be the highest number, and you will win. So this strategy means you always win if the first number you pull is the middle number. This means that so far, we have a one-in-three chance of losing and a one-in-three chance of winning. What happens in the remaining one-in-three scenario where the first number pulled is the lowest number? Well, this means that the second number pulled will definitely be higher than the first, so we will keep it, and there is a one-in-two chance that it was the highest number and a one-in-two chance that it was the middle number. So on the one-in-three chance that the first number pulled is the lowest number, we have a 50% chance of winning and a 50% chance of losing. Adding all these percentages up, we have a one-in-three chance of losing, a one-in-three chance of winning, another one-in-six (33.33% times 50%) chance of losing, and another one-in-six chance of winning. That comes out to a one-half chance of winning and a one-half chance of losing. That’s better than the one-in-three chance given by random selection, so this is a superior strategy.

Beyond the Puzzle

It’s useful to work out this sort of small-scale puzzle to learn basic mathematical patterns, but in order to really wring every bit of value out of a puzzle and internalize the underlying concepts, it’s important to expand it and see how it can apply in other contexts. In order to solve the puzzle, we worked out what happens with a set of three numbers, but what happens with a set of ten? Should we just examine and discard the first selection? Examine and discard one-third of the numbers? Discard all but three of the numbers and then follow the strategy from the first puzzle? Follow some other strategy? Let’s find out…

First off, the odds are pretty easy to calculate if we decide to discard seven of the ten and then follow the strategy from the first puzzle. There is a 30% chance that the highest number remains undiscovered after discarding 70% of the numbers, and the first puzzle solution gives us a 50% chance of finding the highest of the three remaining numbers, so our overall odds of winning are 15%. This is a good check; it proves that the first puzzle still has value here. The odds of 15% beat the odds of 10% that we get if we choose at random. But can we beat 15%? Obviously, we can: if we just slightly modify the original strategy to say that we will discard the ninth number not only if it is smaller than the eighth, but if it is smaller than any of the first eight numbers, this of course slightly betters the odds. These first couple of intuitive tests having borne fruit, we are motivated to proceed to look for the best solution by working through the decision trees.

Let’s next look at the other obvious permutation of the strategy from the original puzzle: pick a number, look at it, discard it, then proceed to draw additional numbers until we find one that is higher than the first number. This gives us:

• a 10% chance of drawing the highest number first, in which case we lose;
• a 10% chance of drawing the second-highest number first, in which case the next number we draw that is higher than any preceding number will necessarily be the highest number in the set, which means we will win;
• a 10% chance of drawing the third-highest number first, in which case there is a 50-50 chance that the next number we draw that is higher than any preceding number will be the highest number;
• a 10% chance of drawing the fourth-highest number first, in which case there is a one-in-three chance that the next number we draw that is higher than any preceding number will be the highest number;

… and so on. You see the pattern. The odds of selecting the highest number via this method are (.1 × 0) + (.1 × 1) + (.1 × .5) + (.1 × .333) + (.1 × .25) + (.1 × .2) + (.1 × .1667) + (.1 × .1429) + (.1 × .125) + (.1 × .111), totaling about 28.3%. Already this is way better than any prior answer. But can we improve on it further?

Now let’s try drawing three numbers, discarding them all, and proceeding from there. The first thing you’ll notice is that your decision tree becomes a LOT more complex if you try to map out all the possibilities of which three numbers you might draw. In fact, there are 720 (ten times nine times eight) possibilities for what those first three numbers could be. We need to collapse this down some. So let’s think: which of these possibilities are alike? It turns out that the only thing that matters about those first three numbers is the highest number. Think about it: if the highest of the first three numbers is, let’s say, the second-highest number in the set, it doesn’t matter what the other two are. The rest of the puzzle proceeds the same. So, collapsing things down: in 216 out of the 720 possibilities, the highest of the three numbers is the highest number in the set; in 168 of the 720 possibilities, the highest of the three numbers is the second-highest number in the set; in 126 of the 720, the highest of the three is the third-highest in the set; in 90 of the 720, the highest of the three is the fourth-highest in the set; 60 of 720, fifth-highest; 36 of 720, sixth-highest; 18 of 720, seventh-highest; 6 of 720, eighth-highest; and of course if you have three different numbers out of a set of ten, the highest of the three can be no smaller than the third-smallest, which is also the eighth-highest. Add ‘em up and you get 720.

So what are the odds of victory in each of these scenarios? Well, if the highest number got drawn as one of the first three, we lose. And the rest of the odds track what we just worked out in the preceding scenario: 100% if the highest among the three is the second-highest of the set; 50% if the highest among the three is the third-highest of the set; one-in-three if the highest among the three is the fourth-highest of the set; and so on. Multiplying it out, our total comes to almost a 40% chance of finding the highest card! (39.75% to be precise). So by reviewing and discarding almost a third of the numbers, thereby accepting an automatic 30% chance of failure, we actually boost our overall odds of success!

Now, just for the sake of confirmation, let’s run the math if you discard four. … Actually, let’s not do that part together. If you want to, I hope you will, but I’m just going to give you the answer: 39.83%. And then if you run the numbers on discarding five, you get 37.28%. So we’ve identified a peak at around three or four cards discarded. The key seems to be to discard a third of the numbers. For example, if you have 12 numbers, the peak odds are 39.6% if you discard four cards.

The Point

Can you think of a parallel scenario from real life? A situation where you have to get “involved,” let’s say, with an unknown in order to learn its value, and then before you can learn the value of another unknown, you have to discard the first one? How about dating? After you’ve narrowed the field to a set of likely possibilities, you have to date one of your prospects in order to find out how compatible you are. But before you can investigate another prospect, you are typically going to have to discard the first one… and by the time you’ve investigated your second prospect, the first will probably be involved with someone else and therefore no longer an option.

The metaphor isn’t perfect, but it’s pretty good. As a young, single person looking for a relationship, you typically have no idea what the range of possible values are for relationship bliss. Even after you’re in a relationship, it’s impossible to tell how your relationship stacks up in terms of objective quality. You need to experience a few relationships in order to have some confidence that you’ve found a good match.

So to give a real-world example: let’s say you’re in college. Out of your fellow students, numbering 20,000, you winnow them down based on criteria such as age, religion, sex, socio-economic background, geography, similar interests, physical attractiveness, and maybe other factors to ten viable dating prospects. You could pick the one that, based on your best guess, seems best to you, but let’s face it: you’re not that far along in your life. There’s a pretty sizeable margin of error on your guess. Your best move is really to get some experience by dating a few people, and then start looking in earnest.  If you have ten prospects, this puzzle suggests that your optimum strategy would be to try out four of them to maximize the value of your experiences.  Of course this puzzle is just one equation among many that would inform an actual decision, but it does suggest a base experience level is necessary to learn enough about yourself and relationships generally to make further decisions with some degree of confidence.  It also suggests that, if a person has a high number of potential mates, it makes sense to test out more of them before beginning to look in earnest.

The most obvious way in which this puzzle differs from reality is that it is not actually a loss scenario if you fail to end up with the best possible mate, and of course this fact changes the decision tree significantly.  However, it does perhaps describe that persistent part of the human psyche that does feel like anything short of the “best” is failure.

This is a wonderful puzzle because it provides an example of how to think through decisions in a limited-information environment.  Sometimes people lock up when presented with a decision and incomplete information, and will sometimes throw up their hands and make a decision at random; especially in a situation like this, where losing is more likely than winning.  However, you can frequently increase your odds in an apparently hopeless situation by just carefully thinking through what you can deduce from the information you do have, and what else you can learn efficiently in the time you have.

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 log₂ of the number of floors remaining.  So if you have 100 floors remaining, the log₂ 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.