2026 年中科大少年班入围考 · 第 19 题

解答

固定首顶点颜色。记前 $k$ 个相邻异色顶点中，末色等于首色的方案数为 $A_k$，末色异于首色的为 $B_k$。有 $A_1=1,B_1=0$，且

总链数为 $A_k+B_k=2^{k-1}$，由此解得

闭环必须末色异于首色，首色本身又有三种选择，所以染色方式为 $\boxed{2^n+2(-1{)}^n}$（$n\ge 3$）。