1 The pigeonhole principle
If n objects are placed in k boxes, k < n, then at least one box contains more
than one object .
This is so obvious, one might think that nothing non-trivial can be derived from
this "principle".
And yet, this principle is very useful.
1.1 Two equal degrees
The fol lowing consequence is quite easy.
Theorem 1. In any graph, there are two vertices of equal degree.
Proof. For any graph on n vertices , the degrees are between 0 and n-1.
Therefore, the only way all
degrees could be different is that there is exactly one vertex of each possible
degree. In particular,
there is a vertex v of degree 0 and a vertex w of degree n - 1. However, if
there is an edge (v, w),
then v cannot have degree 0, and if there is no edge (v, w) then w cannot have
degree n - 1. This
is a contradiction.
1.2 Subsets without divisors
Let [2n] ={1, 2, ... , 2n}. Suppose you want to pick a subset S
[2n] so that no number in S divides
another. How many numbers can you pick? Obviously, you can take S = { n + 1, n +
2, ... , 2n}
and no number divides another . Can you pick more then n numbers? The answer is
negative .
Theorem 2. For any subset S [2n] of size
lSl > n, there are two numbers a, b ∈
S such that alb.
Proof. For each odd number a ∈ [2n], let 
. The
number of these
classes is n and every element b ∈ [2n] belongs to exactly one of them, for a
obtained by dividing b
by the highest possible power of 2. Consider S [2n] of size
lSl > n. By the
pigeonhole principle,
there is a class 
that contains at least two elements of S.
1.3 Rational approximation
Theorem 3. For any x ∈ R and n > 0, there is a rational number p/q, 1
≤ q ≤ n,
such that
Note that it is easy to get an approximation whose error is at most
, by fixing the denominator
to be q = n. The improved approximation uses the pigeonhole principle and is due
to Dirichlet
(1879).
Proof. Let {x} denote the fractional part of x. Consider
{ax} for a = 1, 2, ... , n + 1 and place
these n+1 numbers into n buckets [0, 1/n), [1/n, 2/n),..., [(n-1)/n, 1).
There must be a bucket
containing at least two numbers {ax} ≤ {a'x}. We set q = a' - a and we get {qx}=
{a'x - ax} <
1/n. This means that qx = p + ε where p is an integer and ε = {qx} < 1/n. Hence,
1.4 Monotone subsequences
Finally, we give an application which is less immediate. Given an arbitrary
sequence of distinct
real numbers , what is the largest monotone subsequence that we can always find?
It is easy to
construct sequences of mn numbers such that any increasing subsequence has
length at most m
and any decreasing subsequence has length at most n. We show that this is an
extremal example.
Theorem 4. For any sequence of mn+1 distinct real numbers
,
there is an increasing
subsequence of length m + 1 or a decreasing subsequence of length n + 1.
Proof. Let 
denote the maximum length of an increasing subsequence starting
with
. If
for some i, we are done. So assume 
for all i, i.e. we have
mn + 1 numbers in m
buckets. By the pigeonhole principle, there must be a value
such that = s for
at least n + 1 indices, 
. Now we claim that
. Indeed, if there
were a pair such that 
, we could extend the increasing subsequence
starting at 
by
adding 
, to get an increasing subsequence of length s + 1. However, this
contradicts 
.
2 Double counting
Another elementary trick which often brings surprising results is double
counting. As the name
suggests, the trick involves counting a certain quantity in two different ways
and comparing the
results .
2.1 Sum of degrees in a graph
The following observation is due to Leonard Euler (1736).
Lemma 1. For any graph G, the sum of degrees over all vertices is even.
Proof. For a vertex v and edge e, let i(v, e) = 1 if v ∈ e and 0 otherwise. We
count all the incidences
between vertices and edges in two ways:
•
because d(v) is exactly the number of edges incident with
v.
•
because every edge is incident with exactly two vertices.
Thus we have proved that the sum of all degrees is exactly twice the number of
edges.
2.2 Average number of divisors
Let t(n) denote the number of divisors of n. E.g., for a prime n, t(n) = 2,
while for a power of 2,
t(2k) = k + 1. We would like to know what is the average number of divisors,
This seems to be a complicated question, however, double
counting gives a simple answer . Let
d(i, j) = 1 if ilj and 0 otherwise. I.e.,
. We count the total number of dividing
pairs
, in two different ways.
where
is the n-th
harmonic number.
In the second case, we have been somewhat sloppy and
neglected some roundoff errors, but these
add up to at most n overall. We can conclude that
, within an
error of 1.
