Maths Olympiad Prep

Library / /57 of 121

Combinatorics Difficulty 6.0 AIME, harder Find the answer India

Problem:
There are four basket-ball players AA, BB, CC, DD. Initially, the ball is with AA. The ball is always passed from one person to a different person. In how many ways can the ball come back to AA after seven passes? (For example ACBDABCAA \rightarrow C \rightarrow B \rightarrow D \rightarrow A \rightarrow B \rightarrow C \rightarrow A and ADADCABAA \rightarrow D \rightarrow A \rightarrow D \rightarrow C \rightarrow A \rightarrow B \rightarrow A are two ways in which the ball can come back to AA after seven passes.)

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
Let xnx_{n} be the number of ways in which AA can get back the ball after nn passes. Let yny_{n} be the number of ways in which the ball goes back to a fixed person other than AA after nn passes. Then
xn=3yn1, x_{n}=3 y_{n-1},
and
yn=xn1+2yn1 y_{n}=x_{n-1}+2 y_{n-1}
We also have x1=0x_{1}=0, x2=3x_{2}=3, y1=1y_{1}=1 and y2=2y_{2}=2.

Eliminating yny_{n} and yn1y_{n-1}, we get xn+1=3xn1+2xnx_{n+1}=3 x_{n-1}+2 x_{n}. Thus
x3=3x1+2x2=2×3=6x4=3x2+2x3=(3×3)+(2×6)=9+12=21x5=3x3+2x4=(3×6)+(2×21)=18+42=60x6=3x4+2x5=(3×21)+(2×60)=63+120=183x7=3x5+2x6=(3×60)+(2×183)=180+366=546 \begin{aligned} & x_{3}=3 x_{1}+2 x_{2}=2 \times 3=6 \\ & x_{4}=3 x_{2}+2 x_{3}=(3 \times 3)+(2 \times 6)=9+12=21 \\ & x_{5}=3 x_{3}+2 x_{4}=(3 \times 6)+(2 \times 21)=18+42=60 \\ & x_{6}=3 x_{4}+2 x_{5}=(3 \times 21)+(2 \times 60)=63+120=183 \\ & x_{7}=3 x_{5}+2 x_{6}=(3 \times 60)+(2 \times 183)=180+366=546 \end{aligned}

Alternate solution:
Since the ball goes back to one of the other 3 persons, we have
xn+3yn=3n x_{n}+3 y_{n}=3^{n}
since there are 3n3^{n} ways of passing the ball in nn passes. Using xn=3yn1x_{n}=3 y_{n-1}, we obtain
xn1+xn=3n1 x_{n-1}+x_{n}=3^{n-1}
with x1=0x_{1}=0. Thus
x7=36x6=3635+x5=3635+34x4=3635+3433+x3=3635+3433+32x2=3635+3433+323=(2×35)+(2×33)+(2×3)=486+54+6=546 \begin{array}{r} x_{7}=3^{6}-x_{6}=3^{6}-3^{5}+x_{5}=3^{6}-3^{5}+3^{4}-x_{4}=3^{6}-3^{5}+3^{4}-3^{3}+x_{3} \\ =3^{6}-3^{5}+3^{4}-3^{3}+3^{2}-x_{2}=3^{6}-3^{5}+3^{4}-3^{3}+3^{2}-3 \\ =\left(2 \times 3^{5}\right)+\left(2 \times 3^{3}\right)+(2 \times 3)=486+54+6=546 \end{array}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.