方針
三角柱の6頂点を、 側にいる状態と 側にいる状態の2種類にまとめる。各頂点からは、同じ三角形内の頂点へ進む辺が2本、反対側の対応する頂点へ進む辺が1本出ている。したがって、終点が上側にある経路数 と下側にある経路数 は2本の漸化式を満たす。和は全経路数 、差は不変であることから を求める。
解答
終点が のいずれかである経路数を 、終点が のいずれかである経路数を とする。初期状態は であるから である。
三角柱の各頂点からは、同じ三角形内の別の2頂点へ向かう辺が2本あり、反対側の対応する頂点へ向かう辺が1本ある。したがって、 回移動後に上側 にいる経路からは、次の1回で上側へ行くものが2通り、下側へ行くものが1通りである。同様に、下側にいる経路からは、次の1回で上側へ行くものが1通り、下側へ行くものが2通りである。
よって が成り立つ。
まず和をとると である。 だから である。これは、各回の移動先が常に3通りあることとも一致する。
次に差をとると である。したがって は一定で、初期値より である。
以上の2式 を加えると である。よって求める総数は である。
別解
解法2
方針
各移動を「同じ三角形内の辺」と「対応頂点へ渡る辺」に分類する。終点が 側にあるためには渡る辺を使う回数が偶数である。渡る回の位置を選び、残りの各回には同じ側で2通りの選択があるので、二項定理の偶数項和を使う。
解答
1回の移動には、現在いる三角形の内部で別の頂点へ進む2通りと、反対側の対応する頂点へ渡る1通りがある。
側へ渡る辺を使った回数を とする。出発点は 側なので、 回後にも 側にいるための必要十分条件は が偶数である。
渡る 回の位置は 通りに選べる。残りの 回は、その時いる三角形内で2本の辺から選ぶので 通りである。したがって二項定理よりこの2式を加えると奇数 の項が消え、偶数 の項が2倍になる。よってである。
総評
三角柱上の歩道数を数える問題。目安時間は10〜14分。公式出題意図は場合の数と漸化式の理解・計算力を評価するとしている。上下2状態の漸化式では和 と差 を使い、偶数回の層移動を数える解法では二項定理の偶数項和を使う。どちらも各頂点から同じ側へ2本、反対側へ1本というグラフ構造を根拠として書く。