Transcript Pigeonhole Principle

Section 4.2
The Pigeonhole Principle
1
The Pigeonhole Principle
• … states that, if there are more pigeons than
there are pigeonholes, there must be at least
one pigeonhole with 2 pigeons in it
• More formally: if k+1 objects are placed in
k boxes, there is at least one box containing
2 or more objects
2
Applying the pigeonhole
principle to counting problems
• Among any group of 367 people, at least 2
must have the same birthday
• In any group of 27 English words, at least 2
must start with the same letter
3
Example 1
• A drawer contains 12 black socks and 12
blue socks. Your professor takes socks out
of the drawer at random, in the dark.
– How many must she remove to guarantee at
least one matched pair?
– How many to guarantee at least 2 black socks?
– The answers are 3 and 14, respectively
4
Example 2
• During a month with 30 days, a baseball
team plays at least 1 game a day, but no
more than 45 games in the month. Show
that there must be a period of some number
of consecutive days during which the team
must play exactly 14 games
5
Example 2
• Let aj = number of games played on or
before day j (of the 30-day month)
• Then a1, a2, … a30 is an increasing sequence
of distinct positive integers with 1<=aj<=45
(sequence 1)
• And a1+14, a2+14, a3+14 and so forth is also
an increasing sequence of positive integers,
with 15<=aj+14<=59 (sequence 2)
6
Example 2
• The 60 integers from a1, a2, … , a30 and from
a1+14, a2+14, … , a30+14 are all less than or equal
to 59 (since a30 <= 45)
• Hence, by the pigeonhole principle, at least 2 of
these integers are equal (59 pigeonholes, 60
“pigeons”
• Since the integers in the 2 sequences are all
distinct, there must be indices i and j with ai=aj+14
- so there are exactly 14 games played from day
j+1 to day i
7
Example 3
• Show that among n+1 positive integers less
than or equal to 2n, there must be an integer
that divides one of the other integers
• The n+1 integers are: a1, a2, … an, an+1
• Each of these integers can be written as a
power of 2 times an odd integer (odd*2 is
even; odd*20 is odd)
8
Example 3
• So, let aj = 2kjqj for:
– j=1, 2, …, n+1
– kj is a non-negative integer
– qj is an odd integer
• The integers q1, q2, … qn+1 are all odd
positive integers <= 2n (this must be true if
aj is a product of qj and some power of 2)
9
Example 3
• Since there are only n odd positive integers
less than 2n, the pigeonhole principle holds
that 2 of the q’s must be equal - in other
words, there are two integers i and j such
that qi = qj
• If we represent this common value as q,
then ai = 2kiq and aj = 2kjq
• It follows then that if ki<kj, ai divides aj, and
10
if ki>kj, aj divides ai
Pigeonholes & subsequences
• Can use the pigeonhole principle to show the
existence of a subsequence of a certain length within a
sequence of distinct integers
• For a sequence of the form: a1, a2, … , aN a
subsequence is a sequence of the form: ai1,ai2, … ,aim
where 1<=i1< i2< … < im<=N
• So if we have this sequence: 2, 4, 6, 8; some
subsequences are: 2,4; 4,6,8; 2,8 (we include terms in
original order, but can skip terms)
11
Subsequences
• A subsequence is strictly increasing if each
term is larger than the preceding term, and
strictly decreasing if each is smaller than its
predecessor
• There is a theorem which states: every
sequence of n2+1 distinct real numbers
contains a subsequence of length n+1 that is
either strictly increasing or strictly
decreasing
12
Example 4
• For example, the sequence:
11, 2, 23, 14, 15, 81, 90, 4, 3, 5
has length 10, so n=3 (10 = 32+1)
• According to the theorem, there is a subsequence
of length 4 that is either strictly increasing or
decreasing
• There are several examples of both, including:
11, 23, 81, 90 (increasing)
23, 15, 4, 3 (decreasing)
13
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 of application of the principle:
– Among 100 people there are at least 100/12, or 9
people who share a birth month
– Minimum number of students needed to guarantee that
at least 3 receive the same grade (A,B,C,D or F) would
be the smallest number N such that N/5 = 3; that
would be 11
14
Example 5
• What is the least number of area codes
needed to guarantee that 25 million phones
in a state have distinct 10-digit numbers
under the NXX-NXX-XXXX scheme?
– Where N = 2..9
– And X = 0..9
15
Example 5
• There are 8*10*10*10*10*10*10=8,000,000
different 7-digit numbers of the form NXXXXXX
• So, for 25,000,000 telephones, at least
25,000,000/8,000,000 = 4 will have identical
7-digit numbers - therefore, 4 area codes are
needed
16
Generalized pigeonhole principle
& Ramsey Theory - example 6
• Ramsey theory: in a group of 6 people, in
which each pair consists of 2 friends or 2
enemies, there must be 3 mutual friends or 3
mutual enemies in the group (assuming
anyone who is not a friend is an enemy)
• We can use the generalized pigeonhole
principle to prove this theory
17
Example 6
• Let A be one of the 6 - of the other 5, 3 or more
are either friends or enemies of A (because by the
generalized pigeonhole principle, when 5 objects
are divided into 2 sets, one set has at least 5/2 =
3 elements)
• Suppose that B, C and D are friends of A
– If any 2 of these 3 are friends, then that pair + A make 3
mutual friends
– If they are not friends, then they are mutual enemies so theory is proven
18
Section 4.2
The Pigeonhole Principle
- ends -
19