Exercises 263
- Prove that in any class of more than 101 students, at least two must receive the same
grade for an exam with grading scale of 0 to 100.
- Prove that for any 44 people, at least four must be born in the same month.
- Prove that in any class of 35 students, at least seven receive the same final grade, where
the scale is A-B-C-D-F.
- Area codes are used to distinguish phone numbers for which the last seven digits are
the same. If you have 35,000,000 phone numbers in a state and an area code can
distinguish approximately 900,000 phone numbers, how many area codes are needed
to distinguish the phone numbers of this state?
- There are 35,000 students at State University. Each student takes four different courses
each term. State University offers 999 courses each term. The largest classroom on
campus holds 135 students. Is this a problem? If so, what is the problem?
- At Bridgetown University, there are 45 time periods during the week for scheduling
classes. Use the Generalized Pigeon-Hole Principle to determine how many rooms (at
least) are needed if 780 different classes are to be scheduled in the 45 time slots.
- Suppose someone (say, Aesop) is marking days in some leap year (say, 2948). You do
not know which days he marks, only how many. Use this to answer the following ques-
tions. (Warning: Some, but not all, of these questions use the Pigeon-Hole Principle.)
(a) How many days would Aesop have to mark before you can conclude that he
marked two days in January?
(b) How many days would Aesop have to mark before you can conclude that he
marked two days in February?
(c) How many days would Aesop have to mark before you can conclude that he
marked two days in the same month?
(d) How many days would Aesop have to mark before you can conclude that he
marked three days in the same month?
(e) How many days would Aesop have to mark before you can conclude that he
marked three days with the same date (for example, the third of three different
months, or the 31st of three different months)?
(f) How many days would Aesop have to mark before you can conclude that he
marked two consecutive days (for example, January 31 and February 1)?
(g) How many days would Aesop have to mark before you can conclude that he
marked three consecutive days?
- Prove that for any collection of n people, two persons have the exact same number of
acquaintances in the group provided that each person has at least one acquaintance.
- There are five suburbs in the city of Melbourn. How many all-stars must be picked
from each suburb to guarantee that at least five players come from the same suburb?
- A bowl contains raspberry and orange lollipops, with 15 of each. How many must be
drawn one at a time to ensure that you have at least three orange lollipops?
- A man has 10 black socks and 11 blue socks scrambled in a drawer. Still half-asleep,
the man reaches in the drawer to get a pair of matching socks. How many socks
should he select, one at a time, before he will be sure that he has a matching pair. How
many selections are needed to be sure he has a blue pair?
- Prove that:
(a) 0.999999.. .99... = 1
(b) 0.346270 = 0.346269
