wu :: forums « wu :: forums - Permutation Combination 2 » Welcome, Guest. Please Login or Register. Apr 17th, 2024, 8:44am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, Eigenray, Grimbal, towr, ThudnBlunder, Icarus, SMQ)    Permutation Combination 2 « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Permutation Combination 2  (Read 522 times)
navdeep1771
Newbie

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: 2872
 Re: Permutation Combination 2   « Reply #1 on: Jun 19th, 2018, 6:18am » Quote Modify

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: 7526
 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
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: 7526
 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: 7526
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »