Discrete Mathematics

Spring 2017
Previous Lecture
Binomial Coefficients
Pascal’s Triangle
The Pigeonhole Principle
If a flock of 20 pigeons roosts in a set of 19 pigeonholes, one
of the pigeonholes must have more than 1 pigeon
The Pigeonhole Principle
Pigeonhole Principle: If k is a positive integer and k + 1
objects are placed into k boxes, then at least one box contains
two or more objects
Proof: We use a proof by contraposition. Suppose none of the
k boxes has more than one object. Then the total number of
objects would be at most k. This contradicts the statement
that we have k + 1 objects
Corollary: A function f from a set with k + 1 elements to a
set with k elements is not one-to-one
The Pigeonhole Principle
Corollary: A function f from a set with k + 1 elements to a
set with k elements is not one-to-one
Proof: Use the pigeonhole principle
Create a box for each element y in the codomain of f
Put in the box for y all of the elements x from the domain
such that f (x) = y
Because there are k + 1 elements and only k boxes, at least
one box has two or more elements
Hence, f cannot be one-to-one
Pigeonhole Principle
Example: Among any group of 367 people, there must be at
least two with the same birthday, because there are only 366
possible birthdays
Example: Show that for every integer n there is a multiple of
n that has only 0s and 1s in its decimal expansion
Solution: Let n be a positive integer. Consider the n + 1
integers 1, 11, 111, . . . , 11 . . . 1 (where the last number has
n + 1 1s)
There are n possible remainders when an integer is divided by
n. By the pigeonhole principle, when each of the n + 1 integers
is divided by n, at least two must have the same remainder.
Subtract the smaller from the larger and the result is a
multiple of n that has only 0s and 1s in its decimal expansion
Pigeonhole Principle

Example: While on a four-week vacation, Herbert will play at least

one set of tennis each day, but he will not play more than 40 sets
total during this time. Prove that no matter how he distributes his
sets during the four weeks, there is a span of consecutive days
during which he will play exactly 15 sets

Solution: For 1 ≤ i ≤ 28, let xi be the total number of sets Herbert

will play from the start of the vacation to the end of ith day
Then 1 ≤ x1 < x2 < · · · < x28 ≤ 40 and
x1 + 15 < x2 + 15 < · · · < x28 + 15 ≤ 55
We have the 28 distinct numbers x1 , x2 , . . . , x28 and the 28
distinct numbers x1 + 15, x2 + 15, . . . , x28 + 15
Pigeonhole Principle

These 56 numbers can take only 55 different values, so at least

two of them are equal

If for 1 ≤ i < j ≤ 28 we have xi + 15 = xj , then from the start of

day i + 1 to the end of day j, Herbert will play exactly 15 sets of
tennis
The Generalized Pigeonhole Principle

Principle: If N objects are placed into k boxes, then there is at

least one box containing at least dN/ke objects

Proof: We use a proof by contraposition. Suppose that none of

the boxes contains more than dN/ke − 1 objects. Then the total
number of objects is at most
k(d Nk e − 1) < k(( Nk + 1) − 1) = N,
where the inequality dN/ke < N/k + 1 has been used. This is a
contradiction because there are a total of n objects

Example: Among 100 people there are at least d100/12e = 9 who

were born in the same month
The Generalized Pigeonhole Principle
Example: You are selecting cards from a deck of 52 cards.

How many cards must be selected from a standard deck of 52 cards to

guarantee that at least three cards of the same suit are chosen?

How many must be selected to guarantee that at least three hearts are
selected?

Solution:

We assume four boxes; one for each suit. Using the generalized
pigeonhole principle, at least one box contains at least dN/4e cards. At
least three cards of one suit are selected if dN/4e ≥ 3. The smallest
integer N such that dN/4e ≥ 3 is N = 2 × 4 + 1 = 9

A deck contains 13 hearts and 39 cards which are not hearts. So, if we
select 41 cards, we may have 39 cards which are not hearts along with 2
hearts. However, when we select 42 cards, we must have at least three
hearts. (Note that the generalized pigeonhole principle is not used here)
The Generalized Pigeonhole Principle

Example: Suppose that a computer science laboratory has 15

workstations and 10 servers. A cable can be used to directly
connect a workstation to a server. For each server, only one direct
connection to that server can be active at any time. We want to
guarantee that at any time any set of 10 or fewer workstations can
simultaneously access different servers via direct connections
Although we could do this by connecting every workstation directly
to every server (using 150 connections), what is the minimum
number of direct connections needed to achieve the goal?
The Generalized Pigeonhole Principle

Solution: Let us label workstations W1 , W2 , . . . , W15 and the

servers S1 , S2 , . . . , S10
Let us connect Wk to Sk for k = 1, 2, . . . , 10 and each of W11 ,
W12 , W13 , W14 , and W15 to all 10 servers. We have a total of 60
direct connections
Clearly any set of 10 or fewer workstations can simultaneously
access different servers
Now suppose that there are fewer than 60 direct connections
Then some server is connected to at most 5 workstations. (If all
servers were connected to at least 6 workstations, there would be
at least 60 connections)
This means that the remaining 9 servers are not enough to allow
other 10 workstations to simultaneously access different servers
Ramsey Numbers
Assume that in a group of six people, each two individuals are
either friends or enemies. Show that there are either three mutual
friends or three mutual enemies in the group

Solution:
Let A be one of the six people
Of the five other people in the group, there are either three or
more who are friends of A, or three or more who are enemies of A
Indeed, by the generalized pigeonhole principle, when 5 objects are
divided into 2 sets, one of the sets contains at least d5/2e = 3
objects
In the former case, suppose that B, C , and D are friends of A
If any of these 3 individuals are friends, then these two and A form
a group of 3 friends
Otherwise, B, C , and D form a group of 3 enemies
Ramsey Numbers

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

In the example above we showed that R(3, 3) ≤ 6

Pigeonhole Principle: Examples

An auditorium has a seating capacity of 800. How many seats

must be occupied to guarantee that at least two people seated in
the auditorium have the same first and last initials

Let ABCD be a square with AB = 1. Show that if we select 5

points in the interior of this square,
√ there are at least two whose
distance apart is less than 1/ 2
Homework for practice (not graded)
Exercises from the Book:

Section 6.2: Exercises 2, 4, 6, 8, 12