CMPS 2120 Lecture Notes - The Pigeonhole Principle
The pigeonhole principle works for particular types of counting problems.
1. Show that in any set of six classes there must be two that meet on the
same day of the week, assuming that no classes are held on weekends.
pigeons = 6 classes
holes = 5 days
Start by filling up each empty hole with a class.
1 1 1 1 1
Mon Tue Wed Thu Fri
Since the 6th class must go in a hole that already has a class, two
classes must meet on the same day.
2. A drawer contains a dozen brown socks and a dozen black socks, all
unmatched. A man takes socks out at random in the dark.
a) How many socks must he pick to guarantee two socks of the same color?
holes = 2 colors
pigeons = 24 socks (12 brown socks and 12 black socks)
Thus, 3 socks will guarantee 2 socks of the same color.
1 1 <- the next sock guarantees a solution
----- -----
brown black
b) How many socks must he pick to guarantee at least two black socks?
holes = 1 hole for black socks and 1 hole for brown colors
pigeons = 24 socks (12 black and 12 brown)
Worst case, the first 12 picks are brown.
12 <- the next 2 picks guarantee a solution
----- -----
brown black
ANS: 14
3. Show that among any group of five (not necessarily consecutive) integers,
there are two with the same remainder when divided by 4.
Mod 4 constitutes 4 pigeonholes : 0 1 2 3
thus, of any 5 numbers, two will have the same remainder
4. Let n be a positive integer. Show that in any set of n consecutive integers
there is exactly one divisible by n.
Mod n constitutes n pigeonholes : 0 1 2 3 .. n-1
For any n consecutive integers, mod n = 0 will only occur once.
5. What is the minimum number of students, each of whom comes from one of the
50 states, enrolled in a university to guarantee that there are at least
100 who come from the same state?
50 states = 50 pigeonholes
Worst case, each of the 50 states will have 99 students. The next student
will guarantee 100 from the same state.
99 students in all the other holes + 1 in the final hole. Thus,
99 * 50 + 1 = 4951 students.
99 99 99 99 99 ..99
1
-- -- -- -- --...--
#1 #2 #3 #4 #5 ...#50
6. a) Show that if five integers are selected from the first eight positive
integers, there must be a pair of these integers with a sum equal to 9.
S = { 1,2,3,4,5,6,7,8 }
possible x,y solutions = (1,8), (2,7), (3,6), (4,5)
hole #1 holds x value: (1,2,3,4)
hole #2 holds y value: (8,7,6,5)
As soon as you pick 5 integers you are guaranteed a solution.
b) Is the conclusion in part (a) true if four integers are selected rather
than five?
No. There is no way to guarantee a solution by picking 4. Ex: 1,2,6,5.
7. How many numbers must be selected from the set {1, 2, 3, 4, 5, 6} to
guarantee that at least one pair of these numbers add up to 7?
solution pairs: (1,6) (2,5) (3,4)
hole #1: for numbers 1 2 3
hole #2: for numbers 4 5 6
111 1
--- ---
#1 #2
If you pick 4 numbers you are guaranteed to hit a solution
8. Th Party Problem. Show that among any 6 people, there are always 3 that are
mutual friends OR 3 that are mutual enemies.
Let people be denoted by 1,2,3,4,5,6. The pigeonholes are the friends and
enemies that each person has:
-- -- -- -- -- -- -- -- -- -- -- --
1F 1E 2F 2E 3F 3E 4F 4E 5F 5E 6F 6E
Each of the two pigeonholes for each person must have 2 numbers that add
to 5, accounting for the relationship between person n and the other 5
people. The number of pigeons in the pigeonholes must be one of these tuples:
(1,4), (2,3), (3,2), (4,1), (5,0)
What you want to PREVENT is the following:
(1->2; 2->3; 1->3
Now try to fill up the pigeonholes so that there is NEVER 3 that are all
friends or 3 that are all enemies.
2345 6 6 1345 # so far so good; no one
---- -- -- ---- -- -- -- -- -- -- -- -- # is a mutual friend or
1F 1E 2F 2E 3F 3E 4F 4E 5F 5E 6F 6E # mutual enemy yet
* ** ***
2345 6 6 1345 1 2456 # no matter how you
---- -- -- ---- -- ---- -- -- -- -- -- -- # fill the pigeonhole
1F 1E 2F 2E 3F 3E 4F 4E 5F 5E 6F 6E # for person 3, two
# people are mutual
# friends or enemies
* ** ***
2345 6 6 1345 1 2456 16 2 # no matter how you
---- -- -- ---- -- ---- -- -- -- -- -- -- # fill the pigeonhole
1F 1E 2F 2E 3F 3E 4F 4E 5F 5E 6F 6E # for person 4, two
# people are mutual
# friends or enemies
9. The Party/Graph Problem. Equivalently, no matter how you color the 15 edges
of a complete graph on 6 points red or blue, you will always have either a
red triangle or a blue triangle (these are monochromatic. triangles). Show
that you must always have at least two such monochromatic triangles; e.g.,
Suppose you 2-color the edges of the complete graph on 7 points. What is the
smallest number of monochromatic triangles you can have?
How about for 8 points?