Evolton
方針
2つの底面は互いには隣り合わず、各底面はすべての側面と隣り合う。そこで底面2つが同色か異色かで分ける。底面の色を決めると、側面で使える色数がそれぞれ , に決まり、側面 枚は輪状に並ぶので、輪 を 色で隣り合う面が異色になるように塗る数 を使う。この公式を側面に適用し、最後に および を代入する。
解答
まず、輪状に並んだ 個の面を 色で、隣り合う面が同色にならないように塗る数を確認しておく。最初の面の色を1つ固定し、 番目の面の色が最初の面と異なる塗り方の数を とする。最初の面と同じ色になる塗り方の数を とすると であり、 番目が最初の面と異なるようにするには、 番目が最初の面と同じなら 通り、異なるなら 通りである。したがって となる。 から帰納的に が得られる。輪にするには最後の面が最初の面と異なればよいので、最初の色の選び方 通りを掛けて、輪状の 個の面の塗り方は 通りである。
(1) 角柱には、 個の側面と2つの底面がある。2つの底面は互いには隣り合わないが、各底面はすべての側面と隣り合う。したがって、まず2つの底面の色の関係で分ける。
底面2つが同色である場合を考える。その色の選び方は 通りである。側面はどれも底面と隣り合うため、その底面の色を使えない。したがって側面では残り 色を使い、輪状に並んだ 個の側面を隣り合う側面が異色になるように塗る。この数は、上の公式で として である。よってこの場合は 通りである。
次に、底面2つが異色である場合を考える。2つの底面の色の選び方は 通りである。側面はどちらの底面とも隣り合うので、底面で使った2色を使えない。したがって側面で使える色は 色であり、輪状の側面の塗り方は 通りである。この場合は 通りである。
以上より である。 のときは、底面が同色でも異色でも側面を適切に塗ることができず、式からも である。 のときは である。 なので であり、 となる。したがってである。
(2) , を上の式に代入する。まず底面2つが同色の場合は 通りである。底面2つが異色の場合は、側面で使える色が2色しかなく、奇数個の輪を2色で交互に塗ることはできない。式でも である。よって である。
別解
解法2
方針
底面2枚が同色か異色かで分ける点は保ちつつ、側面の輪の彩色数を漸化式から導く。最初の側面と同色で終わる列・異色で終わる列の2状態を追い、輪 の彩色数を証明してから各値を代入する。
解答
側面の輪を 色で塗る数を とする。最初の側面の色を固定し、長さ の列について、末尾が最初と同色の数を 、異色の数を と置くとこの漸化式から帰納的にを得る。輪を閉じるには末尾が最初と異色であればよく、最初の色は 通りだから、通常の輪の彩色数はである。
(1)
底面2枚が同色なら、その色の選び方は 通り、側面は残る 色で塗る。異色なら底面は 通り、側面は残る 色で塗る。従って を代入してを得る。
(2)
では
総評
難度7、計算量6。角柱の面の隣接関係をグラフとして正しく捉える場合の数である。想定時間は25分程度。2つの底面は互いには隣接しないが、どちらも全側面に接するため、底面が同色か異色かで側面に許される色数が変わる。側面は一直線ではなく輪なので、端の条件を忘れると大きく数え過ぎる。特に の異色底面の場合、側面が2色で奇数輪になるため0通りになる点は、式だけでなく意味からも確認しておきたい。 主解法と第2解法を別々に再計算し、条件範囲、端点、等号成立条件まで照合した。