Author 
Topic: Permutation Combination 2 (Read 143 times) 

navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender:
Posts: 22


Permutation Combination 2
« on: Jun 18^{th}, 2018, 9:57pm » 
Quote Modify

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.

« Last Edit: Jun 18^{th}, 2018, 10:00pm by navdeep1771 » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2819


Re: Permutation Combination 2
« Reply #1 on: Jun 19^{th}, 2018, 6:18am » 
Quote Modify

Answer: 546 Solution: hidden:  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 


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13660


Re: Permutation Combination 2
« Reply #2 on: Jun 20^{th}, 2018, 10:53am » 
Quote Modify

One might simplify A(n) further to A(n) = 2A(n1) + 3A(n2) = [3*(1)^n + 3^n)]/4


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7443


Re: Permutation Combination 2
« Reply #3 on: Jun 21^{st}, 2018, 2:17pm » 
Quote Modify

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. PS: 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.

« Last Edit: Jun 21^{st}, 2018, 2:37pm by Grimbal » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13660


Re: Permutation Combination 2
« Reply #4 on: Jun 21^{st}, 2018, 11:04pm » 
Quote Modify

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)

« Last Edit: Jun 21^{st}, 2018, 11:04pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7443


Re: Permutation Combination 2
« Reply #5 on: Jun 22^{nd}, 2018, 4:39am » 
Quote Modify

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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13660


Re: Permutation Combination 2
« Reply #6 on: Jun 22^{nd}, 2018, 5:27am » 
Quote Modify

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?


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7443


Re: Permutation Combination 2
« Reply #7 on: Jun 23^{rd}, 2018, 3:46am » 
Quote Modify

hidden:  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  )  (  PT  0  0  0  )  (  0  PT  0  0  )  (  0  0  PT  PT1  )  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 ~= (P1)! / (PT1)! * (PT)^(NT) / P 

« Last Edit: Jun 23^{rd}, 2018, 3:47am by Grimbal » 
IP Logged 



