

Title: Permutation Combination 2 Post by navdeep1771 on Jun 18^{th}, 2018, 9:57pm There are four basketball 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(n1)+C(n1)+D(n1) = 3B(n1) B(n) = A(n1)+C(n1)+D(n1) = A(n1) + 2B(n1) 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(n1) + 3A(n2) = [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_{0} counts the ways for A to have the ball and a_{1} 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 P1 players. But the second time, there are T players (A inclusive) who can not receive the ball. So the first T1 throws must be treated specially, the players have more choices than the (PT) choices they have eventually. 

Title: Re: Permutation Combination 2 Post by towr on Jun 22^{nd}, 2018, 5:27am Don't the first T1 turns just give a multiplier of (P1)!/(T1)!, and from that point on you can treat it generically as (PT) 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).
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 ~= (P1)! / (PT1)! * (PT)^(NT) / P [/hideb] 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 