공 주위를 패스하는 방법
다섯 명이 그들 사이에서 공을 패스하고 있습니다. 공은 Alonzo로 시작합니다. 공을 가진 각 사람은 공을 다른 사람에게 전달합니다. 여덟 번째 패스 후 공은 Alonzo로 돌아갑니다. 가능한 패스 시퀀스 수를 찾으십시오.
나는 8 개의 패스가 있기 때문에 $4^8$ 제한이 없을 때 공을 패스하는 방법 $7$ 패스가있을 것입니다 $4^6$Alonzo에게 다시 공을 패스하는 방법. 계속하려면 어떻게합니까?
답변
다음으로 시작하는 경로로 제한하여 재귀 적으로 작업합시다. $A$ (우리는 $A$ 에 $0^{th}$ 문자열의 슬롯).
허락하다 $a_n$ 길이의 경로 수 $n$ 그 끝 $A$. 표기법을 수정하기 위해 이니셜이$A$길이에 포함되지 않습니다. 그래서 우리는$a_1=0$ 예를 들어, 우리는 넣을 수 없기 때문에 $A$ 슬롯 $1$.
허락하다 $b_n$ 길이의 경로 수 $n$ 끝나지 않는 $A$. 그때,$b_1=4$ 예를 들면.
당신이 말했듯이, 우리는 $$a_n+b_n=4^n$$
재귀 적으로 우리는 $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$
이미 문제를 해결하기에 충분합니다. $$\boxed{a_8=13108}$$ 약간의 추가 작업은 $$a_n=\frac {4^n+4\times (-1)^n}5$$
힌트:
허락하다 $a_n$ 가능한 시퀀스의 수 $n$ 패스, Alonzo가 공으로 시작하고 Alonzo가 공을 다시 가져옵니다. $n$th 패스. 그때$a_1 = 0$ 과 $a_2 = 4$.
우리가 일련의 $n$패스, Alonzo가 공으로 시작하고 공을 가진 각 사람이 공을 다른 사람에게 패스하지만 마지막 패스가 Alonzo에있을 필요는 없습니다. 각 패스에 대해 4 가지 선택이 있으므로$4^n$가능한 시퀀스. 에$a_n$ 이 시퀀스 중 Alonzo는 공을 가진 마지막 사람입니다. $4^n - a_n$ Alonzo가 마지막 사람이 아닌 시퀀스.
이제 재귀를 사용하십시오. Alonzo는 공을 가질 수 없습니다.$n-1$th 패스.