3.3 THE PIGEONHOLE PRINCIPLE 89This set of pigeonholes does the trick. If we choose any six numbers from
{1,2, ... , 1O},then two of them must be contained in one of the above five sets. Some of the sets (in
this case, just two) contain just one element, so the two numbers that "cohabit" a set
cannot lie in these sets. Therefore the two cohabitors must live in either { 1,2,4, 8} or
{3, 6} or {5, 10}, and then we are done, for then one of the two cohabitors is a multiple
of the other.
It is easy now to solve the problem in general.
Formal Solution: Each element of {I, 2, ... ,2n} can be uniquely written in the
form 2 r q, where q is an odd integer and r is a non-negative integer. Each different
odd number q defines a pigeonhole, namely all the elements of { 1,2, ... ,2n} that have
the form 2 r q for some positive integer r. (For example, if n = 100, the value q = 11
would define the pigeonhole {II, 22, 44 , 88, 176}.) Since there are exactly n odd num
bers between 1 and 2n, we have defined n sets, and these sets are disjoint (they need
to be disjoint; otherwise they cannot be "pigeonholes".) So we are done, for by the
pigeonhole principle, two of the n + 1 numbers will lie in one of our n sets, which will
force one of the two numbers to be a multiple of the other. _
The next problem, from the 1994 Putnam exam, involves some linear algebra,
which makes it already pretty difficult. But the fun parts are the two crux moves:
defining a function, and using the pigeonhole principle with the roots of a polynomial.
Both ideas have many applications.
Example 3.3.8 Let A and B be 2 x 2 matrices with integer entries such that A, A +
B,A + 2B,A + 3B, and A + 4B are all invertible matrices whose inverses have integer
entries. Show that A + 5B is invertible and that its inverse has integer entries.
Solution: If X is an invertible matrix with integer entries and its inverse also has
integer entries, then detX = ± 1. This follows from the fact that detX and det (X -I)
are both integers and that det(X -) = 1/ detX. And conversely, if the determinant of
a matrix with integer entries is ± 1, the inverse also will have integer entries (why?).
Now define the functionf(t) :=det(A+tB). Since A andB are 2 x 2 matrices with
integer entries, f(t) is a quadratic polynomial in t with integer coefficients (verify!).
Since A,A +B,A + 2B,A + 3B, and A +4B are all invertible matrices whose inverses
have integer entries, we know that the five numbers
f(O), f( 1), f(2) , /(3),/( 4)take on only the values 1 or -1. By the pigeonhole principle, at least three of these
numbers must have the same value; without loss of generality, assume that it is 1. Then
the quadratic polynomial f(t) is equal to 1 when three different numbers are plugged
in for t. This means that f(t) must be the constant polynomial ; i.e., f(t) == 1. There
fore det(A + 5B) = f(5) = 1, so A + 5B is invertible and its inverse has integer entries.