OMC143(D)

ユーザー解説 by myiru

　漸化式を用いた解法です．

　問題の椅子の個数が $n$ 個である時の座り方の総数を $a_n$ とおく． $n+1$ 個の椅子がある時，最も左の椅子に人が座っている場合の座り方の総数は $a_{n-5}$ ，座っていない場合の座り方の総数は $a_{n-1}$ と表せることから， $a_n=a_{n-1}+a_{n-5},a_1=2,a_2=3,a_3=4,a_4=5,a_5=6$ が成立し，これを用いて $a_{20}$ を求めればよく，求める値は $a_{20}-1=\bf{430}$ である．(誰も座っていない時も含まれていることに注意する．)