[This article is included in the 45th Carnival of Math]
The games we will talk about are two-person games with perfect information, no chance moves, and a win-or-lose outcome. In these games, players usually alternate moves until they reach a terminal position. After that, one player is declared the winner and the other the loser. How Two Pigeons Helped Scientists Confirm the Big Bang Theory For decades, astronomers had debated how the universe began. Then, in 1964, they had their “Eureka!” moment. The puzzles topics include the mathematical subjects including geometry, probability, logic, and game theory. Math Puzzles Volume 1 features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.6/5 stars on 39 reviews.
Mathematical logic can produce some great trivia. Did you know that at every instant, there is a spot in the world where no wind is blowing? It is true, and the proof comes as an application of a fixed point theorem which I discussed a year ago.
This article continues the Thanksgiving tradition of discussing math trivia. These 16 fun tidbits cover topics as disconnected as birthdays, haircuts, WordPress blogs, and cocktail parties. Amazingly, all the results come out of a basic insight from stuffing pigeons into pigeonholes.
The pigeonhole principle
The pigeonhole principle is a powerful tool used in combinatorial math. But the idea is simple and can be explained by the following peculiar problem.
Imagine that 3 pigeons need to be placed into 2 pigeonholes. Can it be done? The answer is yes, but there is one catch. The catch is that no matter how the pigeons are placed, one of the pigeonholes must contain more than one pigeon.
The logic can be generalized for larger numbers. The pigeonhole principle states that if more than n pigeons are placed into n pigeonholes, some pigeonhole must contain more than one pigeon. While the principle is evident, its implications are astounding. The reason is that the principle proves the existence (or impossibility) of a particular phenomenon.
The pigeonhole principle (more generalized)
Game Theory Pigeons
There is another version of the pigeonhole principle that comes in handy. This version is “the maximum value is at least the average value, for any non-empty finite bag of real numbers” (thanks Professor Dijkstra)
Do not let the math jargon intimidate you. The idea is intuitive. For typical data sets, the average is the “middle” value, so clearly the maximum should be at least as big. While this version sounds different, it is mathematically the same as the one stated with pigeons and pigeonholes. Let’s see how the two are connected.
Consider again the problem of stuffing pigeons into pigeonholes and consider the average. If we have more than n pigeons and n pigeonholes, then the average value of (pigeons / pigeonholes) is greater than one. This means the maximum value should also be larger than one. In other words, there has to be some value of more than one pigeons per pigeonhole. Indeed, the two versions are about the same idea.
Now that we have a good grasp on the pigeonhole principle, let’s see how it can be used. Here are 16 of my favorite applications, categorized by difficultly:
.
.
'All will be well if you use your mind for your decisions, and mind only your decisions.' Since 2007, I have devoted my life to sharing the joy of game theory and mathematics. MindYourDecisions now has over 1,000 free articles with no ads thanks to community support! Help out and get early access to posts with a pledge on Patreon.
..
Easy (1-8)
1. For every 27 word sequence in the US constitution, at least two words will start will the same letter.
There are 27 words or “pigeons” that can start with one of the 26 different English letters or “pigeonholes.” By the pigeonhole principle, two of the words must start with the same letter.
2. In New York City, there are two non-bald people who have the same number of hairs on their head.
The human head can contain up to several hundred thousand hairs, with a maximum of about 500,000. In comparison there are millions of people in New York City. Consequently, at least two of them must share the same number of hairs.
Pigeons Game Theory Definition
3. Two or more people reading this blog will have the same birthday.
There are 366 possible birthdays (including February 29 in a leap year) and this blog has many more than 367 readers. Therefore two of you must share the same birthday.
4. On Thanksgiving, two or more of the consumed turkeys will have the same weight when rounded to the nearest millionth of a pound.
Turkeys weigh roughly 15 pounds, with the largest recorded at 37 pounds. If we could weigh all turkeys to the millionth of a pound, then we have 37 million possible values for weight. In comparison, there are an estimated 46 million turkeys consumed on Thanksgiving. By the pigeonhole principle, two of those turkeys must have the same weight to the nearest millionth.
5. At least two WordPress.com blogs have the same number of yearly comments.
At the time of this writing, there are almost 4.75 million wordpress.com blogs. I would estimate one million as a safe maximum for yearly comments. Thus, the pigeonhole principle implies at least two wordpress.com blogs must have the same number of yearly comments.
6. In a packed Carnegie Hall performance, there will be two people who have the same first and last initials.
Each initial can take be one of the 26 English letters, meaning there are 26 x 26 = 676 possible values for the first and last initials. The main hall at Carnegie seats roughly 2,800. Consequently, two of the patrons on a sold out show must share the same first and last initials.
7. If you pick five cards from a standard deck of 52 cards, then at least two will be of the same suit.
Each of the five cards can belong to one of four suits. By the pigeonhole principle, two or more must belong to the same suit.
8. If you have 10 black socks and 10 white socks, and you are picking socks randomly, you will only need to pick three to find a matching pair.
The three socks can be one of two colors. By the pigeonhole principle, at least two must be of the same color.
Another way of seeing this is by thinking sock by sock. If the second sock matches the first, then we are done. Otherwise, pick the third sock. Now the first two socks already cover both color cases. The third sock must be one of those and form a matching pair.
Medium (9-14)
9. On New Years at New York’s Time Square, over 820 people will have the same birthday.
It will now be useful to use the second version “the maximum must at least be the average.”
There are roughly 300,000 attendees on New Years split over a possible 366 birthdays. The average is 300,000 / 366 = 819.7 people per birthday. The maximum must at least be the average, so there must be a birthday that at least 820 people share.
10. Imagine a certain college has 6,000 American students, at least one from each of the 50 states. Then there must be a group of 120 students coming from same state.
Again, we invoke the second version that “the maximum must at least be the average.”
The average is 6,000 / 50 = 120 students per state. The maximum must at least be the average, so there must be a state where 120 students share in common.
11. If you pick five numbers from the integers 1 to 8, then two of them must add up to nine.
Every number can be paired with another to sum to nine. In all, there are four such pairs: the numbers 1 and 8, 2 and 7, 3 and 6, and lastly 4 and 5.
Each of the five numbers belongs to one of those four pairs. By the pigeonhole principle, two of the numbers must be from the same pair–which by construction sums to 9.
12. If you draw five points on the surface of an orange in permanent marker, then there is a way to cut the orange in half so that four of the points will lie on the same hemisphere (suppose a point exactly on the cut belongs to both hemispheres).
Two points determine a great circle on a sphere, so for any two points, cut the orange into half. The remaining three points can be on either one of the two resulting hemispheres. By the pigeonhole principle, at least two of them belong to the same hemisphere, bringing the total to 4 points.
13. Gary is training for a triathlon. Over a 30 day period, he pledges to train at least once per day, and 45 times in all. Then there will be a period of consecutive days where he trains exactly 14 times.
Problem and proof based on a handout from Professor Gary MacGillivray (pdf)
Let Si indicate the cumulative number of workouts by day i. Since each day contains one workout, and the total number of workouts is 45, we know that:
1 ≤ S1 < S2 < … < S30 =45
We want to prove there is some place with i < j such that Si + 14 = Sj. Start by adding 14 to every term in the inequality:
Game Pigeon Online
15 ≤ S1 + 14 < S2 + 14 < … < S30 + 14 =59
The two inequalities imply there are 60 numbers (S1, S2, …, S30 and S1 + 14,S2 + 14, …, S30 + 14) that can assume any of the 59 integer values from 1 to 59. By the pigeonhole principle, two of the numbers must be the same.
Which two? Notice that none of the numbers S1, S2, …, S30 could possibly be equal to one another (Rick takes at least one workout every day, so the sequence is strictly increasing). The same logic is true for the group S1 + 14, S2 + 14, …, S30 + 14.
Therefore, we must have one value from the group S1, S2, …, S30 equal to one of the values from the group S1 + 14, S2 + 14, …, S30 + 14, which is exactly what we wanted to prove.
14. In any cocktail party with two or more people, there must be at least two people who have the same number of friends. (Assume that “friend” is symmetric-if x is a friend of y, then y is a friend of x.)
Imagine a party has n people. Then each person can be friends with anywhere from 0 to n-1 other people.
Game Pigeon Download
Case 1: everyone has at least one friend
If everyone has at least one friend, then each person has between 1 to n-1 friends. Each of the n partygoers can be categorized as one of these n-1 values, and hence two of the partygoers must have the same value-that is, the same number of friends-by the pigeonhole principle.
Case 2: someone has no friends
If someone lacks any friends, then that person is a stranger to all other guests. Because friend is symmetric, the highest value anyone else could have is n – 2, that is, they would be friends with everyone except the singleton. Therefore everyone has between 0 to n – 2 friends.
This means of the n partygoers can be categorized as one of the n-1 values, and hence two of the partygoers must have the same value, or number of friends.
Hard (15-16)
15. Imagine you are trying to cover a chessboard with pieces of domino each that covers exactly two squares. If you remove two diagonally opposite corners, it will be impossible to cover the chessboard.
This is a puzzle I posted about. You can read the solution here
16. In a group of six people, there will always be three people that are mutual friends or mutual strangers. (Assume that “friend” is symmetric-if x is a friend of y, then y is a friend of x.)
The problem can be thought of geometrically. Imagine the six people as points and let an edge between points indicate friendship. No matter how the graph is drawn, we want to show there is a set of three points that are all connected or a set of three points that has no connecting edges.
Consider any single point. There are five other points it could possibly connect to. By the pigeonhole principle, the point is either connected to at least three other points or not connected to at least three other points.
Case 1: the point is connected to (at least) three other points
If any of these points are connected to each other, then we have found a triangle of three mutual friends. (These two points are connected, plus they are both connected to the original point).
Otherwise, that means none of these three points are connected and hence they are mutual strangers. This would be a set of three points without any edges.
Case 2: the point is not connected to (at least) three other points
If any of these points are not connected to each other, then we have found a triangle of three mutual strangers. (These two points are not connected, plus they are both not connected to the original point).
Otherwise, that means all of these three points are connected and hence they are mutual friends. This would be a set of three points with all connecting edges.
Bonus: Lossless data compression cannot guarantee compression for all data input files.
Amazingly, this is also about the pigeonhole principle! See the proof.