In how many ways can the ball can be returned back to player $A$ if no player can receive the ball more than $2$ times?

Question

Four players $A$, $B$, $C$, $D$ are playing with a ball, passing the ball to each other. If $A$ starts by passing the ball to any of the players $B$, $C$, $D$, then find the number of ways in which the ball can return to $A$ when it is known that a player can't receive the ball more than $2$ times?

Given answer is $111$. I was trying to make cases like $A$ has $3$ options in the beginning and after that make various cases like first one who gets a ball gives it straight away to $A$ or gives it to one of the other two and so forth, but it is turning out to be lengthy. Could someone suggest a better approach?

Answer 1

Let's denote $X_0X_1X_2X_3X_4X_5X_6X_7$ a sequence of a passing ball between a set of $X_i\in \{A,B,C,D\}$ respectively in order after leaving the starting point $A$.

Using inclusiong/exclusion principle we can count the number of plays where the ball doesn't stop in hands of $A$, this includes BCBDCAD for instance.

• 1/ The number of plays when A has the last catch is $\binom{6}{2,2,2}$ permutations of a set {A,A,B,B,C,C}.

The problem with this number is that sequences like BBXXXX and CCXXXX and DDXXXX are counted twice, this sums to 2*3 cases where we need to remove just 3 of them $3*\binom{5}{2,2}$.

This leaves us with another 3 cases BBCCXX , BBDDXX and CCDDXX to be added, $3*\binom{4}{2}$.

The last sequence AABBCC is removed thrice then added 3 times thus it should be removed, $3!$ in total.

All raises to $S(xxxxxxA)=S(all)-S(BB\cup CC \cup DD)+S(BB\cap CC)+S(BB\cap DD)+S(CC\cap DD)-(BB\cap CC\cap DD)$

$S(x_iA)=\frac{6!}{8}-3*\frac{5!}{4}+3*\frac{4!}{2}-3!=30$

• 2/ The number of plays when A has the beforelast catch is the same as the previous just including some valid cases like xxxxBB and xxxxCC and xxxxDD because A is in the midst of the last two, cases aren't intersected this evaluates to $2*\binom{3}{2}$ let's call it $|V_1|$.

$S(x_iAx)=S(x_iA)+|V_1|=30+3*2=36$

To not be forgotten that this case involves symmetricity when $A$ is the second to catch the ball, let's denominate it $Sy(x_iAx)=S(xAx_i)$. As it happens to be just 3 cases.

• 2/ The number of plays when A has the third to last catch is the same as the first one just including supplementary cases like xxxBBx and xxxCCx and xxxDDx because A is in the midst of the beforelast two players, cases aren't intersected. It gives $|V_2|=|V_1|=6$.

Bore in mind as well, since the game doesn't keep on beyond A, that S should be divided by 2 distinct players after when $A$ catches the ball. additional occurences that souldn't be divided comprehend a case of two adjacent identical players succeeding $A$, $|V_3|=S(x_iABB)+S(x_iACC)+S(x_iADD)=3*2=6$. the result mounts to $S(x_iAxx)=\frac{S(x_iA)+|V_2|}{2}+|V_3|=\frac{S(x_iAx)}{2}+6$.

Symmetricity $Sy(x_iAxx)=S(xxAx_i)$ is just figuring in remaining cases divided by, which is $2*\binom{3}{2}$.

• 3/ When A has the fourth before last catch possibilities could be enumerated manually, it includes two major subsets $S_1=\{BCBA,CBCA,CDCA...\}$, $|S_1|=\binom{3}{2}*2=6$. And $S_2=\{BCDA,DBCA,...\}$, $|S_2|=3!=6$. Which sums up to $S(x_iAxxx)=|S_1|+|S_2|=6+6=12$.

Symmetricity here doesn't count.

• All in all:

$$S=S(x_iA)+S(x_iAx)+sy(x_iAx)+S(x_iAxx)+sy(x_iAxx)+S(x_iAxxx)$$ $$S=30+36+3+(36/2+6)+6+12=111$$ overall.

Answer 2

Given there are $111$ solutions, you want to show there are $37$ starting with $AB$.
There is $ABA$, then by symmetry you want to show there are $18$ starting with $ABC$.
There is $ABCA$, and then you count six starting $ABCB$, so you need to find $11$ left starting $ABCD$.
There is $ABCDA$, so by symmetry you need to count $5$ starting $ABCDB$.

Answer 3

Call the players $A$, $1$, $2$, $3$. Assume that $A$ passes to $1$, and $1$ passes to $2$. Then we have the following tree of potential histories:

Together with the first vertex marked $2$ there are $18$ possible vertices to stop the game by passing the ball back to $A$. Multiply by $6$ for the choice $A\to1\to2$ made at the beginning, and add $3$ for the cases where the ball is returned to $A$ after the first pass. Gives $111$ in all.