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。
第 4/5 步:恰好一半的子集可达
#{H:H achievable}=2 n2+(n−1)2−1\#\{H: H\text{ achievable}\}=2^{\,n^2+(n-1)^2-1}
详细分析

由于 ff 是 G\mathcal{G} 的边的 2n2+(n−1)22^{n^2+(n-1)^2} 个子集上的双射,它把每个可达的 HH 与不可达的 f(H)f(H) 配对,故可达与不可达的子集互相双射,并将全部 2n2+(n−1)22^{n^2+(n-1)^2} 个子集划分为两部分;因此恰有 2 n2+(n−1)2−12^{\,n^2+(n-1)^2-1} 个子集可达。