Evolton

京都大学 2022年度 前期日程 第2次学力試験文系数学 第2問

下図の三角柱ABC−DEFにおいて,Aを始点として,辺に沿って頂点をn回移動する.
すなわち,この移動経路P0→P1→P2→⋯→Pn−1→Pn(ただしP0=A)において,P0P1, P1P2, ⋯ , Pn−1Pnはすべて辺であるとする.
また,同じ頂点を何度通ってもよいものとする.
このような移動経路で,終点PnがA, B, Cのいずれかとなるものの総数anを求めよ.

問題の図

難易度5/ 10計算量3/ 10目安15分

数列、場合の数 状態分類、漸化式の変形、数え上げ

方針

三角柱の6頂点を、A,B,C 側にいる状態と D,E,F 側にいる状態の2種類にまとめる。各頂点からは、同じ三角形内の頂点へ進む辺が2本、反対側の対応する頂点へ進む辺が1本出ている。したがって、終点が上側にある経路数 an と下側にある経路数 bn は2本の漸化式を満たす。和は全経路数 3n、差は不変であることから an を求める。

解答

終点が A,B,C のいずれかである経路数を an、終点が D,E,F のいずれかである経路数を bn とする。初期状態は P0=A であるから a0=1,b0=0 である。

三角柱の各頂点からは、同じ三角形内の別の2頂点へ向かう辺が2本あり、反対側の対応する頂点へ向かう辺が1本ある。したがって、n 回移動後に上側 A,B,C にいる経路からは、次の1回で上側へ行くものが2通り、下側へ行くものが1通りである。同様に、下側にいる経路からは、次の1回で上側へ行くものが1通り、下側へ行くものが2通りである。

よって an+1=2an+bn,bn+1=an+2bn が成り立つ。

まず和をとると an+1+bn+1=3(an+bn) である。a0+b0=1 だから an+bn=3n である。これは、各回の移動先が常に3通りあることとも一致する。

次に差をとると an+1−bn+1=an−bn である。したがって an−bn は一定で、初期値より an−bn=a0−b0=1 である。

以上の2式 an+bn=3n,an−bn=1 を加えると 2an=3n+1 である。よって求める総数は an=3n+12 である。

別解

解法2

方針

各移動を「同じ三角形内の辺」と「対応頂点へ渡る辺」に分類する。終点が A,B,C 側にあるためには渡る辺を使う回数が偶数である。渡る回の位置を選び、残りの各回には同じ側で2通りの選択があるので、二項定理の偶数項和を使う。

解答

1回の移動には、現在いる三角形の内部で別の頂点へ進む2通りと、反対側の対応する頂点へ渡る1通りがある。

D,E,F 側へ渡る辺を使った回数を k とする。出発点は A,B,C 側なので、n 回後にも A,B,C 側にいるための必要十分条件は k が偶数である。

渡る k 回の位置は nCk 通りに選べる。残りの n−k 回は、その時いる三角形内で2本の辺から選ぶので 2n−k 通りである。したがってan=∑0≦k≦nk は偶数nCk2n−k.二項定理より3n=(2+1)n=∑k=0nnCk2n−k,1=(2−1)n=∑k=0n(−1)knCk2n−k.この2式を加えると奇数 k の項が消え、偶数 k の項が2倍になる。よって2an=3n+1,an=3n+12である。

総評

三角柱上の歩道数を数える問題。目安時間は10〜14分。公式出題意図は場合の数と漸化式の理解・計算力を評価するとしている。上下2状態の漸化式では和 3n と差 1 を使い、偶数回の層移動を数える解法では二項定理の偶数項和を使う。どちらも各頂点から同じ側へ2本、反対側へ1本というグラフ構造を根拠として書く。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る京大の数列の問題で問題集を作る

出典: 京都大学 2022年度 一般選抜(前期日程)数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。