PAGE 1

GEH1036 TUTORIAL 2 (WEEK 4)

1. Find the number of integers from 1 to 1000 inclusive which are

(a) multiples of at least one of the integers 3, 5, 7,
(b) multiples of at least two of the integers 3, 5, 7,
(c) multiples of exactly one of the integers 3, 5, 7.

Solution. Let U = {1, 2, . . . , 1000} and Ak be multiples of k in U .

(a)

|A3 ∪ A5 ∪ A7 | = |A3 | + |A5 | + |A7 | − |A3 ∩ A5 | − |A3 ∩ A7 | − |A5 ∩ A7 | + |A3 ∩ A5 ∩ A7 |

= |A3 | + |A5 | + |A7 | − |A15 | − |A21 | − |A35 | + |A105 |
= 333 + 200 + 142 − 66 − 47 − 28 + 9 = 543.

(b)

|(A3 ∩ A5 ) ∪ (A5 ∩ A7 ) ∪ (A3 ∩ A7 )| = |A15 | + |A35 | + |A21 | − |A15 ∩ A35 |

− |A15 ∩ A21 | − |A35 ∩ A21 | + |A15 ∩ A21 ∩ A35 |
= |A15 | + |A35 | + |A21 | − 2|A105 |
= 66 + 28 + 47 − 18 = 123.

(c)
|A3 ∪ A5 ∪ A7 | − |(A3 ∩ A5 ) ∪ (A5 ∩ A7 ) ∪ (A3 ∩ A7 )| = 543 − 123 = 420.
The second part of the LHS are the integers that belong to at least two of the sets.

2. Determine the number of integers between 1 and 2011 inclusive, which are multiples of
6 or 7 or 9 but not multiples of 12.

Solution. Let Ai be multiples of i that are between 1 and 2011 inclusive. Now

|A6 ∪ A7 ∪ A9 | = |A6 | + |A7 | + |A9 | − |A42 | − |A18 | − |A63 | + |A126 |

= 335 + 287 + 223 − 47 − 111 − 31 + 15 = 671.

Note that multiples of 12 in A6 ∪ A7 ∪ A9 are just multiples of 12 between 1 and 2011

inclusive. Thus the answer is 671 − ⌊2011/12⌋ = 671 − 167 = 504.

3. Internet smileys are used to convey the mood or facial expression of the sender and
each consists of a sequence xyz of symbols, where x could be : or ; or ! or 8, y could be a
blank space or - or = or 3, and z could be ( or ) or p or b. Some examples are:
 PAGE 2

:-) 8=( !=p

How many types of moods and expressions can be represented by these smileys?

Solution. Each of the symbols x, y, z can be chosen in 4 ways. Thus the answer is
43 = 64.

4. Find the number of ways of having a group photograph taken of a group of one teacher,
10 girls and 10 boys in the following cases.
(a) The teacher and girls are to be seated in a row with the boys standing behind in a row.
(b) The teacher and girls are to be seated in a row with the teacher in the centre while
the boys are to stand behind in a row.

Solution. (a) Number of ways of seating the teacher and 10 girls in the first row = 11!.
Number of ways of seating the 10 boys in the second row = 10!. Hence the number of ways
of getting the photograph taken = 11!10!.
(b) If the teacher is to be seated in the centre, the number of ways of seating the teacher
and 10 girls in the first row = 10!. Hence the required number of ways in this case is
10! × 10!.

5. In a pharmaceutical study, two drugs (A and B) and a placebo are to be compared

for effects. Fifty people are to be used in the study, of whom 20 are to receive drug A,
20 to receive drug B, and the remainder to receive the placebo. Assuming the people are
numbered from 1 to 50, how many different ways can the assignment of the drugs and
placebo be made?
Hint. What is the most practical way to make the required assignment? Instead of assigning
the drugs or placebo to people, think of first selecting the people to be assigned to drug A,
then the people to be assigned to drug B and finally the remaining people to be assigned to
the placebo.

Solution. The procedure of assigning the drugs and placebo can be performed as a se-
quence of the following three procedures:
(a) select 20 people out of the 50 people and assign drug A to each of the selected,
(b) select 20 people out of the remaining 30 people and assign drug B to each of the
selected,
(c) select 10 people out of the last remaining 10 people and assign placebo to each of the
selected.
 PAGE 3
( ) (30) (10)
Procedure (a) can be performed in 50 20 ways, (b) in 20 ways and (c) in 10 ways. By
the rs-principle, the total number of ways of assigning the drugs and placebo is
( )( )( )
50 30 10 50!
= .
20 20 10 20!20!10!

6. In how many ways can 5 integers be chosen from 1, 2, . . . , 20 so that no two are consec-
utive?

Solution. Represent each number chosen by 1 and not chosen by 0. Then the answer
is given by the permutation of these 20 symbols so that the 1’s are not adjacent. This is
the same as choosing 5 slots( for
) the 1’s among the 16 slots created by the 0’s. Thus the
16
required number of ways is 5 = 4368.

7. In the following problems, assume that the rooks are all identical.
(a) Find the number of ways of placing 8 rooks on an 8 × 8 chessboard so that none of
them can capture another. (Observe that the rooks must be placed in different rows.)
(b) Find the number of ways of placing 6 rooks on an 8 × 8 chessboard so that none of
them can capture another. (First decide which rows you want to place the rooks. Having
chosen the rows, how can you place the 6 rooks?)
(c) For any integer k between 1 and 8 inclusive, write down a general expression for the
number of ways of placing k rooks on an 8 × 8 chessboard so that none of them can capture
another.

Solution. (a) In the first row (from the top) there are 8 ways to place a rook. Having
done that, there are only 7 ways to place a rook in the second row, 6 ways in the third
row, and so on. The total number of ways is 8!.
(b) Clearly, a row cannot have( )more than one rook. First, choose 6 rows in which to
place the 6 rooks. There are 86 = 28 choices. Second, place a rook in the first of these
rows chosen. We have 8 choices. Next, place a rook in the second of those rows chosen.
We have 7 choices (since it cannot be in the same column as the first rook). Continue
this procedure until 6 rooks are in place. The total number of ways of performing this
procedure is 28 × 8 × 7 × 6 × 5 × 4 × 3 = 564480.

(8) ≤ 8!k ≤ 8) rooks in the required position.

(c) The above procedure can be used(to) place k(1
8 8
The number of ways of doing this is k Pk = k (8−k)! .

8. In how many ways can five couples be seated at a round table in the following cases:
(a) there are no restrictions on the sitting arrangement,
 PAGE 4

(b) males and females alternate each other,

(c) males and females alternate each other, and the partners of each couple sit next to
each other,

Solution. (a) The number of unrestricted sitting arrangements is 9! = 362880.

(b) Starting from the position of a given male as reference point, arrange the other persons
in a clockwise direction so that the next person is a female, then a male, then a female,
and so on. The number of ways of doing so is 5! × 4! = 2880.
(c) Going in a clockwise direction, each couple can be seated as xy or yx. Once this is
chosen, the adjacent couple can only sit in one way. Again, using one particular couple as
reference point, arrange the other couples in a clockwise direction. Hence the total number
of such arrangements is 2 × 4! = 48.