MathLabs

第5题

设 nn 为正整数。有 n(n+1)n(n+1) 个房间排成一个 (n+1)×n(n+1)\times n 的方格阵。每两个相邻房间之间有一扇门。求选取一个门的子集并将其锁上的方法数，使得存在两个房间 SS 与 GG 满足： (i) SS 在第一行，GG 在第 (n+1)(n+1) 行。 (ii) 只用未锁的门就能从 SS 到达 GG。
第 1/5 步：归约为图的可达性计数
上一步下一步
collapse row 1→A, row n+1→B;∣E(G)∣=n2+(n−1)2,free doors=2(n−1)\text{collapse row }1\to A,\ \text{row }n{+}1\to B;\quad |E(G)|=n^2+(n-1)^2,\quad \text{free doors}=2(n-1)
详细分析

由于 SS 可以是第一行的任意房间，GG 可以是最后一行的任意房间，是否存在合适的一对与第一行内部相连的 n−1n-1 扇门、以及最后一行内部的 n−1n-1 扇门是否上锁无关；这样的自由门共有 2(n−1)2(n-1) 扇。将第一行收缩为一个顶点 AA，最后一行收缩为一个顶点 BB，其余房间与门构成一个图 G\mathcal{G}，共有 n2+(n−1)2n^2+(n-1)^2 条边，问题归结为计数这些边的子集 HH，使得 AA 与 BB 在 HH 中连通。