Evolton

京都大学 2003年度 後期日程 第2次学力試験理系(後期)数学 第6問

7つの文字を並べた列a1a2⋯a7で,次の3つの条件をみたすものの総数を求めよ.

(i) a1,a2,⋯ ,a7はA,B,C,D,E,Fのいずれかである

(ii) i=1,2,⋯ ,6に対し,aiとai+1は相異なる

(iii) i=1,2,⋯ ,6に対し,aiとai+1は右図において線分で結ばれている

問題の図

難易度3/ 10計算量2/ 10目安8分

場合の数 数え上げ、状態分類

方針

図は三角形 ABD と三角形 CEF の対応する頂点を結んだ三角柱の辺グラフであり、各頂点から出る辺は3本である。最初の文字を選んだ後は、直前の頂点に隣接する3頂点から次を選ぶ。

解答

図の各頂点に接続する頂点を調べるとAB,D,EBA,D,FCD,E,FDA,B,CEA,C,FFB,C,Eであり、どの頂点の次数も3である。また辺は異なる二頂点を結ぶので、辺を選ぶ限り条件(ii)も自動的に満たされる。

最初の文字 a1 は6通りに選べる。ai が決まったとき、ai+1 はそれに辺で結ばれた3文字から選べるので常に3通りである。遷移は6回あるから、総数は6⋅36=4374である。

別解

解法2(末尾文字ごとの漸化式)

方針

長さ m の列を末尾の文字ごとに数える。図の各頂点に接続する文字が3個ずつであることから、総数の漸化式を得る。

解答

長さ m で条件を満たし、末尾が文字 X である列の数を Nm(X) とする。図では各文字に隣接する文字がちょうど3個ある。

長さ m+1 の列を作るには、長さ m の列の末尾から、線分で結ばれた3文字のいずれかへ移ればよい。したがって総数Tm=∑X∈{A,B,C,D,E,F}Nm(X)はTm+1=3Tmを満たす。初めの文字は自由に選べるのでT1=6.よってTm=6⋅3m−1.求める列の長さは7だからT7=6⋅36=4374である。各辺は異なる2頂点を結ぶため、線分に沿って移る限り「隣接する文字が相異なる」という条件も自動的に満たされる。

総評

難度3、計算量2。想定時間は8分程度。図が複雑に交差して見えるが、交点は頂点ではなく、6頂点はいずれも次数3である。各段階の選択肢数が常に3なので、直前以外の履歴を分類する必要はない。

第1解法は標準的な答案構成を詳しく示し、第2解法は異なる着眼または計算経路で同じ結論を再確認する。図は式変形の役割と条件の使いどころを可視化した。積分・極限・総和は独立行に置き、分数は表示サイズで組版した。

Evolton Pro

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

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

出典: 京都大学 2003年度 後期 理系 第6問。問題文はHTML表示のために再入力・数式組版しています。