5 friends are playing a game, passing a basketball back and forth. At each turn, the person with the ball randomly passes it to another person (one cannot pass the ball to oneself). The game starts with Daniel who is about to make the first pass of the game.

What is the probability that, after the $7^\text{th}$ pass, Daniel has the ball?

If your answer is of the form $\frac{p}{q},$ where $p$ and $q$ are coprime positive integers, submit $p+q.$

**
Bonus:
**
Find the probability that, in a game of
$n$
players, Daniel has the ball after the
$k^\text{th}$
pass.

The answer is 4915.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Method #1

In a game of $n$ players, let $p_k$ be the probability that Daniel has the ball after the $k$ -th turn.

We have $p_k = \displaystyle\frac{1}{n-1}\left(1-p_{k-1}\right)$ , and obviously $p_0=1$ and $p_1 = 0$

we can solve the recursive relation by subtracting both sides by $\displaystyle \frac{1}{n}$

$\begin{aligned}\displaystyle p_k - \frac{1}{n} &= -\frac{1}{n-1}p_{k-1} +\frac{1}{n-1}-\frac{1}{n} \\&= -\frac{1}{n-1}p_{k-1} + \frac{1}{n(n-1)} \\&= -\frac{1}{n-1}\left(p_{k-1} - \frac{1}{n}\right) \end{aligned}$

and thus $\displaystyle p_k - \frac{1}{n}$ is a geometric progression with common ratio $\displaystyle -\frac{1}{n-1}$

$\displaystyle p_k - \frac{1}{n} = \left(p_1 - \frac{1}{n}\right)\left(-\frac{1}{n-1}\right)^{k-1}$

and we have $\displaystyle p_k = \frac{1}{n} +\frac{n-1}{n}\left(-\frac{1}{n-1}\right)^k$

substituding $n = 5$ and $k = 7$ yields our answer $\displaystyle p_7 = \frac{1}{5} + \frac{4}{5}\left(-\frac{1}{4}\right)^7 = \boxed{\displaystyle \frac{819}{4096}}$

Method #2

The game can be visualised by a graph with the adjacency matrix

$A = \begin{pmatrix} 0&1&1&1&1\\ 1&0&1&1&1\\ 1&1&0&1&1\\ 1&1&1&0&1\\ 1&1&1&1&0 \end{pmatrix}$

Computing $A^7$ would give us the number of ways the ball passing can happen

$A^7 = \begin{pmatrix} 3276&3277&3277&3277&3277\\ 3277&3276&3277&3277&3277\\ 3277&3277&3276&3277&3277\\ 3277&3277&3277&3276&3277\\ 3277&3277&3277&3277&3276 \end{pmatrix}$

The probability is therefore $\displaystyle \frac{3276}{3277\times4 + 3276} = \boxed{\displaystyle \frac{819}{4096}}$