One morning at precisely 9:00 AM a monk begins walking up a mountain path. He takes his time, stopping several times to rest along the way. He arrives at the temple at the mountain's summit at precisely 5:00 PM that evening. The next day, the monk leaves the temple at precisely 9:00 AM and makes his way back down the path. Again, he takes his time and rests at several points along the journey. He arrives back at his original starting point at precisely 5:00 PM that evening. Is there any time when the monk is in exactly the same spot on both days? Click below to see the answer.
Since the monk isn't travelling at a constant rate of speed on his two trips, it's tempting to say that there's not necessarily a time when the monk is in the same spot at the same time on both days. However, such a time and place must exist. To see why, take a look at the following plot of the two trips.
Imagine that you can grab the lines on the plot and bend them however you like, you just can't move the endpoints, and the lines must stay within the bounds of the two axes. No matter how you stretch and bend the lines, they must cross somewhere.
To think of it another way, imagine there were two monks, one at the base of the mountain and one at the temple, and they started their journeys on the same day. If they were to begin and end their trips at the same time, they would have to pass each other on the path at some point during the day.
The pigeonhole principle states that if a group of pigeons flies into a set of pigeonholes, and there are more pigeons than pigeonholes, then there must be at least one pigeonhole with two pigeons in it. More generally, if k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects. Despite its seeming simplicity (perhaps obviousness), it can be used to solve a surprising range of problems in probability, number theory, and computer science, just to name a few. See if you can use it to solve the following three problems.
(Warm up) A drawer contains a dozen blue socks and a dozen black socks, all unmatched. If the room is dark, how many socks do you have to take out to be sure you have a matching pair?
Prove that there are at least two people in Tokyo with exactly the same number of hairs on their heads.
Prove that if five distinct integers are selected from the numbers 1 through 8, there must be at least one pair with a sum equal to 9.
Click below to see the answers.
(Warm up) If you've only heard one problem involving the pigeonhole principle, it was probably the classic sock drawer problem. You only need to pick three socks to make sure you have one matching pair. When you pick two socks, you might already have a matching pair, or you might have one of each color sock. Selecting one more sock ensures that you have at least two socks of one color or the other.
The Tokyo hairs problem sounds like something you might be asked as a "brain teaser" interview question. If you're stuck in an interview, then the first step is to show off your estimating skills. Since we're not in that situation, we can just use Google to find out that there are about 100,000 hairs on the average human head, and that Tokyo is home to about 13.6 million people. That's more than enough people for our proof. For the sake of simplicity, let's say that 200,000 is the maximum number of hairs a person can have on their head. Then, if you select 200,001 people who happen to each have a distinct number of hairs on their heads (zero is a valid number of hairs to have on your head), you only need one more to ensure that two people have the same number of hairs. (Note: This puzzle will work with any city larger than 200,001 residents.)
To see how the pigeonhole principle applies to this problem, you just need to group the numbers 1 through 8 in pairs that sum to 9. {1,8}, {2,7}, {3,6}, {4,5}. Now, if I select four distinct numbers from that range, I might select one number from each of the four pairs. If I select a fifth number, then I must complete one of the pairs that sums to 9.
Suppose you have two cups in front of you, one with precisely 8 fluid ounces of coffee, and the other with precisely 8 fluid ounces of cream. You take precisely one teaspoon of the cream and add it to your coffee. You stir it in so that it's thoroughly mixed. Then you take precisely one teaspoon of that coffee/cream mixture and put it back into the cup of cream. Does the cup of coffee have more cream in it, or does the cup of cream contain more coffee? Click below for the answer.
This question is a bit tricky. It's tempting to think that the cup of coffee contains more cream, because the teaspoon of cream added to the coffee was 100% pure, while the teaspoon of coffee added to the cream was diluted. However, it's important to remember that the total volume of each vessel changed by one teaspoon after the first transfer of fluid. The coffee/cream mixture was greater by two teaspoons than the pure cream. Before I reveal the answer, let's re-frame the question in discrete units.
Suppose that instead of liquids, our two cups contained 20 black marbles and 20 white marbles. You take 5 white marbles and thoroughly mix then in with the black marbles. Then you randomly select 5 marbles from the black/white marble mixture and place them back in the cup of white marbles. Are there more white marbles in the black cup or more black marbles in the white cup?
If you're like me, you may be tempted to treat this as a probability problem, but it isn't one. When I think about randomly drawing marbles, I want to immediately start writing a quick simulation in Python, but as you'll see, that isn't necessary. We can easily enumerate all possible outcomes in this scenario to find the answer to the question. When we draw 5 marbles from the cup with a mixture of 20 black and 5 white marbles, then place them in the cup with the other 15 white marbles, there are only 6 possible outcomes:
black
white
black/white mix
white/black mix
5
0
15/5
15/5
4
1
16/4
16/4
3
2
17/3
17/3
2
3
18/2
18/2
1
4
19/1
19/1
0
5
20/0
20/0
So the black/white ratio of the 5 marbles in the second transfer doesn't really matter. The end result is that there are always the same number of white marbles in the black cup as there are black marbles in the white cup.
The same is true of the original coffee/cream problem. The ratio of the two liquids in the teaspoon that is transferred to the cup of cream is such that you will end up with precisely the same volume of coffee in your cream as there is cream in your coffee. So the answer to the trick question posed at the beginning is "neither, they are the same."
The letters of the (English) alphabet can be grouped into four distinct categories.
A M
B C D E K
F G J L
H I
Based on the categories established by the first 13 letters, can you place each of the remaining 13 letters in the correct group?
This question is tricky because it's not about the sounds the letters make, or the frequency of letters, but about the shapes of the (capital) letters.
In the solution to A Unique Number, I asked a bonus question. "Can you think of a number whose letters when spelled out in English are all in alphabetical order?" Several people replied via Twitter with the correct answer of "forty." You may have found a shortcut to the solution if you noted that none of the single-digit numbers have their letters in alphabetical order, nor does the word "teen." This allows you to skip ahead to 20, 30, etc. Can you use a similar strategy to answer the following questions?
What is the lowest number that requires the five vowels A, E, I, O, and U only once each in its spelling?
What is the lowest number that requires the six letters A, E, I, O, U, and Y only once each in its spelling?
Click below to see the answers.
The lowest number that requires the five vowels A, E, I, O, and U once each in its spelling is 206 (two-hundred and six).
The lowest number that requires the six letters A, E, I, O, U, and Y once each in its spelling is 230 (two-hundred and thirty).
The strategy to quickly find these answers is to note which vowels are used in the base numbers, one, two, three, etc, then avoid combinations that include multiples of the same vowel. For example, you can skip past the 100s entirely, because "one-hundred" contains two of the letter "e".
The following is a classic "thinking outside the box" puzzle. Can you connect all nine dots below by drawing exactly four straight lines, without lifting your pencil or tracing back over any line?
Give it a try before you click below for the answer.
If this puzzle looks familiar, it's because it dates back at least as far as Sam Loyd's 1914 Cyclopedia of Puzzles. When I said this was a classic "thinking outside the box" puzzle, that was a clue. You have to think outside the bounds of the box created by the nine dots to come up with a solution.
You work in a factory boxing fruit. In front of you are three boxes labeled "apples," "oranges," and "apples & oranges." One box contains only apples, one contains only oranges, and one contains a mixture of both apples and oranges. Unfortunately, the label machine has gone haywire and has mislabeled all three boxes. Can you look at one piece of fruit from only one of the boxes and correctly label all three? Click below for the solution.
The key to this puzzle is that the type of fruit you pull from the box is not the only piece of information you have to work with. You also have the three labels that you know are incorrect. Pull a piece of fruit from the box labeled "apples & oranges." If it is an apple, then you know that this is the apples-only box. That means that the box (incorrectly) labeled "oranges" must be the box with both apples and oranges, and the box labeled "apples" must contain only oranges.
(It's interesting to note that if you pick from either the box labeled "apples" or the box labeled "oranges," you can't figure out the composition of the box. Only selecting from the box labeled "apples & oranges" leads to a solution.)
