Here are the answers for the pigeonhole principle problems page.
- 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:
- 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.
- 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.
- 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
, the distance between at least one set of two points must be no greater than that distance.
- 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.
- We can group the integers in pairs that sum to 104, as follows:
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.
- Group 1
- Group 2
- 4, 100
- Group 3
- 7, 97
- Group 17
- 49, 55
- Group 18
- 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.
- 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 |a − b|X must differ from an integer by no more than the size of the partion, 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.
- 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:
Therefore, in any group of six people there are either three mutual acquaintances or three mutual strangers.
- 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.
- Consider the n numbers between n + 1 and 2n. It is possible to select all of these and not have any member of the set divide another member of the set. However, we need to find an additional number. Consider the upper half of the remaining numbers (from n / 2 + 1, rounded down, to n). If we select one of these numbers, we will not be able to select its double, which will appear between n + 1 and 2n. Therefore, there are still only n possible numbers to select. Now consider the upper half of the remaining numbers. If any of these are selected, we will not be able to select its double. We can repeat the process until we reach the number 1. Therefore, given a set of n + 1 integers between 1 and 2n, show that at least one member of the set must divide another member of the set.