# Answers to Pigeonhole Principle Problems

Math Lair Home > Puzzles & Problems > Answers to Pigeonhole Principle Problems

Here are the answers for the pigeonhole principle problems page.

1. We can group the five selected numbers into three categories based on the remainder they give when divided by 3. All numbers will have a remainder of either 0, 1, or 2 when divided by 3. Two possibilities exist:
1. Three of the numbers have the same remainder when divided by 3. In this case, the sum of these three numbers will be a multiple of 3.
2. No three numbers have the same remainder when divided by 3. In this case, there will need to be at least one number with a remainder of 0, one number with a remainder of 1, and one number with a remainder of 2. The sum of these three numbers will be divisible by 3.
2. Divide the unit square into four smaller squares as shown. Because there are five points and only four subsquares, at least two points will fall in or on the border of the same square. Because the length of the diagonal of the smaller square is
 1 2
, the distance between at least one set of two points must be no greater than that distance.
3. Consider each of the columns that contain three squares. For three squares, there are eight different permutations of black and white. If any of the eight permutations are repeated, a square is formed. So, seven different permutations must be used. This means that one of them must be a column containing either all black or all white. These columns will form a square with three other permutations (the three that have two squares the same colour), at least one of which must be present, so a square must be formed.
4. We can group the integers in pairs that sum to 104, as follows:
Group 1
1
Group 2
4, 100
Group 3
7, 97
...
Group 17
49, 55
Group 18
52
When selecting 20 distinct integers from the given arithmetic progression, at least two must be in the same group. However, if two integers from the same group are selected, they must sum to 104, and the assertion is proved.
5. Say that there are n guests at the party. Each of them must know a number of guests between 0 and n − 1. There are two possibilities:
If each guest knows at least one other guest, then there are only n − 1 possibilities and n guests, so two guests must know the same number of other guests.
• If one guest knows no other guests, then the maximum number of guests any other guest can know is n − 2. There are still n − 1 possibilities and n guests, so two guests must know the same number of other guests.
6. Consider the decimal portions of X, 2X, ..., (n − 1)X. Each must, of course, fall somewhere between .000... and .999... Divide the range between 0 and 1 into n equal partitions, the first being between 0 and 1/n, the second being between 1/n and 2/n, ..., the nth being between (n − 1)/n and 1. If the decimal portions of aX and bX fall in the same partition, then the decimal part of |ab|X must differ from an integer by no more than the size of the partition, 1/n. Otherwise, all of the partitions must contain one of the numbers, including the partition ranging between 0 and 1/n, which completes the proof.
7. You can also look at this question geometrically. Geometrically, the question boils down to drawing all sides and diagonals of a hexagon in two colours (say, red and green) such that there is no triangle with three sides all the same colour. Looking at the problem this way:
• Consider any vertex on the hexagon. It will have five lines connected to it. Either at least three of them will be red, or at least three of them will be green. Without loss of generality, assume that three of them are red.
• Consider the three vertices connected to the original vertex by red lines. If any of those three vertices are connected to each other by a red line, it will form a red triangle with the original red vertex. The only other possibility is that they are connected to each other with green lines, but then that will form a green triangle. Either way a triangle must be formed.
Therefore, in any group of six people there are either three mutual acquaintances or three mutual strangers.
8. We can write each number between 1 and 2n as 2x · y, where y is an odd number. For example, 24 = 2³ · 3. Now, y must be an odd number between 1 and 2n − 1. There are n such numbers. If we select n + 1 numbers between 1 and 2n, then there must be at least two of them that can be written as 2a · y and 2b · y, where y is the same in both cases. Depending on which of a and b is greater, one of these numbers must be a factor of the other. Therefore, given a set of n + 1 integers between 1 and 2n, at least one member of the set must divide another member of the set.