In how many ways can five books and three magazines be selected from eight books and six magazines?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Number of ways to select books} = {}^{\mathrm{8}}\mathrm{C}_{\mathrm{5}} = \frac{\mathrm{8}!}{\mathrm{5}!\mathrm{3}!} = \mathrm{56} \\
& \text{Number of ways to select magazines} = {}^{\mathrm{6}}\mathrm{C}_{\mathrm{3}} = \frac{\mathrm{6}!}{\mathrm{3}!\mathrm{3}!} = \mathrm{20} \\
& \text{Total number of ways} = \mathrm{56} \times \mathrm{20} \\
& = \mathrm{1120}
\end{aligned} $$
Problem 2
Let $\displaystyle \mathrm{A}$ and $\displaystyle \mathrm{B}$ be two given sets such that $\displaystyle \mathrm{n}(\mathrm{A})=\mathrm{12}$ and $\displaystyle \mathrm{n}(\mathrm{B})=\mathrm{18}$. In how many ways can two elements, one of which is from $\displaystyle \mathrm{A}\setminus \mathrm{B}$ and the other is from $\displaystyle \mathrm{B}\setminus \mathrm{A}$, be chosen if $\displaystyle \mathrm{n}(\mathrm{A}\cap \mathrm{B})=\mathrm{6}$ and the order of selection does not matter?
A doctor sees $\displaystyle \mathrm{6}$ patients in a given week. In how many ways can the doctor do this in such a way that (any) three of them on Monday, the other two on Tuesday, the remaining one on Thursday, and the order of patients on the same day does not matter?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Ways to select } \mathrm{3} \text{ patients for Monday} = {}^{\mathrm{6}}\mathrm{C}_{\mathrm{3}} = \mathrm{20} \\
& \text{Ways to select } \mathrm{2} \text{ patients for Tuesday} = {}^{\mathrm{3}}\mathrm{C}_{\mathrm{2}} = \mathrm{3} \\
& \text{Ways to select } \mathrm{1} \text{ patient for Thursday} = {}^{\mathrm{1}}\mathrm{C}_{\mathrm{1}} = \mathrm{1} \\
& \text{Total number of ways} = \mathrm{20} \times \mathrm{3} \times \mathrm{1} = \mathrm{60}
\end{aligned} $$
Problem 4
A committee of some people is to be chosen from a group of $\displaystyle \mathrm{7}$ women and $\displaystyle \mathrm{4}$ men. How many ways are there to do so if the committee must have equal numbers of women and men?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Possible equal combinations are (1W, 1M), (2W, 2M), (3W, 3M), (4W, 4M).} \\
& \text{Ways for 1W and 1M} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{1}} \times {}^{\mathrm{4}}\mathrm{C}_{\mathrm{1}} = \mathrm{7} \times \mathrm{4} = \mathrm{28} \\
& \text{Ways for 2W and 2M} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{2}} \times {}^{\mathrm{4}}\mathrm{C}_{\mathrm{2}} = \mathrm{21} \times \mathrm{6} = \mathrm{126} \\
& \text{Ways for 3W and 3M} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{3}} \times {}^{\mathrm{4}}\mathrm{C}_{\mathrm{3}} = \mathrm{35} \times \mathrm{4} = \mathrm{140} \\
& \text{Ways for 4W and 4M} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{4}} \times {}^{\mathrm{4}}\mathrm{C}_{\mathrm{4}} = \mathrm{35} \times \mathrm{1} = \mathrm{35} \\
& \text{Total number of ways} = \mathrm{28} + \mathrm{126} + \mathrm{140} + \mathrm{35} = \mathrm{329}
\end{aligned} $$
Problem 5
How many permutations of the letters in the word SINGER are there satisfying all the following conditions:
(i) S precedes I.
(ii) I precedes N.
(iii) N precedes G.
Here "precedes" means "occurs earlier than", but not necessarily "immediately before".
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The word SINGER has } \mathrm{6} \text{ letters.} \\
& \text{Total permutations without restriction} = \mathrm{6}! = \mathrm{720} \\
& \text{The } \mathrm{4} \text{ letters S, I, N, G must appear in a fixed relative order (S-I-N-G).} \\
& \text{Any } \mathrm{4} \text{ letters can be arranged in } \mathrm{4}! = \mathrm{24} \text{ ways, but only } \mathrm{1} \text{ way satisfies the condition.} \\
& \text{Required permutations} = \frac{\mathrm{6}!}{\mathrm{4}!} = \frac{\mathrm{720}}{\mathrm{24}} = \mathrm{30}
\end{aligned} $$
Problem 6
Find how many ways two mangoes (M) and three watermelons (W) can be placed in a line if the five fruits are distinguishable and the mangoes:
a. must not be separated
b. must be separated
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) Mangoes must not be separated:} \\
& \text{Treat the } \mathrm{2} \text{ mangoes as } \mathrm{1} \text{ unit. Total units} = \mathrm{1} + \mathrm{3} = \mathrm{4} \text{ units.} \\
& \text{Arrange units} = \mathrm{4}! = \mathrm{24} \\
& \text{Arrange mangoes internally} = \mathrm{2}! = \mathrm{2} \\
& \text{Total ways} = \mathrm{24} \times \mathrm{2} = \mathrm{48} \\
& \\
& \text{(b) Mangoes must be separated:} \\
& \text{Total arrangements without restriction} = \mathrm{5}! = \mathrm{120} \\
& \text{Ways they are separated} = \text{Total} - \text{Ways they are together} \\
& = \mathrm{120} - \mathrm{48} = \mathrm{72}
\end{aligned} $$
Problem 7
In how many ways can four boys and three girls stand in a row when no two girls are allowed to stand next to each other?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{First, arrange the } \mathrm{4} \text{ boys. Number of ways} = \mathrm{4}! = \mathrm{24} \\
& \text{The } \mathrm{4} \text{ boys create } \mathrm{5} \text{ spaces (including ends): } \_ \text{ B } \_ \text{ B } \_ \text{ B } \_ \text{ B } \_ \\
& \text{Arrange } \mathrm{3} \text{ girls in these } \mathrm{5} \text{ spaces.} \\
& \text{Number of ways to place girls} = {}^{\mathrm{5}}\mathrm{P}_{\mathrm{3}} = \mathrm{5} \times \mathrm{4} \times \mathrm{3} = \mathrm{60} \\
& \text{Total number of ways} = \mathrm{24} \times \mathrm{60} = \mathrm{1440}
\end{aligned} $$
Problem 8
Find the number of ways of arranging six men in a line so that:
a. the oldest man is at the far-left side
b. the two youngest men are at the far-right side
c. the shortest man is at neither end of the line.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) The oldest man is fixed at far-left.} \\
& \text{Arrange the remaining } \mathrm{5} \text{ men} = \mathrm{5}! = \mathrm{120} \\
& \\
& \text{(b) The two youngest men are fixed at far-right.} \\
& \text{Arrange the } \mathrm{2} \text{ youngest men} = \mathrm{2}! = \mathrm{2} \\
& \text{Arrange the remaining } \mathrm{4} \text{ men} = \mathrm{4}! = \mathrm{24} \\
& \text{Total ways} = \mathrm{24} \times \mathrm{2} = \mathrm{48} \\
& \\
& \text{(c) Total arrangements of } \mathrm{6} \text{ men} = \mathrm{6}! = \mathrm{720} \\
& \text{Ways shortest man is at far-left} = \mathrm{5}! = \mathrm{120} \\
& \text{Ways shortest man is at far-right} = \mathrm{5}! = \mathrm{120} \\
& \text{Ways shortest man is at neither end} = \mathrm{720} - (\mathrm{120} + \mathrm{120}) = \mathrm{480} \\
\end{aligned} $$
Problem 9
Find how many permutations there are of:
a. five from seven distinct objects
b. four from nine distinct objects.
From \(\displaystyle \mathrm{12}\) books, how many ways are there to select and arrange exactly half of them in a row on a shelf?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Exactly half of } \mathrm{12} \text{ books is } \mathrm{6} \text{ books.} \\
& \text{Number of ways to select and arrange } \mathrm{6} \text{ from } \mathrm{12} = {}^{\mathrm{12}}\mathrm{P}_{\mathrm{6}} \\
& = \frac{\mathrm{12}!}{\mathrm{6}!} \\
& = \mathrm{12} \times \mathrm{11} \times \mathrm{10} \times \mathrm{9} \times \mathrm{8} \times \mathrm{7} = \mathrm{665280}
\end{aligned} $$
Problem 11
In how many ways can gold, silver and bronze medals be awarded for first, second and third places in a race between \(\displaystyle \mathrm{20}\) athletes? You may assume that no two athletes tie in these positions.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{We are selecting and ordering } \mathrm{3} \text{ athletes out of } \mathrm{20}. \\
& \text{Number of ways} = {}^{\mathrm{20}}\mathrm{P}_{\mathrm{3}} \\
& = \mathrm{20} \times \mathrm{19} \times \mathrm{18} = \mathrm{6840}
\end{aligned} $$
Problem 12
a. Find the number of ways in which Alvaro can paint his back door and his front door in a different colour if he has \(\displaystyle \mathrm{14}\) colours of paint to choose from.
b. In how many ways could Alvaro do this if he also considered painting them the same colour?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) If colours must be different:} \\
& \text{Options for 1st door} = \mathrm{14} \\
& \text{Options for 2nd door} = \mathrm{13} \\
& \text{Total ways} = \mathrm{14} \times \mathrm{13} = \mathrm{182} \\
& \\
& \text{(b) If colours can be the same:} \\
& \text{Options for 1st door} = \mathrm{14} \\
& \text{Options for 2nd door} = \mathrm{14} \\
& \text{Total ways} = \mathrm{14} \times \mathrm{14} = \mathrm{196}
\end{aligned} $$
Problem 13
Find the number of ways in which five apples can be selected from:
a. eight apples
b. nine apples and \(\displaystyle \mathrm{12}\) oranges.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) Select } \mathrm{5} \text{ apples from } \mathrm{8}: \\
& \text{Number of ways} = {}^{\mathrm{8}}\mathrm{C}_{\mathrm{5}} \\
& = \frac{\mathrm{8}!}{\mathrm{5}!\mathrm{3}!} \\
& = \mathrm{56} \\
& \\
& \text{(b) Select } \mathrm{5} \text{ apples from } \mathrm{9} \text{ apples and } \mathrm{12} \text{ oranges:} \\
& \text{Only apples are selected, so oranges are ignored.} \\
& \text{Number of ways} = {}^{\mathrm{9}}\mathrm{C}_{\mathrm{5}} \\
& = \frac{\mathrm{9}!}{\mathrm{5}!\mathrm{4}!} = \mathrm{126}
\end{aligned} $$
Problem 14
From seven men and eight women, find how many ways there are to select:
a. four men and five women
b. three men and six women
c. at least \(\displaystyle \mathrm{13}\) people.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) Select } \mathrm{4} \text{ men and } \mathrm{5} \text{ women:} \\
& \text{Number of ways} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{4}} \times {}^{\mathrm{8}}\mathrm{C}_{\mathrm{5}} \\
& = \mathrm{35} \times \mathrm{56} = \mathrm{1960} \\
& \\
& \text{(b) Select } \mathrm{3} \text{ men and } \mathrm{6} \text{ women:} \\
& \text{Number of ways} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{3}} \times {}^{\mathrm{8}}\mathrm{C}_{\mathrm{6}} \\
& = \mathrm{35} \times \mathrm{28} = \mathrm{980} \\
& \\
& \text{(c) Select at least } \mathrm{13} \text{ people from total } \mathrm{15} \text{ people:} \\
& \text{This means } \mathrm{13}, \mathrm{14}, \text{ or } \mathrm{15} \text{ people.} \\
& \text{Number of ways} = {}^{\mathrm{15}}\mathrm{C}_{\mathrm{13}} + {}^{\mathrm{15}}\mathrm{C}_{\mathrm{14}} + {}^{\mathrm{15}}\mathrm{C}_{\mathrm{15}} \\
& = \mathrm{105} + \mathrm{15} + \mathrm{1} = \mathrm{121}
\end{aligned} $$
Problem 15
a. How many different hands of five cards can be dealt from a standard deck of \(\displaystyle \mathrm{52}\) playing cards?
b. How many of the hands in part a consist of three of the \(\displaystyle \mathrm{26}\) red cards and two of the \(\displaystyle \mathrm{26}\) black cards?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) Select } \mathrm{5} \text{ cards from } \mathrm{52}: \\
& \text{Number of hands} = {}^{\mathrm{52}}\mathrm{C}_{\mathrm{5}} \\
& = \frac{\mathrm{52}!}{\mathrm{5}!\mathrm{47}!} \\
& = \mathrm{2598960} \\
& \\
& \text{(b) Select } \mathrm{3} \text{ from } \mathrm{26} \text{ red cards and } \mathrm{2} \text{ from } \mathrm{26} \text{ black cards:} \\
& \text{Number of hands} = {}^{\mathrm{26}}\mathrm{C}_{\mathrm{3}} \times {}^{\mathrm{26}}\mathrm{C}_{\mathrm{2}} \\
& = \mathrm{2600} \times \mathrm{325} = \mathrm{845000}
\end{aligned} $$
Problem 16
In a classroom there are four lights, each operated by a switch that has an on and an off position. How many possible lighting arrangements are there in the classroom?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{There are } \mathrm{4} \text{ switches in total.} \\
& \text{Each switch has } \mathrm{2} \text{ possible states (On or Off).} \\
& \text{Total possible arrangements} = \mathrm{2} \times \mathrm{2} \times \mathrm{2} \times \mathrm{2} \\
& = \mathrm{2}^{\mathrm{4}} \\
& = \mathrm{16}
\end{aligned} $$
Problem 17
The diagram opposite shows the activities offered to children at a school camp. If children must choose three activities to fill their day, how many sets of three activities are there to choose from? (Today's Activities -- Morning: acting, painting or singing; Afternoon: swimming, tennis, golf or cricket; Evening: night-hike, star-gazing or drumming. Afternoon swimming can be done at the pool or at the lake).
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Options for Morning} = \mathrm{3} \\
& \text{Options for Afternoon} = \mathrm{5} \text{ (Swimming counts as } \mathrm{2} \text{: pool or lake)} \\
& \text{Options for Evening} = \mathrm{3} \\
& \text{Total sets of activities} = \mathrm{3} \times \mathrm{5} \times \mathrm{3} = \mathrm{45}
\end{aligned} $$
Problem 18
Two taxis are hired to take a group of eight friends to the airport. One taxi can carry five passengers and the other can carry three passengers. What information is given in this situation by the fact that \(\displaystyle {}^{\mathrm{8}}\mathrm{C}_{\mathrm{5}} = {}^{\mathrm{8}}\mathrm{C}_{\mathrm{3}} = \mathrm{56}\)?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Choosing } \mathrm{5} \text{ friends from } \mathrm{8} \text{ for the first taxi automatically leaves exactly } \mathrm{3} \text{ friends for the second taxi.} \\
& \text{Therefore, the number of ways to choose the group for the } \mathrm{5}\text{-seater taxi} \\
& \text{is equal to the number of ways to choose the remaining group for the } \mathrm{3}\text{-seater taxi.} \\
& \text{This illustrates the symmetrical property of combinations: } {}^{\mathrm{n}}\mathrm{C}_{\mathrm{r}} = {}^{\mathrm{n}}\mathrm{C}_{\mathrm{n-r}}. \\
& \text{Hence, } {}^{\mathrm{8}}\mathrm{C}_{\mathrm{5}} = {}^{\mathrm{8}}\mathrm{C}_{\mathrm{3}} = \mathrm{56}.
\end{aligned} $$
Problem 19
How many positive integers, not exceeding $\displaystyle \mathrm{1000}$, are divisible by $\displaystyle \mathrm{7}$ or $\displaystyle \mathrm{11}$?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Let } \mathrm{A} \text{ be the set of integers divisible by } \mathrm{7}. \\
& \text{Let } \mathrm{B} \text{ be the set of integers divisible by } \mathrm{11}. \\
& \mathrm{n}(\mathrm{A}) = \left\lfloor \frac{\mathrm{1000}}{\mathrm{7}} \right\rfloor = \mathrm{142} \\
& \mathrm{n}(\mathrm{B}) = \left\lfloor \frac{\mathrm{1000}}{\mathrm{11}} \right\rfloor = \mathrm{90} \\
& \mathrm{n}(\mathrm{A} \cap \mathrm{B}) = \left\lfloor \frac{\mathrm{1000}}{\mathrm{77}} \right\rfloor = \mathrm{12} \\
& \mathrm{n}(\mathrm{A} \cup \mathrm{B}) = \mathrm{n}(\mathrm{A}) + \mathrm{n}(\mathrm{B}) - \mathrm{n}(\mathrm{A} \cap \mathrm{B}) \\
& = \mathrm{142} + \mathrm{90} - \mathrm{12} = \mathrm{220}
\end{aligned} $$
Problem 20
How many positive integers, not exceeding $\displaystyle \mathrm{1000}$, are divisible neither by $\displaystyle \mathrm{7}$ nor $\displaystyle \mathrm{11}$?
How many integers, in which each of the digits $\displaystyle \mathrm{8}$ and $\displaystyle \mathrm{9}$ appear exactly once, are there between $\displaystyle \mathrm{1}$ and $\displaystyle \mathrm{1000}$?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Any integer between } \mathrm{1} \text{ and } \mathrm{1000} \text{ can be represented as a } \mathrm{3}\text{-digit string (e.g., } \mathrm{89} \text{ is } \mathrm{089}\text{).} \\
& \text{We need exactly one } \mathrm{8} \text{ and exactly one } \mathrm{9}. \text{ The third digit } \mathrm{x} \text{ must be from } \{ \mathrm{0}, \mathrm{1}, \dots, \mathrm{7} \}. \\
& \text{Number of arrangements of positions for } \mathrm{8}, \mathrm{9}, \text{ and } \mathrm{x} = \mathrm{3}! = \mathrm{6} \\
& \text{Number of choices for digit } \mathrm{x} = \mathrm{8} \text{ (since it can be any digit from } \mathrm{0} \text{ to } \mathrm{7}\text{)} \\
& \text{Total number of integers} = \mathrm{6} \times \mathrm{8} = \mathrm{48}
\end{aligned} $$
Problem 22
How many odd four-digit numbers greater than $\displaystyle \mathrm{3000}$ can be made from the digits $\displaystyle \mathrm{1}, \mathrm{2}, \mathrm{3}$ and $\displaystyle \mathrm{4}$, each used once?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The digits are } \mathrm{1}, \mathrm{2}, \mathrm{3}, \mathrm{4}. \text{ The number must start with } \mathrm{3} \text{ or } \mathrm{4} \text{ and end with } \mathrm{1} \text{ or } \mathrm{3}. \\
& \text{Case 1: Starts with } \mathrm{3}. \text{ To be odd, it must end in } \mathrm{1}. \\
& \text{Remaining } \mathrm{2} \text{ digits (} \mathrm{2}, \mathrm{4} \text{) can be arranged in } \mathrm{2}! \text{ ways. Number of ways} = \mathrm{2}. \\
& \text{Case 2: Starts with } \mathrm{4}. \text{ It can end in } \mathrm{1} \text{ or } \mathrm{3} \text{ (} \mathrm{2} \text{ choices).} \\
& \text{Remaining } \mathrm{2} \text{ digits can be arranged in } \mathrm{2}! \text{ ways. Number of ways} = \mathrm{2} \times \mathrm{2} = \mathrm{4}. \\
& \text{Total numbers} = \mathrm{2} + \mathrm{4} = \mathrm{6}.
\end{aligned} $$
Problem 23
In how many ways can $\displaystyle \mathrm{4}$ out of $\displaystyle \mathrm{18}$ girls sit on a four-seat sofa when the oldest girl must be given one of the seats?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The oldest girl must be seated. She can be placed in any of the } \mathrm{4} \text{ seats.} \\
& \text{Number of ways to seat the oldest girl} = \mathrm{4} \\
& \text{The remaining } \mathrm{3} \text{ seats must be filled by } \mathrm{3} \text{ girls chosen from the remaining } \mathrm{17} \text{ girls.} \\
& \text{Number of ways to arrange the rest} = {}^{\mathrm{17}}\mathrm{P}_{\mathrm{3}} = \mathrm{17} \times \mathrm{16} \times \mathrm{15} = \mathrm{4080} \\
& \text{Total number of ways} = \mathrm{4} \times \mathrm{4080} = \mathrm{16320}
\end{aligned} $$
Problem 24
How many license plates, involving two letters in the English alphabet and three digits, are there if the letters must appear consecutively (but there is no other restriction)?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Since there is "no other restriction", repetition of letters and digits is allowed.} \\
& \text{The two letters must be consecutive, so we treat them as a block. The possible patterns are:} \\
& \text{LLDDD, DLLDD, DDLLD, DDDLL (Total } \mathrm{4} \text{ patterns).} \\
& \text{For each pattern, the } \mathrm{2} \text{ letters can be chosen in } \mathrm{26} \times \mathrm{26} = \mathrm{676} \text{ ways.} \\
& \text{The } \mathrm{3} \text{ digits can be chosen in } \mathrm{10} \times \mathrm{10} \times \mathrm{10} = \mathrm{1000} \text{ ways.} \\
& \text{Total number of license plates} = \mathrm{4} \times \mathrm{676} \times \mathrm{1000} = \mathrm{2704000}
\end{aligned} $$
Problem 25
Nine students, three of whom are from class A, three from class B and three from class C, are to be seated in a row of $\displaystyle \mathrm{9}$ seats. In how many ways can this be done if all the students of class A as well as all the students of class B occupy a block of three consecutive seats?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Treat the } \mathrm{3} \text{ students from Class A as a single block (Block A).} \\
& \text{Treat the } \mathrm{3} \text{ students from Class B as a single block (Block B).} \\
& \text{The } \mathrm{3} \text{ students from Class C are } \mathrm{3} \text{ individual units.} \\
& \text{Total units to arrange} = \mathrm{1} \text{ (Block A)} + \mathrm{1} \text{ (Block B)} + \mathrm{3} \text{ (Class C)} = \mathrm{5} \text{ units.} \\
& \text{Number of ways to arrange the } \mathrm{5} \text{ units} = \mathrm{5}! = \mathrm{120} \\
& \text{Number of ways to arrange students within Block A} = \mathrm{3}! = \mathrm{6} \\
& \text{Number of ways to arrange students within Block B} = \mathrm{3}! = \mathrm{6} \\
& \text{Total number of ways} = \mathrm{120} \times \mathrm{6} \times \mathrm{6} = \mathrm{4320}
\end{aligned} $$
Problem 26
In how many ways can the $\displaystyle \mathrm{10}$ diplomats be assigned to $\displaystyle \mathrm{5}$ embassies in order that each embassy gets $\displaystyle \mathrm{2}$ diplomats assigned to it?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{We choose } \mathrm{2} \text{ diplomats for the 1st embassy, } \mathrm{2} \text{ for the 2nd, etc.} \\
& \text{Since the embassies are distinct, we just multiply combinations.} \\
& \text{Number of ways} = {}^{\mathrm{10}}\mathrm{C}_{\mathrm{2}} \times {}^{\mathrm{8}}\mathrm{C}_{\mathrm{2}} \times {}^{\mathrm{6}}\mathrm{C}_{\mathrm{2}} \times {}^{\mathrm{4}}\mathrm{C}_{\mathrm{2}} \times {}^{\mathrm{2}}\mathrm{C}_{\mathrm{2}} \\
& = \frac{\mathrm{10}!}{\mathrm{2}!\mathrm{8}!} \times \frac{\mathrm{8}!}{\mathrm{2}!\mathrm{6}!} \times \frac{\mathrm{6}!}{\mathrm{2}!\mathrm{4}!} \times \frac{\mathrm{4}!}{\mathrm{2}!\mathrm{2}!} \times \mathrm{1} \\
& = \frac{\mathrm{10}!}{\mathrm{2}! \times \mathrm{2}! \times \mathrm{2}! \times \mathrm{2}! \times \mathrm{2}!} \\
& = \frac{\mathrm{3628800}}{\mathrm{32}} = \mathrm{113400}
\end{aligned} $$
Problem 27
From a group of four men and six women, how many ways are there to form a committee consisting of at least two men and exactly twice as many women as men?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Let } \mathrm{m} \text{ be the number of men. We need } \mathrm{m} \ge \mathrm{2} \text{ and Women } = \mathrm{2m}. \\
& \text{Case 1: } \mathrm{m} = \mathrm{2}. \text{ We need } \mathrm{2} \text{ men and } \mathrm{4} \text{ women.} \\
& \text{Ways} = {}^{\mathrm{4}}\mathrm{C}_{\mathrm{2}} \times {}^{\mathrm{6}}\mathrm{C}_{\mathrm{4}} = \mathrm{6} \times \mathrm{15} = \mathrm{90}. \\
& \text{Case 2: } \mathrm{m} = \mathrm{3}. \text{ We need } \mathrm{3} \text{ men and } \mathrm{6} \text{ women.} \\
& \text{Ways} = {}^{\mathrm{4}}\mathrm{C}_{\mathrm{3}} \times {}^{\mathrm{6}}\mathrm{C}_{\mathrm{6}} = \mathrm{4} \times \mathrm{1} = \mathrm{4}. \\
& \text{Case 3: } \mathrm{m} = \mathrm{4}. \text{ We need } \mathrm{8} \text{ women, which is impossible (only } \mathrm{6} \text{ available).} \\
& \text{Total number of ways} = \mathrm{90} + \mathrm{4} = \mathrm{94}.
\end{aligned} $$
Problem 28
There are $\displaystyle \mathrm{10}$ distinct white balls and $\displaystyle \mathrm{2}$ identical red balls in an urn. How many ways are there to select $\displaystyle \mathrm{5}$ balls and the order of selection does not matter?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Since the red balls are identical, choosing } \mathrm{1} \text{ or } \mathrm{2} \text{ red balls only has } \mathrm{1} \text{ way.} \\
& \text{Case 1: Select } \mathrm{0} \text{ red balls and } \mathrm{5} \text{ white balls.} \\
& \text{Ways} = \mathrm{1} \times {}^{\mathrm{10}}\mathrm{C}_{\mathrm{5}} = \mathrm{252}. \\
& \text{Case 2: Select } \mathrm{1} \text{ red ball and } \mathrm{4} \text{ white balls.} \\
& \text{Ways} = \mathrm{1} \times {}^{\mathrm{10}}\mathrm{C}_{\mathrm{4}} = \mathrm{210}. \\
& \text{Case 3: Select } \mathrm{2} \text{ red balls and } \mathrm{3} \text{ white balls.} \\
& \text{Ways} = \mathrm{1} \times {}^{\mathrm{10}}\mathrm{C}_{\mathrm{3}} = \mathrm{120}. \\
& \text{Total number of ways} = \mathrm{252} + \mathrm{210} + \mathrm{120} = \mathrm{582}.
\end{aligned} $$
Problem 29
There are $\displaystyle \mathrm{15}$ distinct apples and $\displaystyle \mathrm{10}$ distinct pears in a pile of fruit. Ko Ko has to pick one fruit (an apple or a pear) from the pile and take away, and then Nyi Nyi is to pick an apple and a pear from the remaining. How many ways are there to do this?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Case 1: Ko Ko picks an Apple.} \\
& \text{Ko Ko's ways} = \mathrm{15}. \text{ Remaining: } \mathrm{14} \text{ Apples, } \mathrm{10} \text{ Pears.} \\
& \text{Nyi Nyi picks } \mathrm{1} \text{ Apple and } \mathrm{1} \text{ Pear from remaining} = \mathrm{14} \times \mathrm{10} = \mathrm{140} \text{ ways.} \\
& \text{Total for Case 1} = \mathrm{15} \times \mathrm{140} = \mathrm{2100}. \\
& \text{Case 2: Ko Ko picks a Pear.} \\
& \text{Ko Ko's ways} = \mathrm{10}. \text{ Remaining: } \mathrm{15} \text{ Apples, } \mathrm{9} \text{ Pears.} \\
& \text{Nyi Nyi picks } \mathrm{1} \text{ Apple and } \mathrm{1} \text{ Pear from remaining} = \mathrm{15} \times \mathrm{9} = \mathrm{135} \text{ ways.} \\
& \text{Total for Case 2} = \mathrm{10} \times \mathrm{135} = \mathrm{1350}. \\
& \text{Overall total number of ways} = \mathrm{2100} + \mathrm{1350} = \mathrm{3450}.
\end{aligned} $$
Problem 30
Find how many of the arrangements of four letters from A, B, C, D, E and F:
a. begin with the letter A
b. contain the letter A.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) The first position is fixed as } \mathrm{A}. \text{ We need to arrange } \mathrm{3} \text{ more letters from the remaining } \mathrm{5}. \\
& \text{Number of arrangements} = {}^{\mathrm{5}}\mathrm{P}_{\mathrm{3}} = \mathrm{5} \times \mathrm{4} \times \mathrm{3} = \mathrm{60}. \\
& \\
& \text{(b) The group must contain } \mathrm{A}. \text{ First, choose the other } \mathrm{3} \text{ letters from the remaining } \mathrm{5}. \\
& \text{Ways to choose the other letters} = {}^{\mathrm{5}}\mathrm{C}_{\mathrm{3}} = \mathrm{10}. \\
& \text{For each group of } \mathrm{4} \text{ chosen letters, there are } \mathrm{4}! \text{ arrangements.} \\
& \text{Total number of arrangements} = \mathrm{10} \times \mathrm{4}! = \mathrm{10} \times \mathrm{24} = \mathrm{240}.
\end{aligned} $$
Problem 31
From a group of $\displaystyle \mathrm{10}$ boys and seven girls, two are to be chosen to act as the hero and the villain in the school play. Find in how many ways this can be done if these two roles are to be played by:
a. any of the children
b. two girls or two boys
c. a boy and a girl.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The roles of hero and villain are distinct, so order of selection matters (Permutations).} \\
& \text{(a) Any of the } \mathrm{17} \text{ children for } \mathrm{2} \text{ roles:} \\
& \text{Ways} = {}^{\mathrm{17}}\mathrm{P}_{\mathrm{2}} = \mathrm{17} \times \mathrm{16} = \mathrm{272}. \\
& \\
& \text{(b) Two girls or two boys:} \\
& \text{Both Girls} = {}^{\mathrm{7}}\mathrm{P}_{\mathrm{2}} = \mathrm{7} \times \mathrm{6} = \mathrm{42}. \\
& \text{Both Boys} = {}^{\mathrm{10}}\mathrm{P}_{\mathrm{2}} = \mathrm{10} \times \mathrm{9} = \mathrm{90}. \\
& \text{Total Ways} = \mathrm{42} + \mathrm{90} = \mathrm{132}. \\
& \\
& \text{(c) A boy and a girl:} \\
& \text{Boy as Hero, Girl as Villain} = \mathrm{10} \times \mathrm{7} = \mathrm{70}. \\
& \text{Girl as Hero, Boy as Villain} = \mathrm{7} \times \mathrm{10} = \mathrm{70}. \\
& \text{Total Ways} = \mathrm{70} + \mathrm{70} = \mathrm{140}.
\end{aligned} $$
Problem 32
Using each digit not more than once, how many even four-digit numbers can be made from the digits $\displaystyle \mathrm{1}, \mathrm{2}, \mathrm{3}, \mathrm{4}, \mathrm{5}, \mathrm{6}$ and $\displaystyle \mathrm{7}$?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{To form an even number, the last digit must be even. Available even digits: } \mathrm{2}, \mathrm{4}, \mathrm{6}. \\
& \text{Number of choices for the last digit} = \mathrm{3}. \\
& \text{After choosing the last digit, we have } \mathrm{6} \text{ digits left to fill the remaining } \mathrm{3} \text{ positions.} \\
& \text{Number of ways to fill the first three positions} = {}^{\mathrm{6}}\mathrm{P}_{\mathrm{3}} = \mathrm{6} \times \mathrm{5} \times \mathrm{4} = \mathrm{120}. \\
& \text{Total even four-digit numbers} = \mathrm{3} \times \mathrm{120} = \mathrm{360}.
\end{aligned} $$
Problem 33
Find how many three-digit numbers can be made from the digits $\displaystyle \mathrm{0}, \mathrm{1}, \mathrm{2}, \mathrm{3}$ and $\displaystyle \mathrm{4}$, used at most once each, if the three-digit number:
a. must be a multiple of $\displaystyle \mathrm{10}$
b. cannot begin with zero.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{(a) To be a multiple of } \mathrm{10}, \text{ the number must end with } \mathrm{0}. \\
& \text{The last digit is fixed as } \mathrm{0} \text{ (1 choice).} \\
& \text{The first two digits are chosen from the remaining } \mathrm{4} \text{ digits (} \mathrm{1}, \mathrm{2}, \mathrm{3}, \mathrm{4} \text{).} \\
& \text{Ways} = {}^{\mathrm{4}}\mathrm{P}_{\mathrm{2}} = \mathrm{4} \times \mathrm{3} = \mathrm{12}. \\
& \\
& \text{(b) The number cannot begin with zero.} \\
& \text{Choices for the first digit} = \mathrm{4} \text{ (from } \mathrm{1}, \mathrm{2}, \mathrm{3}, \mathrm{4} \text{).} \\
& \text{Choices for the second digit} = \mathrm{4} \text{ (remaining } \mathrm{3} \text{ plus } \mathrm{0} \text{).} \\
& \text{Choices for the third digit} = \mathrm{3}. \\
& \text{Total numbers} = \mathrm{4} \times \mathrm{4} \times \mathrm{3} = \mathrm{48}.
\end{aligned} $$
Problem 34
Give an example of a practical situation where the calculation $\displaystyle {}^{\mathrm{n}} \mathrm{P}_{\mathrm{r}} = \mathrm{120}$ might arise.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{We know that } {}^{\mathrm{6}}\mathrm{P}_{\mathrm{3}} = \mathrm{6} \times \mathrm{5} \times \mathrm{4} = \mathrm{120}. \\
& \text{An example of a practical situation is:} \\
& \text{"Finding the number of different ways to award Gold, Silver, and Bronze medals} \\
& \text{to the top } \mathrm{3} \text{ finishers in a race consisting of } \mathrm{6} \text{ athletes."} \\
& \text{(Alternatively, } {}^{\mathrm{5}}\mathrm{P}_{\mathrm{4}} = \mathrm{120} \text{ or } {}^{\mathrm{5}}\mathrm{P}_{\mathrm{5}} = \mathrm{120} \text{ could also be used).}
\end{aligned} $$
Problem 35
Five playing cards are randomly selected from a standard deck of $\displaystyle \mathrm{52}$ cards. These five cards are shuffled, and then the top three cards are placed in a row on a table. How many different arrangements of three of the $\displaystyle \mathrm{52}$ cards are possible?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Although } \mathrm{5} \text{ cards are drawn first, ultimately we are just choosing and arranging } \mathrm{3} \text{ cards} \\
& \text{out of the original } \mathrm{52} \text{ cards. The intermediate step of drawing } \mathrm{5} \text{ does not limit} \\
& \text{which } \mathrm{3} \text{ cards can be selected, as any } \mathrm{3} \text{ cards from the } \mathrm{52} \text{ could end up as the top } \mathrm{3}. \\
& \text{Number of arrangements} = {}^{\mathrm{52}}\mathrm{P}_{\mathrm{3}} \\
& = \mathrm{52} \times \mathrm{51} \times \mathrm{50} = \mathrm{132600}
\end{aligned} $$
Problem 36
From six boys and seven girls, find how many ways there are to select a group of three children that consists of more girls than boys.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{For a group of } \mathrm{3} \text{ children to have more girls than boys, the possibilities are:} \\
& \text{Case 1: } \mathrm{2} \text{ girls and } \mathrm{1} \text{ boy.} \\
& \text{Ways} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{2}} \times {}^{\mathrm{6}}\mathrm{C}_{\mathrm{1}} = \mathrm{21} \times \mathrm{6} = \mathrm{126}. \\
& \text{Case 2: } \mathrm{3} \text{ girls and } \mathrm{0} \text{ boys.} \\
& \text{Ways} = {}^{\mathrm{7}}\mathrm{C}_{\mathrm{3}} \times {}^{\mathrm{6}}\mathrm{C}_{\mathrm{0}} = \mathrm{35} \times \mathrm{1} = \mathrm{35}. \\
& \text{Total number of ways} = \mathrm{126} + \mathrm{35} = \mathrm{161}.
\end{aligned} $$
Problem 37
A bag contains six red fuses, five blue fuses and four yellow fuses. Find how many ways there are to select:
a. three fuses of different colours
b. three fuses of the same colour
c. $\displaystyle \mathrm{10}$ fuses in exactly two colours
d. nine fuses in exactly two colours.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Assuming all fuses are distinct objects (i.e., distinguishable from one another):} \\
& \text{(a) Select } \mathrm{3} \text{ of different colours (1R, 1B, 1Y):} \\
& \text{Ways} = {}^{\mathrm{6}}\mathrm{C}_{\mathrm{1}} \times {}^{\mathrm{5}}\mathrm{C}_{\mathrm{1}} \times {}^{\mathrm{4}}\mathrm{C}_{\mathrm{1}} = \mathrm{6} \times \mathrm{5} \times \mathrm{4} = \mathrm{120}. \\
& \\
& \text{(b) Select } \mathrm{3} \text{ of the same colour (3R or 3B or 3Y):} \\
& \text{Ways} = {}^{\mathrm{6}}\mathrm{C}_{\mathrm{3}} + {}^{\mathrm{5}}\mathrm{C}_{\mathrm{3}} + {}^{\mathrm{4}}\mathrm{C}_{\mathrm{3}} = \mathrm{20} + \mathrm{10} + \mathrm{4} = \mathrm{34}. \\
& \\
& \textbf{Note on overcounting for (c) and (d):} \\
& \text{To have "exactly two colours", the selection must not be a single colour.} \\
& \text{Since the maximum number of fuses for any single colour is } \mathrm{6} \text{ (Red),} \\
& \text{any selection of } \mathrm{9} \text{ or } \mathrm{10} \text{ fuses from two given colours MUST contain BOTH colours.} \\
& \text{Therefore, there are NO single-colour selections to subtract, and NO overlaps between pairs.} \\
& \\
& \text{(c) } \mathrm{10} \text{ fuses in exactly two colours:} \\
& \text{Red and Blue (Total } \mathrm{11} \text{ available): Ways} = {}^{\mathrm{11}}\mathrm{C}_{\mathrm{10}} = \mathrm{11}. \\
& \text{Red and Yellow (Total } \mathrm{10} \text{ available): Ways} = {}^{\mathrm{10}}\mathrm{C}_{\mathrm{10}} = \mathrm{1}. \\
& \text{Blue and Yellow (Total } \mathrm{9} \text{ available): Impossible to select } \mathrm{10}. \\
& \text{Total Ways} = \mathrm{11} + \mathrm{1} = \mathrm{12}. \\
& \\
& \text{(d) } \mathrm{9} \text{ fuses in exactly two colours:} \\
& \text{Red and Blue (Total } \mathrm{11} \text{ available): Ways} = {}^{\mathrm{11}}\mathrm{C}_{\mathrm{9}} = \mathrm{55}. \\
& \text{Red and Yellow (Total } \mathrm{10} \text{ available): Ways} = {}^{\mathrm{10}}\mathrm{C}_{\mathrm{9}} = \mathrm{10}. \\
& \text{Blue and Yellow (Total } \mathrm{9} \text{ available): Ways} = {}^{\mathrm{9}}\mathrm{C}_{\mathrm{9}} = \mathrm{1}. \\
& \text{Total Ways} = \mathrm{55} + \mathrm{10} + \mathrm{1} = \mathrm{66}.
\end{aligned} $$
Problem 38
A boy has eight pairs of trousers, seven shirts and six jackets. In how many ways can he dress in trousers, shirt and jacket if he refuses to wear a particular pair of red trousers with a particular red shirt?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Total number of ways without restriction} = \mathrm{8} \times \mathrm{7} \times \mathrm{6} = \mathrm{336}. \\
& \text{Number of ways he wears BOTH the specific red trousers and red shirt:} \\
& \text{Trousers (1 specific) } \times \text{ Shirt (1 specific) } \times \text{ Jackets (any of } \mathrm{6}\text{)} = \mathrm{1} \times \mathrm{1} \times \mathrm{6} = \mathrm{6}. \\
& \text{Number of allowed ways} = \text{Total ways} - \text{Restricted ways} \\
& = \mathrm{336} - \mathrm{6} \\
& = \mathrm{330}.
\end{aligned} $$
Problem 39
A girl has $\displaystyle \mathrm{11}$ objects to arrange on a shelf but there is room for only seven of them. In how many ways can she arrange seven of the objects in a row along the shelf, if her clock must be included?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The shelf has } \mathrm{7} \text{ positions. The clock must be placed in one of these positions.} \\
& \text{Number of choices for the position of the clock} = \mathrm{7}. \\
& \text{There are } \mathrm{6} \text{ positions left to be filled by } \mathrm{6} \text{ objects chosen from the remaining } \mathrm{10} \text{ objects.} \\
& \text{Number of ways to arrange the remaining objects} = {}^{\mathrm{10}}\mathrm{P}_{\mathrm{6}} \\
& = \mathrm{10} \times \mathrm{9} \times \mathrm{8} \times \mathrm{7} \times \mathrm{6} \times \mathrm{5} = \mathrm{151200}. \\
& \text{Total number of arrangements} = \mathrm{7} \times \mathrm{151200} = \mathrm{1058400}.
\end{aligned} $$
Problem 40
A Mathematics teacher has $\displaystyle \mathrm{10}$ different posters to pin up in their classroom but there is enough space for only five of them. They have three posters on algebra, two on calculus and five on trigonometry. In how many ways can they choose the five posters to pin up if:
a. there are no restrictions
b. they decide not to pin up either of the calculus posters
c. they decide to pin up at least one poster on each of the three topics algebra, calculus and trigonometry?
As discussed at the beginning of this chapter in Explore 5.1 about encrypting letters, it states that there are over $\displaystyle \mathrm{27}$ million possibilities for the password encrypted as UJSNOL. How many possibilities are there?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The ciphertext "UJSNOL" consists of } \mathrm{6} \text{ distinct letters.} \\
& \text{Under a simple substitution cipher, distinct letters map to distinct original letters.} \\
& \text{To form a password, we are choosing and arranging } \mathrm{6} \text{ distinct letters} \\
& \text{from the } \mathrm{26} \text{ letters of the English alphabet.} \\
& \text{Total number of possibilities} = {}^{\mathrm{26}}\mathrm{P}_{\mathrm{6}} \\
& = \mathrm{26} \times \mathrm{25} \times \mathrm{24} \times \mathrm{23} \times \mathrm{22} \times \mathrm{21} \\
& = \mathrm{165765600} \text{ (which is well over } \mathrm{27} \text{ million).}
\end{aligned} $$
Problem 42
How many distinct three-digit numbers can be made from $\displaystyle \mathrm{1}, \mathrm{2}, \mathrm{2}, \mathrm{3}, \mathrm{4}$ and $\displaystyle \mathrm{5}$, using each at most once?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The given digits are } \mathrm{1}, \mathrm{2}, \mathrm{2}, \mathrm{3}, \mathrm{4}, \mathrm{5}. \\
& \text{Case 1: The number contains NO repeated digits.} \\
& \text{We choose and arrange } \mathrm{3} \text{ distinct digits from } \{ \mathrm{1}, \mathrm{2}, \mathrm{3}, \mathrm{4}, \mathrm{5} \}. \\
& \text{Ways} = {}^{\mathrm{5}}\mathrm{P}_{\mathrm{3}} = \mathrm{60}. \\
& \\
& \text{Case 2: The number contains EXACTLY two } \mathrm{2}\text{s.} \\
& \text{The digits are } \mathrm{2}, \mathrm{2}, \mathrm{x}, \text{ where } \mathrm{x} \in \{ \mathrm{1}, \mathrm{3}, \mathrm{4}, \mathrm{5} \} \text{ (} \mathrm{4} \text{ choices for x).} \\
& \text{For each choice, the arrangements are } \frac{\mathrm{3}!}{\mathrm{2}!} = \mathrm{3} \text{ ways.} \\
& \text{Ways} = \mathrm{4} \times \mathrm{3} = \mathrm{12}. \\
& \\
& \text{Total distinct three-digit numbers} = \mathrm{60} + \mathrm{12} = \mathrm{72}.
\end{aligned} $$
Problem 43
In how many ways can $\displaystyle \mathrm{10}$ identical objects be distributed into $\displaystyle \mathrm{10}$ distinct boxes such that exactly (any) one box is empty?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{We have } \mathrm{10} \text{ identical objects and } \mathrm{10} \text{ distinct boxes.} \\
& \text{If exactly one box is empty, the remaining } \mathrm{9} \text{ boxes must contain all } \mathrm{10} \text{ objects.} \\
& \text{Since none of these } \mathrm{9} \text{ boxes can be empty, we must place at least } \mathrm{1} \text{ object in each of them.} \\
& \text{Giving } \mathrm{1} \text{ object to each of the } \mathrm{9} \text{ boxes uses } \mathrm{9} \text{ objects.} \\
& \text{There is } \mathrm{1} \text{ object left, which must be placed in one of the } \mathrm{9} \text{ chosen boxes.} \\
& \text{Thus, } \mathrm{1} \text{ box will have } \mathrm{2} \text{ objects, } \mathrm{8} \text{ boxes will have } \mathrm{1} \text{ object, and } \mathrm{1} \text{ box will be empty.} \\
& \text{Number of ways to choose the empty box} = \mathrm{10}. \\
& \text{Number of ways to choose the box with } \mathrm{2} \text{ objects from the remaining } \mathrm{9} \text{ boxes} = \mathrm{9}. \\
& \text{Total number of ways} = \mathrm{10} \times \mathrm{9} = \mathrm{90}.
\end{aligned} $$
Problem 44
There are four different roads from town A to town B, three different roads from town B to town C, two different roads from town A to town C. How many different ways are there to go from A to C and then return to A, if B must be visited at least once on the whole trip?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Assuming roads can be travelled in both directions and can be reused on the return trip:} \\
& \text{Number of routes from } \mathrm{A} \text{ to } \mathrm{C} \text{ via } \mathrm{B} = \mathrm{4} \times \mathrm{3} = \mathrm{12}. \\
& \text{Number of direct routes from } \mathrm{A} \text{ to } \mathrm{C} = \mathrm{2}. \\
& \text{Total routes from } \mathrm{A} \text{ to } \mathrm{C} = \mathrm{12} + \mathrm{2} = \mathrm{14}. \\
& \text{Similarly, total return routes from } \mathrm{C} \text{ to } \mathrm{A} = \mathrm{14}. \\
& \text{Total number of round trips without restriction} = \mathrm{14} \times \mathrm{14} = \mathrm{196}. \\
& \text{Number of round trips that NEVER visit } \mathrm{B} = (\text{Direct } \mathrm{A} \to \mathrm{C}) \times (\text{Direct } \mathrm{C} \to \mathrm{A}) = \mathrm{2} \times \mathrm{2} = \mathrm{4}. \\
& \text{Number of ways where } \mathrm{B} \text{ is visited at least once} = \text{Total} - \text{Never visit } \mathrm{B} \\
& = \mathrm{196} - \mathrm{4} = \mathrm{192}.
\end{aligned} $$
Problem 45
How many five-digit natural numbers, containing digit $\displaystyle \mathrm{3}$ exactly once, are there?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{A five-digit number cannot begin with } \mathrm{0}. \\
& \text{Case 1: The first digit is } \mathrm{3}. \\
& \text{The remaining } \mathrm{4} \text{ digits must be chosen from the } \mathrm{9} \text{ other digits (excluding } \mathrm{3}\text{).} \\
& \text{Number of ways} = \mathrm{1} \times \mathrm{9}^{\mathrm{4}} = \mathrm{6561}. \\
& \\
& \text{Case 2: The first digit is NOT } \mathrm{3}. \\
& \text{The first digit must not be } \mathrm{0} \text{ or } \mathrm{3} \text{ (} \mathrm{8} \text{ choices).} \\
& \text{The single digit } \mathrm{3} \text{ can be placed in any of the remaining } \mathrm{4} \text{ positions (} \mathrm{4} \text{ choices).} \\
& \text{The other } \mathrm{3} \text{ positions are filled with any of the } \mathrm{9} \text{ digits (excluding } \mathrm{3}\text{).} \\
& \text{Number of ways} = \mathrm{8} \times \mathrm{4} \times \mathrm{9}^{\mathrm{3}} = \mathrm{32} \times \mathrm{729} = \mathrm{23328}. \\
& \\
& \text{Total numbers} = \mathrm{6561} + \mathrm{23328} = \mathrm{29889}.
\end{aligned} $$
Problem 46
Consider arrangements of all the letters in the word INSTITUTIONAL. In how many these arrangements do the vowels appear in alphabetical order (but these vowels may or may not be consecutive)?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{The word INSTITUTIONAL has } \mathrm{13} \text{ letters.} \\
& \text{Vowels (6): I, I, I, U, O, A. (Alphabetical order: A, I, I, I, O, U).} \\
& \text{Consonants (7): N, S, T, T, T, N, L. (Contains 2 N's, 3 T's, 1 S, 1 L).} \\
& \text{Choose } \mathrm{6} \text{ positions out of } \mathrm{13} \text{ for the vowels.} \\
& \text{Number of ways to choose positions} = {}^{\mathrm{13}}\mathrm{C}_{\mathrm{6}} = \mathrm{1716}. \\
& \text{Since the vowels must appear in alphabetical order, there is only } \mathrm{1} \text{ way to place them in the chosen positions.} \\
& \text{The remaining } \mathrm{7} \text{ positions are filled by the } \mathrm{7} \text{ consonants.} \\
& \text{Number of ways to arrange the consonants} = \frac{\mathrm{7}!}{\mathrm{2}!\mathrm{3}!\mathrm{1}!\mathrm{1}!} = \frac{\mathrm{5040}}{\mathrm{12}} = \mathrm{420}. \\
& \text{Total number of valid arrangements} = \mathrm{1716} \times \mathrm{420} = \mathrm{720720}.
\end{aligned} $$
Problem 47
How many ways are there to make $\displaystyle \mathrm{10}$-letter words using the letters a, b, c, d if each letter must appear at least twice but no more than four times?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Let } \mathrm{x_a, x_b, x_c, x_d} \text{ be the frequencies of letters a, b, c, d.} \\
& \text{We require } \mathrm{x_a + x_b + x_c + x_d = 10} \text{ with } \mathrm{2} \le \mathrm{x_i} \le \mathrm{4}. \\
& \text{The possible multisets of frequencies are } \{\mathrm{4}, \mathrm{2}, \mathrm{2}, \mathrm{2}\} \text{ and } \{\mathrm{3}, \mathrm{3}, \mathrm{2}, \mathrm{2}\}. \\
& \\
& \text{Case 1: Frequencies } \{\mathrm{4}, \mathrm{2}, \mathrm{2}, \mathrm{2}\} \\
& \text{Ways to assign these frequencies to a,b,c,d} = \frac{\mathrm{4}!}{\mathrm{3}!} = \mathrm{4}. \\
& \text{For each assignment, permutations of the } \mathrm{10} \text{ letters} = \frac{\mathrm{10}!}{\mathrm{4}!\mathrm{2}!\mathrm{2}!\mathrm{2}!} = \mathrm{18900}. \\
& \text{Ways for Case 1} = \mathrm{4} \times \mathrm{18900} = \mathrm{75600}. \\
& \\
& \text{Case 2: Frequencies } \{\mathrm{3}, \mathrm{3}, \mathrm{2}, \mathrm{2}\} \\
& \text{Ways to assign these frequencies to a,b,c,d} = \frac{\mathrm{4}!}{\mathrm{2}!\mathrm{2}!} = \mathrm{6}. \\
& \text{For each assignment, permutations of the } \mathrm{10} \text{ letters} = \frac{\mathrm{10}!}{\mathrm{3}!\mathrm{3}!\mathrm{2}!\mathrm{2}!} = \mathrm{25200}. \\
& \text{Ways for Case 2} = \mathrm{6} \times \mathrm{25200} = \mathrm{151200}. \\
& \\
& \text{Total } \mathrm{10}\text{-letter words} = \mathrm{75600} + \mathrm{151200} = \mathrm{226800}.
\end{aligned} $$
Problem 48
How many $\displaystyle \mathrm{5}$-digit codes can be formed using the digits $\displaystyle \mathrm{0}, \mathrm{1}, \mathrm{2}, \ldots, \mathrm{9}$, with the property that exactly two of the ten digits appear in the codes (for example $\displaystyle \mathrm{05550}$ is such a code)?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Since these are codes, they can start with any digit including } \mathrm{0}. \\
& \text{First, choose the } \mathrm{2} \text{ distinct digits from the } \mathrm{10} \text{ available digits.} \\
& \text{Number of ways to choose } \mathrm{2} \text{ digits} = {}^{\mathrm{10}}\mathrm{C}_{\mathrm{2}} = \mathrm{45}. \\
& \text{Now, using ONLY these } \mathrm{2} \text{ digits, we form } \mathrm{5}\text{-digit codes.} \\
& \text{There are } \mathrm{2}^{\mathrm{5}} = \mathrm{32} \text{ possible combinations.} \\
& \text{However, we must subtract the } \mathrm{2} \text{ cases where only ONE digit is used (e.g., all 0s or all 5s),} \\
& \text{because exactly TWO digits must appear.} \\
& \text{Number of valid arrangements for the chosen pair} = \mathrm{32} - \mathrm{2} = \mathrm{30}. \\
& \text{Total number of codes} = \mathrm{45} \times \mathrm{30} = \mathrm{1350}.
\end{aligned} $$
Problem 49
From a set of $\displaystyle \mathrm{10}$ rings, a jeweller wishes to display seven of them in their shop window. The formation of the display is shown in the diagram below.
Find the number of possible displays if, from the set of $\displaystyle \mathrm{10}$:
a. the ring with the largest diamond must go at the top of the display
b. the most expensive ring must go at the top with the two least expensive rings adjacent to it.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Based on the referenced diagram, we assume a specific layout of } \mathrm{7} \text{ display positions:} \\
& \mathrm{1} \text{ "top" position, } \mathrm{2} \text{ positions directly "adjacent" to the top, and } \mathrm{4} \text{ "other" positions.} \\
& \\
& \text{(a) The ring with the largest diamond is fixed at the top (1 way).} \\
& \text{The remaining } \mathrm{6} \text{ positions are filled by } \mathrm{6} \text{ rings chosen from the remaining } \mathrm{9} \text{ rings.} \\
& \text{Number of ways} = {}^{\mathrm{9}}\mathrm{P}_{\mathrm{6}} = \mathrm{9} \times \mathrm{8} \times \mathrm{7} \times \mathrm{6} \times \mathrm{5} \times \mathrm{4} = \mathrm{60480}. \\
& \\
& \text{(b) The most expensive ring is fixed at the top (1 way).} \\
& \text{The } \mathrm{2} \text{ least expensive rings occupy the } \mathrm{2} \text{ adjacent positions.} \\
& \text{Number of ways to arrange these } \mathrm{2} \text{ rings} = \mathrm{2}! = \mathrm{2}. \\
& \text{The remaining } \mathrm{4} \text{ positions are filled by the remaining } \mathrm{7} \text{ rings.} \\
& \text{Number of ways to arrange the rest} = {}^{\mathrm{7}}\mathrm{P}_{\mathrm{4}} = \mathrm{7} \times \mathrm{6} \times \mathrm{5} \times \mathrm{4} = \mathrm{840}. \\
& \text{Total number of ways} = \mathrm{1} \times \mathrm{2} \times \mathrm{840} = \mathrm{1680}.
\end{aligned} $$
Problem 50
a. Under what condition is $\displaystyle {}^{\mathrm{n}} \mathrm{P}_{\mathrm{r}} > {}^{\mathrm{n}} \mathrm{P}_{\mathrm{n-r}}$?
b. Given that $\displaystyle {}^{\mathrm{n}} \mathrm{P}_{\mathrm{r}} \times {}^{\mathrm{n}} \mathrm{P}_{\mathrm{n-r}} = \mathrm{k} \times {}^{\mathrm{n}} \mathrm{P}_{\mathrm{n}}$, find an expression for $\displaystyle \mathrm{k}$ in terms of $\displaystyle \mathrm{n}$ and $\displaystyle \mathrm{r}$.
In how many ways can the chairs be occupied by $\displaystyle \mathrm{7}$ of a group of $\displaystyle \mathrm{12}$ people if three particular people are asked to sit on chairs B, D and F, in any order?
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Chairs } \mathrm{B}, \mathrm{D}, \text{ and } \mathrm{F} \text{ are reserved for } \mathrm{3} \text{ specific people.} \\
& \text{Number of ways these } \mathrm{3} \text{ people can arrange themselves on these } \mathrm{3} \text{ chairs} = \mathrm{3}! = \mathrm{6}. \\
& \text{There are } \mathrm{4} \text{ chairs left (A, C, E, G) and } \mathrm{12} - \mathrm{3} = \mathrm{9} \text{ people remaining.} \\
& \text{Number of ways to fill the } \mathrm{4} \text{ remaining chairs with } \mathrm{4} \text{ of the } \mathrm{9} \text{ people} = {}^{\mathrm{9}}\mathrm{P}_{\mathrm{4}} \\
& = \mathrm{9} \times \mathrm{8} \times \mathrm{7} \times \mathrm{6} = \mathrm{3024}. \\
& \text{Total number of ways} = \mathrm{6} \times \mathrm{3024} = \mathrm{18144}.
\end{aligned} $$
Problem 52
A minibus has $\displaystyle \mathrm{11}$ passenger seats. There are six seats in a row on the sunny side and five seats in a row on the shady side, as shown in the following diagram.
Find how many ways eight passengers can be arranged in these seats if:
a. there are no restrictions
b. one particular passenger refuses to sit on the sunny side
c. two particular passengers refuse to sit in seats that are either next to each other or one directly in front of the other.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Total seats = } \mathrm{11} \text{ (6 Sunny + 5 Shady). Passengers = } \mathrm{8}. \\
& \text{(a) No restrictions:} \\
& \text{Ways to arrange } \mathrm{8} \text{ passengers in } \mathrm{11} \text{ seats} = {}^{\mathrm{11}}\mathrm{P}_{\mathrm{8}} = \mathrm{6652800}. \\
& \\
& \text{(b) One particular passenger must sit on the Shady side.} \\
& \text{Ways to seat this passenger on Shady side (5 seats)} = \mathrm{5}. \\
& \text{Remaining } \mathrm{7} \text{ passengers are arranged in the remaining } \mathrm{10} \text{ seats.} \\
& \text{Ways} = \mathrm{5} \times {}^{\mathrm{10}}\mathrm{P}_{\mathrm{7}} = \mathrm{5} \times \mathrm{604800} = \mathrm{3024000}. \\
& \\
& \text{(c) Two particular passengers (A and B) refuse to sit next to each other or directly in front of each other.} \\
& \text{Assuming the } \mathrm{5} \text{ shady seats align directly with } \mathrm{5} \text{ of the } \mathrm{6} \text{ sunny seats across the aisle:} \\
& \text{This layout creates exactly } \mathrm{5} \text{ "directly in front" pairs across the aisle.} \\
& \text{Adjacent pairs in the same row} = (\mathrm{6}-\mathrm{1}) + (\mathrm{5}-\mathrm{1}) = \mathrm{5} + \mathrm{4} = \mathrm{9} \text{ pairs.} \\
& \text{Total restricted pairs} = \mathrm{9} + \mathrm{5} = \mathrm{14}. \\
& \text{Ways A and B can sit in a restricted pair} = \mathrm{14} \times \mathrm{2}! = \mathrm{28}. \\
& \text{Total ways to seat A and B without restriction} = {}^{\mathrm{11}}\mathrm{P}_{\mathrm{2}} = \mathrm{110}. \\
& \text{Allowed ways for A and B} = \mathrm{110} - \mathrm{28} = \mathrm{82}. \\
& \text{For each allowed placement of A and B, place the remaining } \mathrm{6} \text{ passengers in } \mathrm{9} \text{ seats.} \\
& \text{Total ways} = \mathrm{82} \times {}^{\mathrm{9}}\mathrm{P}_{\mathrm{6}} = \mathrm{82} \times \mathrm{60480} = \mathrm{4959360}.
\end{aligned} $$
Problem 53
Ten cars are to be parked in a car park that has $\displaystyle \mathrm{20}$ parking spaces set out in two rows of $\displaystyle \mathrm{10}$. Find how many different patterns of unoccupied parking spaces are possible if:
a. the cars can be parked in any of the $\displaystyle \mathrm{20}$ spaces
b. the cars are parked in the same row
c. the same number of cars are parked in each row
d. two more cars are parked in one row than in the other.
Show Solution
Solution
$$ \displaystyle \begin{aligned}
& \text{Since we are finding the patterns of unoccupied spaces, we only care about choosing} \\
& \text{which } \mathrm{10} \text{ of the } \mathrm{20} \text{ spaces are empty (the other 10 will have cars).} \\
& \\
& \text{(a) Any spaces: Choose } \mathrm{10} \text{ spaces from } \mathrm{20}. \\
& \text{Ways} = {}^{\mathrm{20}}\mathrm{C}_{\mathrm{10}} = \mathrm{184756}. \\
& \\
& \text{(b) All cars in same row: This means one row is completely full, the other is completely empty.} \\
& \text{Ways} = \mathrm{2} \text{ (Either Row 1 is empty or Row 2 is empty).} \\
& \\
& \text{(c) Same number of cars in each row (5 in Row 1, 5 in Row 2).} \\
& \text{This means } \mathrm{5} \text{ empty spaces in Row 1 and } \mathrm{5} \text{ empty spaces in Row 2.} \\
& \text{Ways} = {}^{\mathrm{10}}\mathrm{C}_{\mathrm{5}} \times {}^{\mathrm{10}}\mathrm{C}_{\mathrm{5}} = \mathrm{252} \times \mathrm{252} = \mathrm{63504}. \\
& \\
& \text{(d) Two more cars in one row than the other (6 in one, 4 in the other).} \\
& \text{This means either (4 empty in Row 1 and 6 empty in Row 2) OR (6 empty in Row 1 and 4 empty in Row 2).} \\
& \text{Ways} = ({}^{\mathrm{10}}\mathrm{C}_{\mathrm{4}} \times {}^{\mathrm{10}}\mathrm{C}_{\mathrm{6}}) + ({}^{\mathrm{10}}\mathrm{C}_{\mathrm{6}} \times {}^{\mathrm{10}}\mathrm{C}_{\mathrm{4}}) \\
& = (\mathrm{210} \times \mathrm{210}) + (\mathrm{210} \times \mathrm{210}) = \mathrm{44100} + \mathrm{44100} = \mathrm{88200}.
\end{aligned} $$