Evolton

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

n,kは自然数で,n≧3,k≧2を満たすものとする.
いま,n角柱のn+2個の面に1からn+2までの番号が書いてあるものとする.
このn+2個の面に1面ずつ,異なるk色の中から1色ずつ選んでは塗っていく.
このとき,どの隣り合う面の組も同一色では塗られない塗り方の数をPkで表す.

(1) P2とP3を求めよ.

(2) n=7のとき,P4を求めよ.

難易度7/ 10計算量6/ 10目安25分

場合の数 数え上げ、場合分け、計算整理

方針

2つの底面は互いには隣り合わず、各底面はすべての側面と隣り合う。そこで底面2つが同色か異色かで分ける。底面の色を決めると、側面で使える色数がそれぞれ k−1, k−2 に決まり、側面 n 枚は輪状に並ぶので、輪 Cn を q 色で隣り合う面が異色になるように塗る数 (q−1)n+(−1)n(q−1) を使う。この公式を側面に適用し、最後に k=2,3 および n=7,k=4 を代入する。

解答

まず、輪状に並んだ n 個の面を q 色で、隣り合う面が同色にならないように塗る数を確認しておく。最初の面の色を1つ固定し、m 番目の面の色が最初の面と異なる塗り方の数を Bm とする。最初の面と同じ色になる塗り方の数を Am とすると Am+Bm=(q−1)m−1 であり、m+1 番目が最初の面と異なるようにするには、m 番目が最初の面と同じなら q−1 通り、異なるなら q−2 通りである。したがって Bm+1=(q−1)Am+(q−2)Bm=(q−1)m−Bm となる。B1=0 から帰納的に Bm=(q−1)m+(−1)m(q−1)q が得られる。輪にするには最後の面が最初の面と異なればよいので、最初の色の選び方 q 通りを掛けて、輪状の n 個の面の塗り方は qBn=(q−1)n+(−1)n(q−1) 通りである。

(1) n 角柱には、n 個の側面と2つの底面がある。2つの底面は互いには隣り合わないが、各底面はすべての側面と隣り合う。したがって、まず2つの底面の色の関係で分ける。

底面2つが同色である場合を考える。その色の選び方は k 通りである。側面はどれも底面と隣り合うため、その底面の色を使えない。したがって側面では残り k−1 色を使い、輪状に並んだ n 個の側面を隣り合う側面が異色になるように塗る。この数は、上の公式で q=k−1 として (k−2)n+(−1)n(k−2) である。よってこの場合は k{(k−2)n+(−1)n(k−2)} 通りである。

次に、底面2つが異色である場合を考える。2つの底面の色の選び方は k(k−1) 通りである。側面はどちらの底面とも隣り合うので、底面で使った2色を使えない。したがって側面で使える色は k−2 色であり、輪状の側面の塗り方は (k−3)n+(−1)n(k−3) 通りである。この場合は k(k−1){(k−3)n+(−1)n(k−3)} 通りである。

以上より Pk=k{(k−2)n+(−1)n(k−2)}+k(k−1){(k−3)n+(−1)n(k−3)} である。 k=2 のときは、底面が同色でも異色でも側面を適切に塗ることができず、式からも P2=0 である。 k=3 のときは P3=3{1n+(−1)n⋅1}+6{0n+(−1)n⋅0} である。n≧3 なので 0n=0 であり、P3=3{1+(−1)n} となる。したがってP2=0,P3={6(n が偶数),0(n が奇数)である。

(2) n=7, k=4 を上の式に代入する。まず底面2つが同色の場合は 4{27+(−1)7⋅2}=4(128−2)=504 通りである。底面2つが異色の場合は、側面で使える色が2色しかなく、奇数個の輪を2色で交互に塗ることはできない。式でも 4⋅3{17+(−1)7⋅1}=12(1−1)=0 である。よって P4=504 である。

別解

解法2

方針

底面2枚が同色か異色かで分ける点は保ちつつ、側面の輪の彩色数を漸化式から導く。最初の側面と同色で終わる列・異色で終わる列の2状態を追い、輪 Cn の彩色数を証明してから各値を代入する。

解答

側面の輪を q 色で塗る数を Qn(q) とする。最初の側面の色を固定し、長さ r の列について、末尾が最初と同色の数を Ar、異色の数を Br と置くとAr+1=Br,Br+1=(q−1)Ar+(q−2)Br,A1=1,B1=0.この漸化式から帰納的にBn=(q−1)n+(−1)n(q−1)qを得る。輪を閉じるには末尾が最初と異色であればよく、最初の色は q 通りだから、通常の輪の彩色数はQn(q)=(q−1)n+(−1)n(q−1)である。

(1)
底面2枚が同色なら、その色の選び方は k 通り、側面は残る k−1 色で塗る。異色なら底面は k(k−1) 通り、側面は残る k−2 色で塗る。従ってPk=kQn(k−1)+k(k−1)Qn(k−2).k=2,3 を代入してP2=0,P3={6(n が偶数),0(n が奇数)を得る。

(2)
n=7,k=4 ではP4=4(27−2)+12(17−1)=504.

総評

難度7、計算量6。角柱の面の隣接関係をグラフとして正しく捉える場合の数である。想定時間は25分程度。2つの底面は互いには隣接しないが、どちらも全側面に接するため、底面が同色か異色かで側面に許される色数が変わる。側面は一直線ではなく輪なので、端の条件を忘れると大きく数え過ぎる。特に n=7,k=4 の異色底面の場合、側面が2色で奇数輪になるため0通りになる点は、式だけでなく意味からも確認しておきたい。 主解法と第2解法を別々に再計算し、条件範囲、端点、等号成立条件まで照合した。

Evolton Pro

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

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

出典: 京都大学 1999年度 前期 文系 第5問(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。