25. Challengeborough's underground train network consists of six lines $p, q, r, s, t$ and $u$, as shown. Wherever two lines meet there is a station which enables passengers to change lines. On each line, each train stops at every station.
Jessica wants to travel from station $X$ to station $Y$. She does not want to use any line more than once, nor return to station $X$ after leaving it, nor leave station $Y$ after reaching it.
How many different routes, satisfying these conditions, can she choose?

A 9
B 36
C 41
D 81
E 720
SolUtion
D A route is specified by giving the sequence of lines that Jessica travels on. We call the lines $s, t$ and $u$ the $X$-lines and the lines $p, q$ and $r$ the $Y$-lines. It follows from the layout of the network and Jessica's conditions, that she can change trains between any $X$-line and any $Y$-line and vice versa, but she cannot change between two $X$-lines, or between two $Y$-lines. So her route from $X$ to $Y$ is given by a sequence of lines starting with an $X$-line, alternating between $X$-lines and $Y$-lines, and ending with a Y-line. So it will consist of an even number of lines. Since Jessica does not wish to use any line more than once, a possible route for Jessica consists of 2,4 or 6 lines. We count these routes according to the number of lines involved.
2 lines A route of 2 lines will be of the form $g, h$, where $g$ is an $X$-line and $h$ is a $Y$-line. There are 3 choices for $g$ and 3 choices for $h$, and hence $3 \times 3=9$ routes of this form.
4 lines A route of 4 lines will be of the form $g, h, i, j$, where $g$ and $i$ are two different $X$-lines and $h$ and $j$ are two different $Y$-lines. Since there are 3 choices for $g$ and then 2 choices for $i$ and likewise for $h$ and $j$, there are $3 \times 3 \times 2 \times 2=36$ routes of this form.
6 lines A route of 6 lines will have the form $g, h, i, j, k, l$, where $g, i$ and $k$ are $X$-lines and $h, j$ and $l$ are $Y$-lines. As before there are 3 choices for $g$ and then 2 choices for $i$, leaving just one choice for $k$, and likewise for the choices of $h, j$ and $l$. So there are $3 \times 3 \times 2 \times 2 \times 1 \times 1=36$ routes of this form.
So, altogether, there are $9+36+36=81$ routes that satisfy Jessica's conditions.