ボールを回す方法

Question

5人が自分たちの間でボールを渡している。ボールはアロンゾで始まります。ボールを持っている人はそれぞれ、ボールを他の人に渡します。8回目のパスの後、ボールはアロンゾに戻ります。パスの可能なシーケンスの数を見つけます。

パスが8つあるので $4^8$ 制限がない場合とその後のボールの通過方法 $7$ パスがあります $4^6$ボールをアロンゾに戻す方法。どうすれば続行できますか？

Answer 1

で始まるパスに制限して、再帰的に作業しましょう $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$$

Answer 2

ヒント：

しましょう $a_n$ の可能なシーケンスの数である $n$ アロンゾがボールからスタートし、アロンゾがボールを取り戻すパス $n$パス。次に$a_1 = 0$ そして $a_2 = 4$。

次のシーケンスがあるとします。 $n$パス。アロンゾはボールから始まり、ボールを持っている人は誰でもボールを他の人に渡しますが、最後のパスはアロンゾである必要はありません。パスごとに4つの選択肢があるため、$4^n$可能なシーケンス。に$a_n$ これらのシーケンスの中で、アロンゾはボールを持っている最後の人です。 $4^n - a_n$ アロンゾが最後の人ではないシーケンス。

ここで、再帰を使用します。アロンゾはボールを上に置くことができないことに注意してください$n-1$パス。