100 TECHNIQUES OF COUNTING [CHAP. 5
PIGEONHOLE PRINCIPLE
5.19. Find the minimum numbernof integers to be selected fromS={ 1 , 2 ,..., 9 }so that: (a) The sum of
two of thenintegers is even. (b) The difference of two of thenintegers is 5.(a) The sum of two even integers or of two odd integers is even. Consider the subsets {1, 3, 5, 7, 9} and {2, 4, 6, 8}
ofSas pigeonholes. Hencen=3.
(b) Consider the five subsets {1, 6}, {2, 7}, {3, 8}, {4, 9}, {5} ofSas pigeonholes. Thenn=6 will guarantee that two
integers will belong to one of the subsets and their difference will be 5.5.20. Find the minimum number of students needed to guarantee that five of them belong to the same class
(Freshman, Sophomore, Junior, Senior).
Here then=4 classes are the pigeonholes andk+ 1 =5sok=4. Thus among anykn+ 1 =17 students (pigeons),
five of them belong to the same class.5.21. LetLbe a list (not necessarily in alphabetical order) of the 26 letters in the English alphabet (which
consists of 5 vowels,A,E,I,O,U, and 21 consonants).(a) Show thatLhas a sublist consisting of four or more consecutive consonants.
(b) AssumingLbegins with a vowel, sayA, show thatLhas a sublist consisting of five or more
consecutive consonants.
(a) The five letters partitionLinton=6 sublists (pigeonholes) of consecutive consonants. Herek+ 1 =4 and so
k=3. Hencenk+ 1 = 6 ( 3 )+ 1 = 19 <21. Hence some sublist has at least four consecutive consonants.
(b) SinceLbegins with a vowel, the remainder of the vowels partitionLinton=5 sublists. Herek+ 1 =5 and so
k=4. Hencekn+ 1 =21. Thus some sublist has at least five consecutive consonants.INCLUSION–EXCLUSION PRINCIPLE
5.22. There are 22 female students and 18 male students in a classroom. Find the total numbertof students.
The sets of male and female students are disjoint; hencet= 22 + 18 =40.5.23. Suppose among 32 people who save paper or bottles (or both) for recycling, there are 30 who save paper
and 14 who save bottles. Find the numbermof people who:
(a) save both; (b) save only paper; (c) save only bottles.
LetPandBdenote the sets of people saving paper and bottles, respectively. Then:
(a) m=n(P∩B)=n(P )+n(B)−n(P∪B)= 30 + 14 − 32 = 12
(b) m=n(P\B)=n(P )−n(P∩B)= 30 − 12 = 18
(c) m=n(B\P)=n(B)−n(P∩B)= 14 − 12 = 25.24. LetA,B,C,Ddenote, respectively, art, biology, chemistry, and drama courses. Find the numberNof
students in a dormitory given the data:12 takeA, 5 takeAandB, 4 takeBandD, 2 takeB,C,D,
20 takeB, 7 takeAandC, 3 takeCandD, 3 takeA, C, D,
20 takeC, 4 takeAandD, 3 takeA, B, C, 2 take all four,
8 takeD, 16 takeBandC, 2 takeA, B, D, 71 take none.LetTbe the number of students who take at least one course. By the Inclusion–Exclusion Principle Theorem 5.9,
T=s 1 −s 2 +s 3 −s 4 where:
s 1 = 12 + 20 + 20 + 8 = 60 ,s 2 = 5 + 7 + 4 + 16 + 4 + 3 = 39 ,
s 3 = 3 + 2 + 2 + 3 = 10 ,s 4 = 2.
ThusT=29, andN= 71 +T=100.