One of the most interesting features of the human brain is its ability to extract general principles from specific cases. According to many philosophers and psychologists, generalization is an important aspect of cognition, nurturing and expanding the brain's thinking powers at the same time. The German philosopher Hegel put it as follows: "An idea is always a generalization, and generalization is a property of thinking. To generalize means to think" (from The Philosophy of Right, 1821).
Perhaps the most brain-boosting aspect of puzzle-solving is the fact that, often, a particular puzzle genre spurs us on to search for some hidden general pattern or structural principle inherent in the various versions of the puzzle. In this blog, it is the well-known genre of "matching" puzzles that will be used to show how this innate capacity of the brain unfolds-a capacity that it is present in all of us, even those who dislike puzzle-solving.
Let's start with a simple puzzle of this type:
In a box there are 20 billiard balls, 10 white and 10 black, scattered haphazardly in the box. They all feel the same. With a blindfold on, what is the least number of balls you must draw out in order to get a pair of balls that matches in color: that is, two white balls or two black balls?
Many newcomers to this kind of puzzle tend to reason somewhat along the following lines:
If the first ball that I pull out is white, then I will need another white one to match it. But the next ball might be black, as might be the one after that, and the one after that, and so on. So, in order to be sure that I get a match, I must (in principle) remove all the black balls from the box-10 in all. The next one I remove after that will then necessarily be white, since that is the color of the balls that are left in the box. Including the first white ball I took out, the ten black balls that I had to remove, and the one white ball that finally matches, 12 is the minimum number of balls I will need to draw out.
This line of reasoning, however, fails to grasp what the puzzle really requires one to do-to match the color of two balls, not just the color of the first one drawn out, which happened to be white. The correct reasoning goes like this. Suppose the first ball you pull out is in fact a white one. If you're lucky the next ball you draw out will also be white, and it's game over! But you cannot assume this luck-based scenario. You must, on the contrary, assume the worst-case scenario, that is, that the next ball you pull out is black. Thus, after two draws, you will have taken out one white and one black ball from the box, under the worst-case scenario. Obviously, you could have pulled out a black ball first and a white one second. The end result would have been the same: one white and one black ball after two draws.
Now, here's the crux of the solution-the next ball you draw from the box will, of course, be either white or black. No matter what color this third ball is, it will match the color of one of the two already drawn out. If it is white, it will match the white ball outside the box; if it is black, it will match the black ball outside the box. You will then have a pair of balls of matching color. So, the least number of balls you will need to draw from the box in order to ensure a pair of matching balls is three.
Next, let's add a color to the mix.
In a box there are 30 billiard balls, 10 white, 10 black, and 10 red scattered haphazardly in the box. Again, they all feel the same. With a blindfold on, what is the least number of balls you must draw out this time in order to get a pair of balls that matches: that is, two white balls or two black balls or two red balls?
Again, let's increase the color mix by one more.
In a box there are 40 billiard balls, 10 white, 10 black, 10 red, and 10 green scattered haphazardly in the box. Again, they all feel the same. With a blindfold on, what is the least number of balls you must draw out in order to get a pair of balls that matches: that is, two white balls or two black balls or two red balls or two green balls?
Let's increase it one last time.
In a box there are 50 billiard balls, 10 white, 10 black, 10 red, 10 green, and 10 blue scattered haphazardly in the box. Again, they all feel the same. With a blindfold on, what is the least number of balls you must draw out in order to get a pair of balls that matches: that is, two white balls or two black balls or two red balls or two green balls or two blue balls?
At this point, do you see a pattern? What is it? Does changing the number of balls of one color change the pattern? That is, what happens if the number of balls in the last puzzle is 10 white, 9 black, 6 red, 4 green, and 1 blue?
Here's an interesting and trickier version of this type of puzzle:
If there are 6 pairs of black shoes and 6 pairs of white shoes in a box, all mixed up, what is the least number of draws you must make with a blindfold on to be sure of having a matching pair of black or white shoes?
To conclude, it is my belief that one of the most important aspects of puzzle-solving is its ability to stimulate and enhance generalization processes spontaneously. It seems that the human brain cannot stop at the particular, but is programmed to extract principles of general structure or design in the information that it processes. As the English historian Thomas Babington Macaulay observed in the Edinburgh Review of 1825, "Generalization is necessary to the advancement of knowledge." Solving puzzles such as those presented here may show why this is so and why it comes so naturally to us.
Answers
The reasoning for the 30-ball, three-color version is the same. You start by assuming the worst-case scenario. What is that? It is drawing out three balls of three different colors-white, black, and red. Now, the fourth ball you draw out, no matter what color it is, will match one of the three colors outside the box, since it can only be white, black, or red.
The reasoning for the 40-ball, four-color version is exactly the same. You start by assuming the worst-case scenario, which consists in drawing out four balls of four different colors-white, black, red, and green. The fifth ball you draw out, however, will match one of these four outside the box.
Needless to say, the reasoning for the 50-ball, five-color version is also the same. You start by assuming the worst-case scenario. For this version, this consists in drawing five balls of five different colors-white, black, red, green, and blue. The sixth ball you draw out, however, will match one of these five outside the box.
What is the general pattern? When there are two colors of balls in the box, we need three draws to get a match; when there are three, we need four draws; when there are four, we need five; when there are five, we need six. This pattern will continue on and on because the reasoning is the same in all cases. The pattern is, simply, that one more draw than the number of colors is required to ensure that a pair of balls of matching color is drawn out.
Changing the number of balls of the colors does not change the solution pattern. Here's why. Let's say there are 10 white and only 1 black in the box. Under the worst-case scenario, you will still draw out 1 white and 1 black. However, the third draw will necessarily produce a white ball-that's the only color of balls left inside the box-to match the white ball already drawn out. The same kind of reasoning can be used over and over again. So, the general rule remains, no matter how many number of balls are involved for each color.
The answer to the shoe problem is 13. There are 24 shoes in all in the box: 6 pairs of black shoes = 12 black shoes; 6 pairs of white shoes = 12 white shoes. Of the 24, half are right-foot-fitting and half are left-foot-fitting. In a worst-case scenario, we might pick all 12 left-foot-fitting shoes (6 of which are black and 6 white) or all 12 right-foot-fitting shoes (6 of which are black and 6 white). The thirteenth shoe drawn, however, will match one of these twelve.
