第5题

设

n

为正整数。有

n(n+1)

个房间排成一个

(n+1)\times n

的方格阵。每两个相邻房间之间有一扇门。求选取一个门的子集并将其锁上的方法数，使得存在两个房间

S

与

G

满足： (i)

S

在第一行，

G

在第

(n+1)

行。 (ii) 只用未锁的门就能从

S

到达

G

。

第 3/5 步：

H

连通

A,B

当且仅当

f(H)

不连通

上一步下一步

H\text{ achievable} \iff f(H)\text{ not achievable}

详细分析

若 $A$ 与 $B$ 在 $H$ 中连通，则称 $H$ 可达。若 $H$ 通过边集 $p_1,\dots,p_k$ 可达，则由 $f$ 的构造， $p_1,\dots,p_k$ 中任何边都不属于 $f(H)$ ，于是 $f(H)$ 中从 $A$ 到 $B$ 的任何路径都必须在不使用这些边的情况下穿过其中之一，这不可能；故 $f(H)$ 不可达。反之，若 $H$ 不可达，则 $H$ 中 $A$ 所在连通分量向外的边都不在 $H$ 中，将它们在 $f$ 下转置即得到 $f(H)$ 中连接 $A$ 与 $B$ 的一条连通边链；故 $f(H)$ 可达。因此 $H$ 可达当且仅当 $f(H)$ 不可达。