Transcript The Pigeonhole Principle

The Pigeonhole Principle
Rosen 4.2
Pigeonhole Principle
If k+1 or more objects are placed into k boxes, then there is
at least one box containing two or more objects.
Generalized Pigeonhole Principle
• If N objects are placed into k boxes, then there is
at least one box containing at least N/k objects
• Examples
– Among any 100 people there must be at least 100/12
= 9 who were born in the same month.
– What is the minimum number of students needed in a
class to be sure that at least 6 to get the same grade? (5
choices for grades:A,B,C,D,F)
• Smallest integer N such that N/5 = 6, 5*5+1 = 26
Example
• What’s the minimum number of students,
each of whom comes from one of the 50
states must be enrolled in a university to
guarantee that there are at least 100 who
come from the same state?
50*99 + 1 = 4951
4951/50 = 100
There are 38 different time periods during which classes at a
university can be scheduled. If there are 677 different classes,
how many different rooms will be needed?
677/38 = 18
A computer network consists of six computers. Each computer is
directly connected to zero or more of the other computers. Show
that there are at least two computers that are directly connected
to the same number of other computers.
Solution:
Each computer can be directly connected to 0,1,2,3,4,5.
But there are really only five choices, not six, since if one computer
is connected to zero other computers, then no computer can be
connected to five others. Six computers, 5 choices. Pigeonhole
principle says that at least two must have the same number of direct
connections.
Let (xi, yi, zi), i = 1,2,3,..,9 be a set of nine distinct points
with integer coordinates in xyz space. Show that the
midpoint of at least one pair of these points has integer
coordinates.
For points (xj, yj, zj) and (xk, yk, zk) we compute the midpoint by ((xi+xj)/2,
(yi+yj)/2, (zi+zj)/2 ).
Example: (1,1,2), (1,2,2), (3,2,7), (10,5,8), (3,1,4), (3,7,2), (2,1,1), (1,2,1), (0,0,0)
The midpoint between (1,1,2) and (3,1,4) = (2,1,3)
Remember from number theory that when we add an odd number to an
odd number, or an even number to an even number, we get an even
number. So the question becomes, does there exist two sets of
coordinates that have the same parity (i.e., their odd/even order is
the same)?
From the product rule there are 2*2*2 = 8 possible parities. There are
nine points, so by the pigeonhole principle two of them must be the
same. Therefore at least one midpoint must have integer
coordinates.
During a month with 30 days a baseball team plays at least 1
game a day, but no more than 45 games. Show that there must
be a period of some number of consecutive days during which
the team must play exactly 14 games.
Proof: Let aj be the number of games played on or
before the jth day of the month. Then a1, a2, …, a30
must be an increasing sequence of distinct positive
integers, with 1aj 45.
Day of Month
1
2
3
…
30
Games Played
a1
a2
a3
…
a30
Moreover, a1+14, a2+14, . . ., a30+14 is also an increasing
sequence of distinct positive integers with 15  aj + 14  59 .
Together the two sequences, each containing 30 integers,
contain 60 positive integers, all of which are less than or equal
to 59. By the pigeonhole principle, at least two of these
integers are equal. Since the integers aj, j = 1 to 30, are all
distinct and the integers aj+14, j = 1 to 30 are all distinct, there
must be indices i and j with ai = aj+14.
This means that exactly 14 games were played from day j+1 to
day i.
Some Definitions
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
• A sequence is called strictly increasing if each term is
larger than the term that precedes it.
• A sequence is called strictly decreasing if each term is
smaller than the one that precedes it.
– Example: {1, 5, 6, 2, 3, 9} is a sequence.
– {5,6,9} is a subsequence that is strictly increasing
Theorem: Every sequence of n2+1 distinct real
numbers contains a subsequence of (at least) length
n+1 that is strictly increasing or strictly decreasing.
Example: 8, 11, 9, 1, 4, 6, 12, 10, 5, 7
10 = 32+1 terms so must be a subsequence of length 4 that is
either strictly increasing or strictly decreasing.
1,4,6,12
1,4,6,7
11,9,6,5
……
Theorem: Every sequence of n2+1 distinct real
numbers contains a subsequence of at least length
n+1 that is strictly increasing or strictly decreasing.
Let a1, a2, …, a n2+1 be a sequence of n2+1 distinct numbers.
Associate an ordered pair (ik,dk) with each term of the
sequence where ik is the length of the longest increasing
subsequence starting at ak and dk is length of the longest
decreasing subsequence starting at ak.
Example: 8, 11, 9, 1, 4, 6, 12, 10, 5, 7
a2 = 11 , (2,4)
a4 = 1 , (4,1)
Proof by contradiction: Now suppose that there are no
increasing or decreasing subsequences of length n+1 or
greater. Then ik and dk are both positive integers  n, for
k=1 to n2+1.
By the product rule, there are n2 possible ordered pairs for (ik,dk).
Why? Because each has the range from 1 to n.
By the pigeonhole principle, since we have n2+1 ordered pairs (one
for each element in the sequence) two of them must be identical.
Formally  terms as and at in the sequence, with s<t such that is = it
and ds = dt.
We will show that this is impossible.
Because the terms in the sequence are distinct, either as < at or as > at.
If as < at, an increasing subsequence of length it+1(or greater) can be
constructed starting at as, by taking as followed by an increasing
subsequence of length it, beginning at at. But we have said that is = it.
Thus this is a contradiction.
Similarly, if as > at, it can be shown that ds must be greater than dt,
which is also a contradiction.