Page 426 - Discrete Mathematics and Its Applications

6.2 The Pigeonhole Principle 405

people where every two people are friends or enemies, there may not be three mutual friends or
three mutual enemies (see Exercise 26).
It is possible to prove some useful properties about Ramsey numbers, but for the most
part it is difficult to find their exact values. Note that by symmetry it can be shown that
R(m, n) = R(n, m) (see Exercise 30).We also have R(2,n) = n for every positive integer n ≥ 2
(see Exercise 29). 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, in-
cluding R(5, 5), which is known to satisfy 43 ≤ R(5, 5) ≤ 49. The reader interested in learning
more about Ramsey numbers should consult [MiRo91] or [GrRoSp90].

Exercises

1. Show that in any set of six classes, each meeting regu- ∗ 11. Let (x i ,y i ,z i ), i = 1, 2, 3, 4, 5, 6, 7, 8, 9, be a set of nine
larly once a week on a particular day of the week, there distinctpointswithintegercoordinatesinxyzspace.Show
must be two that meet on the same day, assuming that no that the midpoint of at least one pair of these points has
classes are held on weekends. integer coordinates.
2. Show that if there are 30 students in a class, then at least 12. How many ordered pairs of integers (a, b) are
two have last names that begin with the same letter. needed to guarantee that there are two ordered pairs
(a 1 ,b 1 ) and (a 2 ,b 2 ) such that a 1 mod 5 = a 2 mod 5
3. A drawer contains a dozen brown socks and a dozen black
and b 1 mod 5 = b 2 mod 5?
socks, all unmatched. A man takes socks out at random
in the dark. 13. a) Show that if five integers are selected from the first
eight positive integers, there must be a pair of these
a) How many socks must he take out to be sure that he
has at least two socks of the same color? integers with a sum equal to 9.
b) Is the conclusion in part (a) true if four integers are
b) How many socks must he take out to be sure that he selected rather than five?
has at least two black socks?
14. a) Show that if seven integers are selected from the first
4. A bowl contains 10 red balls and 10 blue balls. A woman
10 positive integers, there must be at least two pairs
selects balls at random without looking at them.
of these integers with the sum 11.
a) How many balls must she select to be sure of having
b) Is the conclusion in part (a) true if six integers are
at least three balls of the same color?
selected rather than seven?
b) How many balls must she select to be sure of having
at least three blue balls? 15. How many numbers must be selected from the set
{1, 2, 3, 4, 5, 6} to guarantee that at least one pair of these
5. Show that among any group of five (not necessarily con- numbers add up to 7?
secutive) integers, there are two with the same remainder
when divided by 4. 16. How many numbers must be selected from the set
{1, 3, 5, 7, 9, 11, 13, 15} to guarantee that at least one pair
6. Let d be a positive integer. Show that among any group of
of these numbers add up to 16?
d + 1 (not necessarily consecutive) integers there are two
with exactly the same remainder when they are divided 17. A company stores products in a warehouse. Storage bins
by d. in this warehouse are specified by their aisle, location
in the aisle, and shelf. There are 50 aisles, 85 horizontal
7. Let n be a positive integer. Show that in any set of n locations in each aisle, and 5 shelves throughout the ware-
consecutive integers there is exactly one divisible by n. house. What is the least number of products the company
8. Show that if f is a function from S to T , where S and T can have so that at least two products must be stored in
the same bin?
are finite sets with |S| > |T |, then there are elements s 1
and s 2 in S such that f(s 1 ) = f(s 2 ), or in other words, f 18. Suppose that there are nine students in a discrete mathe-
is not one-to-one. matics class at a small college.
9. What is the minimum number of students, each of whom a) Show that the class must have at least five male stu-
comes from one of the 50 states, who must be enrolled in dents or at least five female students.
a university to guarantee that there are at least 100 who b) Show that the class must have at least three male stu-
come from the same state? dents or at least seven female students.
∗ 10. Let (x i ,y i ), i = 1, 2, 3, 4, 5, be a set of five distinct points 19. Suppose that every student in a discrete mathematics class
with integer coordinates in the xy plane. Show that the of 25 students is a freshman, a sophomore, or a junior.
midpoint of the line joining at least one pair of these a) Show that there are at least nine freshmen, at least
points has integer coordinates. nine sophomores, or at least nine juniors in the class.