wu :: forums - Print Page


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

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

Title: Permutation Combination 2
Post by navdeep1771 on Jun 18^th, 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 19^th, 2018, 6:18am

Answer: [hide]546[/hide]

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 20^th, 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 21^st, 2018, 2:17pm

[hide]
If a₀ counts the ways for A to have the ball and a₁ the ways not to have the ball, then
you start with a={1,0}.
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 21^st, 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 22^nd, 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 22^nd, 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 23^rd, 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]