4. A route on the $3 \times 3$ board shown consists of a number of steps. Each step is from one square to an adjacent square of a different colour.
How many different routes are there from square $\mathrm{S}$ to square $\mathrm{T}$ which pass through every other square exactly once?
A 0
B 1
C 2
D 3
E 4
Solution
C For convenience, label the other squares as in the left-hand figure. The first move of a route from $\mathrm{S}$ to $\mathrm{T}$ must be either $\mathrm{S} \rightarrow \mathrm{M}$ or $\mathrm{S} \rightarrow \mathrm{Q}$. It is easy to see that a route that visits all the squares must include both the sequence $\mathrm{M} \rightarrow \mathrm{K} \rightarrow \mathrm{L}$ and the sequence $\mathrm{Q} \rightarrow \mathrm{R} \rightarrow \mathrm{P}$. Hence, we see that there are just two routes that meet all the required conditions; these are shown in two figures on the the right.