1.

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 → B → C → A and A → D → A → D → C →  A → B → A are two ways in which the ball  can come back to A after seven passes.)

Answer»

Let xn be the number of ways in which A can get back the ball after n passes. Let yn be the number of ways in which the ball goes back to a fixed person other than A after n passes. Then 

xn = 3yn - 1; 

and 

yn = xn - 1 + 2yn -1: 

We also have x1 = 0, x2 = 3, y1 = 1 and y2 = 2. 

Eliminating yn and yn-1, we get xn+1 = 3xn-1 + 2xn.Thus 

x3 = 3x1 + 2x2 = 2 x 3 = 6; 

x4 = 3x2 + 2x3 = (3 x 3) + (2 x 6) = 9 + 12 = 21; 

x5 = 3x3 + 2x4 = (3 x 6) + (2 x 21) = 18 + 42 = 60; 

x6 = 3x4 + 2x5 = (3 x 21) + (2 x 60) = 63 + 120 = 183; 

x7 = 3x5 + 2x6 = (3 x 60) + (2 x 183) = 180 + 366 = 546: 

Alternate solution: Since the ball goes back to one of the other 3 persons, we have 

xn + 3yn = 3n; 

since there are 3n ways of passing the ball in n passes. Using xn = 3yn -1, we obtain 

xn-1 + xn = 3n-1; 

with x1 = 0. Thus 

x7 = 36 - x6 = 36 - 35 + x5 = 36 - 35 + 34 - x4 = 36 - 35 + 34 - 33 + x3 

= 36 - 35 + 34 - 33 + 32 - x2 = 36 - 35 + 34 - 33 + 32 - 3 

= (2 x 35) + (2 x 33) + (2 x 3) = 486 + 54 + 6 = 546:


Discussion

No Comment Found

Related InterviewSolutions