2025 年广州预赛

解答

把 $n+1$ 条竖线段依次编号为 $0,1,\dots ,n$。每个相邻编号对之间有上、下两条横线段。选定两条红色竖线段后，凡是至少有一个端点落在这两个编号上的横线段都不能染红，其余横线段可独立选择是否染红。

设被禁止的相邻编号对共有 $r$ 个，则可自由选择的横线段有 $2(n-r)$ 条，对应 $4^{n-r}$ 种染法。两条竖线段的位置分类如下：

其中 $r=2$ 的三对为两个边界相邻对以及最左、最右竖线段组成的一对；$r=3$ 包括内部相邻对和“一个边界、一个不相邻内部位置”的点对；$r=4$ 对应两个不相邻的内部位置。

因此所求染法数为