Pigeonhole Principle - Solutions
1. In the following fraction every letter represents a different digit.
Knowing that the value of the fraction is a real number, find its value. Justify your answer!
Solution: There are 10 different letters above and 10 different digits, so all the digits occur, but 0 can’t occur at the denominator (bottom) so it must at the numerator (top). So the answer is 0.
Q1 / a / b / c / dQ2 / a / b / c / d
Q3 / a / b / c / d
3. A row of houses are randomly assigned distinct numbers between 1 and 50(inclusive). How many houses must there be to insure that there are 5 houses numbered consecutively?
Split the numbers into 10 pigeonholes: 1-5, 5-10, 11-15, 16-20… There must be at least =41 “pigeons”=houses.
4. Given any 6 integers from 1 to 10, show that some two of them have an odd sum.
Possible pigeonholes: There are 5 pigeonholes and 6 pigeons, hence there exists a pigeonhole with 2 pigeons.
5. Prove that having 100 whole numbers, one can choose 15 of them so that the difference of any two is divisible by 7.
7 pigeonholes: all numbers of the form 7k, for example 7, 14, 21, 28, …
all numbers of the form 7k+1, for example 1, 8, 15, 22, 29, …
all numbers of the form 7k+2, for example 2, 9, 16, 23, 30, …
…………………………………………………………………………………………..
all numbers of the form 7k+6, for example 6, 13, 20, 27, 34…
so there exists a pigeonhole with 15 pigeons.
6. Show that any subset of 55 distinct positive numbers less than 101 must contain two numbers which differ by exactly 9.
If the 55 numbers do not include 100, we can use the pigeonholes:
There are such pigeonholes, and 55 pigeons. Hence there is a pigeonhole with 2 pigeons.
7. One of the numbers -1, 0 or 1 is written in each of the squares of the table:
Prove that among the sums by rows, columns and diagonals there are two equal.
The pigeons are the 8 sums on the 3 rows, 3 columns and 2 diagonals. The pigeonholes are all the sums that we can get by adding 3 random numbers with values -1, 0 or 1 each: -3, -2, -1, 0, 1, 2, 3. These are 7 pigeonholes.
8. Show that if you randomly draw 13 points in the interior of a square of 4 cm sides,
then there must exist 4 points among them which are closer than 3 cm from each other.
Split the square into 4 squares of size so that the longest possible distance between two points inside such a square is
9. a) A rectangular board is divided into squares each ofwhich is coloured red or green. Prove that the board contains a rectangle whose four corner squares are all the same colour.
b) A rectangular board is divided into squares each ofwhich is coloured red or green or blue. Prove that the board contains a rectangle whose four corner squares are all the same colour.
a) The pigeons are the 7 columns of the board. If two columns are coloured identically, then they form a rectangle whose four corners are all the same colour. Assume that each column is coloured differently. Consider all the ways to arrange the colours in a column of length 3: RRR, RRG, RGR, GRR, GGG, GGR, GRG, RGG. Then we can form the pigeonholes like this: RRR, RRG}, { RGR }, { GRR }, {GGG, GGR}, {GRG}, {RGG}. We get 6 pigeonholes.
b) The pigeons are the 19 columns of the board. If two columns are coloured identically, then they form a rectangle whose four corners are all the same colour. Assume that each column is coloured differently. Consider all the ways to arrange the colours in a column of length 4, and form the pigeonholes(this is just one of the many possible examples):
{all strings starting with RR}. There are such strings. Similarly when R is replaced by B and by G.
{all strings of the form R_R_, except those already included above}. Similarly for B and G.
{all strings of the form R_ _ R, except those already included above}. Similarly for B and G.
{all strings of the form _ RR_ , except those already included above}. Similarly for B and G.
{all strings of the form _ R_ R, except those already included above}. Similarly for B and G.
{all strings of the form _ _R R, except those already included above}. Similarly for B and G.
Note that a column of length 4 coloured in 3 colours will always have two squares of the same colour. So there are no other possible strings. Hence there are pigeonhole.
10. There are 17 points on the plane, no 3 of which are collinear. The segments that connect the points are coloured in blue, red or green. Prove that among all the triangles thus obtained, there is one all of whose vertices have the same colour.
Consider one of the 17 points, call it A. There are 16 segments connecting A to the other points. There are 3 colours, so by the PP, at least 6 of the segments have the same colour, let’s say blue. Let the two points thus connected to A be called B,C,D,E, F,G. Now if one of the segments connecting the 6 points is also blue, then we have a blue triangle with a vertex at A. Otherwise all the segments connecting B,C,D,E, F,G are red or green. There are 5 segments connecting B with C, D, E, F, G and 2 colours, so there must be 3 segments of the same colour among these. Let’s assume that these segments are BC, BD, BE and they’re all red. If one of the segments CD, CE, DE is red, then we have a red triangle with B as a vertex. Otherwise the triangle CDE is green.
The assumptions we made can be made without loss of generality, which means that changing the names of the colours or the point does not alter the essence of the argument.
11. Show that every integer has a multiple consisting only of 0's and 1's.
n pigeonholes: all numbers of the form nk, for example n, 2n, 3n, …
all numbers of the form nk+1, for example 1, n+1, 2n+1, 3n+1, …
all numbers of the form nk+2, for example 2, n+2, 2n+2, 3n+2, …
…………………………………………………………………………………………..
all numbers of the form nk+n-1, for example n-1, 2n-1…
Infinitely many pigeons: 1, 11, 111, 1111, 11111, 1111111,….
(The difference between two pigeons can be written using only 0’s and 1’s.)
12. Show that at a party with at least two people, there are two people whoknow the same number of other people there. (Assume that if knows , then knows ).
If somebody doesn’t know anybody, we exclude that person and solve the problem for the remaining people. If two such persons are excluded, then we found two persons who know 0 people. Otherwise let be the number of people who know at least somebody. These are the pigeons. Each person could know or other people: these are the pigeonholes.
13.The numbers are randomly written in a array. Prove that there existsa subarray whose numbers have the sum greater than 145.
Divide the table in 16 squares of size
The sum of all the numbers in the table is So there must exist a square among these 16 whose sum is at least 130. Moreover, if there is a square with sum <130, then there must exist a square with sum >130 (to compensate), and then a array around it would have sum >130+1+2+3+4+5=145. On the other hand if all squares had sum 130, we could choose one which is not neighbour to 1 and then a array containing it would have sum at least 130+2+3+4+5+6>145.