In how many ways can the ball come back to $A$ after seven passes?

Let $A(n)$ be the number of ways to end at $A$ after $n$ passes. Let $B(n)$ be the number of ways to end at $B$ after $n$ passes. Clearly $C(n)=B(n)=D(n)$.
$A(1)=0,B(1)=1$
$A(n+1)=3B(n)$
$B(n+1)=2B(n)+A(n)$
It is now simple to calculate $A(7)$.
When $A$ receives the $n+1^{th}$ pass, the previous player was $B,C or D$ after $n$ passes, so $A(n+1)=B(n)+C(n)+D(n).$
When $B$ receives the $n+1^{th}$ pass, either $A,C or D$ received the nth pass, so $B(n+1)=A(n)+C(n)+D(n)$.
Since $B(n)=C(n)=D(n)$, that means $A(n+1)=3B(n)$.
To calculate $A(7)$, first calculate $A(2)$ and $B(2)$, then $A(3)$ and $B(3)$, and so on.


For each number of passes $n$, let $u_n$ be the number of pass sequences ending at $A$ and $v_n$ be the number of pass sequences not ending at $A$. Then we have:

$$u_{n+1} = v_n$$ $$v_{n+1} = 3u_n + 2v_n$$

Substituting $u_n = v_{n-1}$ in the second equation gives

$$v_{n+1} = 3v_{n-1} + 2v_n$$

This is a standard linear recurrence (see for instance this Wikipedia article). The polynomial $x^2-2x-3$ has roots $3$ and $-1$, so $v_n=A\cdot3^n+B\cdot(-1)^n$ for some constants $A$ and $B$. Using the initial values $v_0=0$ and $v_1=3$, we get $A+B=0$ and $3A-B=3$, which gives $A=\frac34, B=-\frac34$.

Hence $v_n = \frac34(3^n-(-1)^n)$, and $u_n$ (which is what we want here) is equal to $v_{n-1} = \frac34(3^{n-1}-(-1)^{n-1}) =\frac143^n + \frac34(-1)^n$.

The final answer is therefore $u_7 = \frac14(3^7-3) = 546$.


Let the number of circuits that get back to $A$ after $n$ passes be $f(n)$

We have two cases. Either pass $n-2$ is to $A$ or it is not.

If pass $n-2$ is to $A$, then the pass $n-1$ can be to any other player. Thus, the number of such circuits is $3f(n-2)$.

If pass $n-2$ is not to $A$, then pass $n-1$ is to one of the two people other than $A$ and the person who got pass $n-2$. Thus, we can substitute $A$ for the receiver of pass $n-1$, and get a unique $n-1$ circuit. Thus, the number of such circuits is $2f(n-1)$.

Therefore, we get the recursion $$ f(n)=2f(n-1)+3f(n-2) $$ with $f(0)=1$ and $f(1)=0$. This linear recurrence has the solution $$ f(n)=\frac{3^n+3(-1)^n}4 $$

Tags:

Combinatorics

Related

Show that the arithmetic mean is less or equal than the quadratic mean How to solve this ordinary differential equation? Does there exist a space $W$ s.t. $X\to W,\ Y\to W$ are covering spaces when $Z\to X,\ Z\to Y$ are covering spaces? Prove that vector space and dual space have same dimension If $G$ is a compact topological group, how to show that a finite index subgroup of $G$ is open? Are $\emptyset$ and $X$ closed, open or clopen? $ \sum_{n=1}^{\infty}a_{n} $ diverges but $ \sum_{n=1}^{\infty}\frac{a_{n}}{1+a_{n}^{2}} $ sometimes converges and sometime diverges. Euler's formula, is this true? Evaluation of integral $\int_{0}^{\infty}\frac{\sin x}{x\left ( 1+x^2 \right )^2}\,{\rm d}x$ Propositional Logic Help: $(\neg p \wedge (p \vee q)) \rightarrow q $ is a tautology Can Number Theory be visualized? When is $2^n -7$ a perfect square?

Recent Posts