wu :: forums
« wu :: forums - Permutation Combination 2 »

Welcome, Guest. Please Login or Register.
Sep 25th, 2018, 9:55am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Grimbal, ThudnBlunder, Icarus, towr, SMQ, Eigenray, william wu)
   Permutation Combination 2
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Permutation Combination 2  (Read 113 times)
navdeep1771
Newbie
*



Let your thoughts go beyond your imagination

    navi
Email

Gender: male
Posts: 22
Permutation Combination 2  
« on: Jun 18th, 2018, 9:57pm »
Quote Quote Modify Modify

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.
« Last Edit: Jun 18th, 2018, 10:00pm by navdeep1771 » IP Logged
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Permutation Combination 2  
« Reply #1 on: Jun 19th, 2018, 6:18am »
Quote Quote Modify 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(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
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Permutation Combination 2  
« Reply #2 on: Jun 20th, 2018, 10:53am »
Quote Quote Modify Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7408
Re: Permutation Combination 2  
« Reply #3 on: Jun 21st, 2018, 2:17pm »
Quote Quote Modify Modify


If a0 counts the ways for A to have the ball and a1 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 21st, 2018, 2:37pm by Grimbal » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Permutation Combination 2  
« Reply #4 on: Jun 21st, 2018, 11:04pm »
Quote Quote Modify 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 21st, 2018, 11:04pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7408
Re: Permutation Combination 2  
« Reply #5 on: Jun 22nd, 2018, 4:39am »
Quote Quote Modify Modify

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.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Permutation Combination 2  
« Reply #6 on: Jun 22nd, 2018, 5:27am »
Quote Quote Modify Modify

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?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7408
Re: Permutation Combination 2  
« Reply #7 on: Jun 23rd, 2018, 3:46am »
Quote Quote Modify 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).
(000 1)
(P-T000)
(0P-T00)
(00P-TP-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
« Last Edit: Jun 23rd, 2018, 3:47am by Grimbal » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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