
4. There are four basket-ball players $A, B, C, D$. Initially, the ball is with $A$. The ball is always passed from one person to a different person. In how many ways can the ball come back to $A$ after seven passes? (For example $A \rightarrow C \rightarrow B \rightarrow D \rightarrow A \rightarrow B \rightarrow C \rightarrow A$ and
$A \rightarrow D \rightarrow A \rightarrow D \rightarrow C \rightarrow A \rightarrow B \rightarrow A$ are two ways in which the ball can come back to $A$ after seven passes.)


Solution: Let $x_{n}$ be the number of ways in which $A$ can get back the ball after $n$ passes. Let $y_{n}$ be the number of ways in which the ball goes back to a fixed person other than $A$ after $n$ passes. Then

$$
x_{n}=3 y_{n-1} \text {, }
$$

and

$$
y_{n}=x_{n-1}+2 y_{n-1}
$$

We also have $x_{1}=0, x_{2}=3, y_{1}=1$ and $y_{2}=2$.

Eliminating $y_{n}$ and $y_{n-1}$, we get $x_{n+1}=3 x_{n-1}+2 x_{n}$. Thus

$$
\begin{aligned}
& x_{3}=3 x_{1}+2 x_{2}=2 \times 3=6 \\
& x_{4}=3 x_{2}+2 x_{3}=(3 \times 3)+(2 \times 6)=9+12=21 \\
& x_{5}=3 x_{3}+2 x_{4}=(3 \times 6)+(2 \times 21)=18+42=60 \\
& x_{6}=3 x_{4}+2 x_{5}=(3 \times 21)+(2 \times 60)=63+120=183 \\
& x_{7}=3 x_{5}+2 x_{6}=(3 \times 60)+(2 \times 183)=180+366=546
\end{aligned}
$$

Alternate solution: Since the ball goes back to one of the other 3 persons, we have

$$
x_{n}+3 y_{n}=3^{n}
$$

since there are $3^{n}$ ways of passing the ball in $n$ passes. Using $x_{n}=$ $3 y_{n-1}$, we obtain

$$
x_{n-1}+x_{n}=3^{n-1}
$$

with $x_{1}=0$. Thus

$$
\begin{array}{r}
x_{7}=3^{6}-x_{6}=3^{6}-3^{5}+x_{5}=3^{6}-3^{5}+3^{4}-x_{4}=3^{6}-3^{5}+3^{4}-3^{3}+x_{3} \\
=3^{6}-3^{5}+3^{4}-3^{3}+3^{2}-x_{2}=3^{6}-3^{5}+3^{4}-3^{3}+3^{2}-3 \\
=\left(2 \times 3^{5}\right)+\left(2 \times 3^{3}\right)+(2 \times 3)=486+54+6=546
\end{array}
$$
