大阪星光学院高等学校２０２２年数学第４問（解答・解説）
３色以下で塗り分ける場合から２色で塗り分ける場合を取り除くという方針で解きます。
２色で塗り分ける場合は「縞模様」になるので、（２）は２色で塗り分けることができませんね。
２色での塗り分け方は、どの１色を使わないかで３通りあり、そのそれぞれに対して、１の色をどの色で塗るかで２通りあり、残りの色の塗り方は自動で確定するので、（１）、（３）いずれの場合も３×２＝６通りあります。
以下、３色以下で塗り分ける場合を考えます。
赤、青、黄をそれぞれＡ、Ｂ、Ｃとします。
Ａの次はＢまたはＣ、Ｂの次はＡまたはＣ、Ｃの次はＡまたはＢを塗ることになり、最初と最後は違う色を塗ることになります。
Ａ→Ｂ Ｂ→Ａ Ｃ→Ａ
→Ｃ →Ｃ →Ｂ
逆から考えると、
Ａの個数＝１つ前のＢの個数＋１つ前のＣの個数
Ｂの個数＝１つ前のＣの個数＋１つ前のＡの個数
Ｃの個数＝１つ前のＡの個数＋１つ前のＢの個数
となることがわかるので、機械的に処理できます。
まず、最初がＡの場合について考えると、以下の表のように、例えば、図３の場合で条件を満たすもの（Ａ以外で終わるもの）は１１×２通りあります。最初がＢ、Ｃの場合も同じだから、図３を３色以下で塗り分ける場合の数は１１×２×３通りとなります。 ←ＢとＣは条件的に同じだからです。〜条件の対等性を利用して作業を減らす！
図１、図２についても同様ですね。
１ ２ ３ ４ ５ ６
Ａ １ ０ ２ ２ ６ １０
Ｂ ０ １ １ ３ ５ １１
Ｃ ０ １ １ ３ ５ １１
（１）の塗り分け方は３×２×３−６＝１２通りあり、（２）の塗り分け方は５×２×３＝３０通りあり、（３）の塗り分け方は１１×２×３−６＝６０通りあります。
なお、同様の問題が京都大学で出されている（京都大学１９９９年前期文系数学第５問）ので、ぜひ解いてみましょう。