Problem 5

Let

n

be a positive integer. There are

n(n+1)

rooms arranged in an

(n+1)\times n

grid. Between every two adjacent rooms there is a door. Find the number of ways to choose a subset of doors and lock them so that there exist two rooms

S

and

G

satisfying: (i)

S

is in the first row and

G

is in the

(n+1)

-th row. (ii)

G

can be reached from

S

using only unlocked doors.

Step 1 of 5: Reduce to a graph-reachability count

Previous step Next step

\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)

Detailed analysis

Since $S$ may be any room of the first row and $G$ any room of the last row, whether a suitable pair exists does not depend on which of the $n-1$ doors joining rooms within the first row, or the $n-1$ within the last row, are locked; there are $2(n-1)$ such free doors in total. Collapsing the first row to a single vertex $A$ and the last row to a single vertex $B$ , the remaining rooms and doors form a graph $\mathcal{G}$ with $n^2+(n-1)^2$ edges, and the problem reduces to counting subsets $H$ of these edges for which $A$ and $B$ are connected in $H$ .