```

wu :: forums
(http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)

riddles >> hard >> Permutation Combination 2
(Message started by: navdeep1771 on Jun 18th, 2018, 9:57pm)

```

Title: Permutation Combination 2
Post by navdeep1771 on Jun 18th, 2018, 9:57pm
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 -> C -> B -> D -> A -> C -> D -> A ) is one way in which ball can come back to A.

Title: Re: Permutation Combination 2
Post by rmsgrey on Jun 19th, 2018, 6:18am

Solution:
[hideb]
Letting A(n) be the number of ways for A to have the ball after n passes, and B(n) ( =C(n)=D(n) ) be the number of ways for B (or C or D) to have it after n passes gives the recurrence relation:
A(0) = 1
B(0) = 0

A(n) = B(n-1)+C(n-1)+D(n-1) = 3B(n-1)
B(n) = A(n-1)+C(n-1)+D(n-1) = A(n-1) + 2B(n-1)

Iterating gives:
n: A(n), B(n)
0: 1, 0
1: 0, 1
2: 3, 2
3: 6, 7
4: 21, 20
5: 60, 61
6: 183, 182
7: 546, 547
[/hideb]

Title: Re: Permutation Combination 2
Post by towr on Jun 20th, 2018, 10:53am
One might simplify A(n) further to [hide]A(n) = 2A(n-1) + 3A(n-2) = [3*(-1)^n + 3^n)]/4 [/hide]

Title: Re: Permutation Combination 2
Post by Grimbal on Jun 21st, 2018, 2:17pm
[hide]
If a0 counts the ways for A to have the ball and a1 the ways not to have the ball, then
If A has the ball, after a pass, A has 0 ways to have the ball and 3 ways not to have it.
If A does not have the ball, after a pass, A has 1 way to have the ball and 2 ways not to have it.
So a pass multiplies the vector 'a' by [0,1},{3,2].
After 7 passes it is [0,1},{3,2]^7 = [546,547},{1641,1640].
See http://www.wolframalpha.com/input/?i=[0,1},{3,2]^7
So the number of ways is:
{1,0} x [0,1},{3,2]^7 x {1,0} = 546.
And the formula works for other values of the constant 7.
[/hide]
PS:
[hide]
The same page gives the eigenvalues of the matrix as 3 and -1.  So you know the general formula for A(n) is a combination of 3^n and -1^n.  As towr found out.
[/hide]

Title: Re: Permutation Combination 2
Post by towr on Jun 21st, 2018, 11:04pm
We can generalize this problem to P players, and players having to wait T turns before the ball can return to them, with the sequences of passes ending after N turns. (So we've dealt with P=4,T=1,N=7)
Is there a simple generic solution for this? (Taking P into account seems simple enough, but maybe T might complicate things)

Title: Re: Permutation Combination 2
Post by Grimbal on Jun 22nd, 2018, 4:39am
One difficulty is that for instance the first time A throws the ball he can throw it to all P-1 players.  But the second time, there are T players (A inclusive) who can not receive the ball.
So the first T-1 throws must be treated specially, the players have more choices than the (P-T) choices they have eventually.

Title: Re: Permutation Combination 2
Post by towr on Jun 22nd, 2018, 5:27am
Don't the first T-1 turns just give a multiplier of (P-1)!/(T-1)!, and from that point on you can treat it generically as (P-T) choices onward?

Title: Re: Permutation Combination 2
Post by Grimbal on Jun 23rd, 2018, 3:46am
[hideb]
Right you are!
The first T turns A will not receive the ball anyway.
The vector must now describe how long A did not have the ball, from 0 to T turns.  It has T+! dimensions.  After T turns, the vector has a 1 at position T.  a = {0,...,1}.  From there on, the vector is multiplied by the following matrix:  (shown for T=3).
 ( 0 0 0 1 ) ( P-T 0 0 0 ) ( 0 P-T 0 0 ) ( 0 0 P-T P-T-1 )
We can assume P>T because else the process has to stop before A gets the ball back.

Since the information on the starting position gets diluted fast, the number of ways for A to get the ball in N turns should approach
(the total number of paths in N turns)/(#players)
That is
ways ~= (P-1)! / (P-T-1)! * (P-T)^(N-T) / P
[/hideb]