Page 427 - Discrete Mathematics and Its Applications

406 6 / Counting

b) Show that there are either at least three freshmen, at Nicole did, that there had to be two Parisians with the
least 19 sophomores, or at least five juniors in the same number of hairs on their heads. Then use the gener-
class. alized pigeonhole principle to show that there had to be
20. Find an increasing subsequence of maximal length and at least five Parisians at that time with the same number
a decreasing subsequence of maximal length in the se- of hairs on their heads.
quence 22, 5, 7, 2, 23, 10, 15, 21, 3, 17. 34. Assuming that no one has more than 1,000,000 hairs on
21. Construct a sequence of 16 positive integers that has no the head of any person and that the population of New
increasing or decreasing subsequence of five terms. York City was 8,008,278 in 2010, show there had to be at
22. Show that if there are 101 people of different heights least nine people in NewYork City in 2010 with the same
standing in a line, it is possible to find 11 people in the number of hairs on their heads.
order they are standing in the line with heights that are 35. There are 38 different time periods during which classes
either increasing or decreasing. at a university can be scheduled. If there are 677 different
∗ 23. Show that whenever 25 girls and 25 boys are seated classes, how many different rooms will be needed?
around a circular table there is always a person both of 36. Acomputernetworkconsistsofsixcomputers.Eachcom-
whose neighbors are boys. puter is directly connected to at least one of the other com-
∗∗ 24. Suppose that 21 girls and 21 boys enter a mathemat- puters. Show that there are at least two computers in the
ics competition. Furthermore, suppose that each entrant network that are directly connected to the same number
solves at most six questions, and for every boy-girl pair, of other computers.
there is at least one question that they both solved. Show
37. Acomputernetworkconsistsofsixcomputers.Eachcom-
that there is a question that was solved by at least three
puter is directly connected to zero or more of the other
girls and at least three boys.
computers. Show that there are at least two computers in
∗ 25. Describe an algorithm in pseudocode for producing the the network that are directly connected to the same num-
largest increasing or decreasing subsequence of a se- ber of other computers. [Hint: It is impossible to have
quence of distinct integers. a computer linked to none of the others and a computer
26. Show that in a group of five people (where any two people linked to all the others.]
are either friends or enemies), there are not necessarily
38. Find the least number of cables required to connect eight
three mutual friends or three mutual enemies.
computers to four printers to guarantee that for every
27. Show that in a group of 10 people (where any two people choice of four of the eight computers, these four com-
are either friends or enemies), there are either three mu- puters can directly access four different printers. Justify
tual friends or four mutual enemies, and there are either your answer.
three mutual enemies or four mutual friends.
39. Find the least number of cables required to connect 100
28. Use Exercise 27 to show that among any group of 20 computers to 20 printers to guarantee that 2every subset
people (where any two people are either friends or ene- of 20 computers can directly access 20 different printers.
mies), there are either four mutual friends or four mutual (Here, the assumptions about cables and computers are
enemies. the same as in Example 9.) Justify your answer.
29. Show that if n is an integer with n ≥ 2, then the Ramsey ∗ 40. Prove that at a party where there are at least two people,
number R(2,n) equals n. (Recall that Ramsey numbers there are two people who know the same number of other
were discussed after Example 13 in Section 6.2.)
people there.
30. Show that if m and n are integers with m ≥ 2 and n ≥ 2,
then the Ramsey numbers R(m, n) and R(n, m) are equal. 41. An arm wrestler is the champion for a period of 75 hours.
(Recall that Ramsey numbers were discussed after Exam- (Here, by an hour, we mean a period starting from an
ple 13 in Section 6.2.) exact hour, such as 1 p.m., until the next hour.) The arm
wrestler had at least one match an hour, but no more than
31. Show that there are at least six people in California (pop- 125 total matches. Show that there is a period of consec-
ulation: 37 million) with the same three initials who were utive hours during which the arm wrestler had exactly 24
born on the same day of the year (but not necessarily in matches.
the same year). Assume that everyone has three initials.
∗ 42. Is the statement in Exercise 41 true if 24 is replaced by
32. Show that if there are 100,000,000 wage earners in the
United States who earn less than 1,000,000 dollars (but a) 2? b) 23? c) 25? d) 30?
at least a penny), then there are two who earned exactly 43. Show that if f is a function from S to T , where S and T are
the same amount of money, to the penny, last year. nonempty finite sets and m = |S| / |T | , then there are at
33. In the 17th century, there were more than 800,000 inhab- least m elements of S mapped to the same value of T .That
itants of Paris.At the time, it was believed that no one had is, show that there are distinct elements s 1 ,s 2 ,...,s m of S
more than 200,000 hairs on their head. Assuming these such that f(s 1 ) = f(s 2 ) = ··· = f(s m ).
numbers are correct and that everyone has at least one hair 44. There are 51 houses on a street. Each house has an address
on their head (that is, no one is completely bald), use the between 1000 and 1099, inclusive. Show that at least two
pigeonhole principle to show, as the French writer Pierre houses have addresses that are consecutive integers.