Author |
Topic: Permutation Combination 2 (Read 553 times) |
|
navdeep1771
Newbie
Let your thoughts go beyond your imagination
Gender: 
Posts: 28
|
 |
Permutation Combination 2
« on: Jun 18th, 2018, 9:57pm » |
 Quote  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
   
Gender:
Posts: 2873
|
|
Re: Permutation Combination 2
« Reply #1 on: Jun 19th, 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(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:
Posts: 13730
|
|
Re: Permutation Combination 2
« Reply #2 on: Jun 20th, 2018, 10:53am » |
Quote 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:
Posts: 7527
|
|
Re: Permutation Combination 2
« Reply #3 on: Jun 21st, 2018, 2:17pm » |
Quote 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:
Posts: 13730
|
|
Re: Permutation Combination 2
« Reply #4 on: Jun 21st, 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 21st, 2018, 11:04pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Permutation Combination 2
« Reply #5 on: Jun 22nd, 2018, 4:39am » |
Quote 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:
Posts: 13730
|
|
Re: Permutation Combination 2
« Reply #6 on: Jun 22nd, 2018, 5:27am » |
Quote 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:
Posts: 7527
|
|
Re: Permutation Combination 2
« Reply #7 on: Jun 23rd, 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 | ) | | ( | 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
|
|
| « Last Edit: Jun 23rd, 2018, 3:47am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print