6.2 The Pigeonhole Principle Flashcards
THE PIGEONHOLE PRINCIPLE
and prove it:
Another name?
If k is a positive integer and k + 1 or more objects
are placed into k boxes, then there is at least one box containing two or more of the objects.
Proof: We prove the pigeonhole principle using proof by contraposition. Suppose that none of
the k boxes contains more than one object. Then the total number of objects would be at most k.
This is a contradiction because there are at least k + 1 objects.
Dirichlet drawer principle
Corollary about functions from pigeonhole Principle:
Proof:
A function f from a set with k + 1 or more elements to a set with k elements is not one-to-one.
Suppose that for each element y in the codomain of f we have a box that contains all
elements x of the domain of f such that f(x) = y. Because the domain contains k + 1 or more
elements and the codomain contains only k elements, the pigeonhole principle tells us that one
of these boxes contains two or more elements x of the domain. This means that f cannot be
one-to-one.
Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal
expansion.
Let n be a positive integer. Consider the n + 1 integers 1, 11, 111, … , 11 … 1 (where
the last integer in this list is the integer with n + 1 1s in its decimal expansion). Note that there
are n possible remainders when an integer is divided by n. Because there are n + 1 integers in
this list, by the pigeonhole principle there must be two with the same remainder when divided
by n. The larger of these integers less the smaller one is a multiple of n, which has a decimal
expansion consisting entirely of 0s and 1s.
THE GENERALIZED PIGEONHOLE PRINCIPLE
Proof:
If N objects are placed into k
boxes, then there is at least one box containing at least ⌈N∕k⌉ objects.
We will use a proof by contraposition. Suppose that none of the boxes contains more
than ⌈N∕k⌉ − 1 objects. Then, the total number of objects is at most
k(⌈N/k⌉− 1)< k((N/k + 1)− 1)= N,
where the inequality ⌈N∕k⌉ < (N∕k) + 1 has been used. Thus, the total number of objects is
less than N. This completes the proof by contraposition.
A common type of problem asks for the minimum number of objects such that at least r
of these objects must be in one of k boxes when these objects are distributed among the boxes.
Method to solve it:
When we have N objects, the generalized pigeonhole principle tells us there must be at least
r objects in one of the boxes as long as ⌈N∕k⌉ ≥ r. The smallest integer N with N∕k > r − 1,
namely, N = k(r − 1) + 1, is the smallest integer satisfying the inequality ⌈N∕k⌉ ≥ r. Could a
smaller value of N suffice? The answer is no, because if we had k(r − 1) objects, we could put
r − 1 of them in each of the k boxes and no box would have at least r objects.
Subsequence and more about it:
Suppose that a1, a2, … , aN is a sequence of real
numbers. A subsequence of this sequence is a sequence of the form ai1
, ai2
, … , aim , where 1 ≤
i1 < i2 < ⋯ < im ≤ N. Hence, a subsequence is a sequence obtained from the original sequence
by including some of the terms of the original sequence in their original order, and perhaps not
including other terms.
A sequence is called strictly increasing if each term is larger than the one that precedes it, and it is called strictly decreasing if each term is smaller than the one that
precedes it.
Theorem of Sequence and Subsequences
Prove it
Every sequence of n^2 + 1 distinct real numbers contains a subsequence of length n + 1 that
is either strictly increasing or strictly decreasing.
Ramsey theory
The final example shows how the generalized pigeonhole principle can be applied to an important part of combinatorics called Ramsey theory, after the English mathematician F. P. Ramsey. In general, Ramsey theory deals with the distribution of subsets of elements of sets.
Ramsey number
The Ramsey number R(m, n), where m and n are positive integers greater than or equal to 2,
denotes the minimum number of people at a party such that there are either m mutual friends
or n mutual enemies, assuming that every pair of people at the party are friends or enemies.
Example 13 shows that R(3, 3) ≤ 6. We conclude that R(3, 3) = 6 because in a group of five
people where every two people are friends or enemies, there may not be three mutual friends or
three mutual enemies (see Exercise 28).
Ramsey number properties:
Note that by symmetry it can be shown that
R(m, n) = R(n, m) (see Exercise 32). We also have R(2, n) = n for every positive integer n ≥ 2
(see Exercise 31). The exact values of only nine Ramsey numbers R(m, n) with 3 ≤ m ≤ n are
known, including R(4, 4) = 18. Only bounds are known for many other Ramsey numbers, including R(5, 5), which is known to satisfy 43 ≤ R(5, 5) ≤ 49.
