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 3 of 5:

H

connects

A,B

iff

f(H)

does not

Previous step Next step

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

Detailed analysis

Call $H$ achievable if $A$ and $B$ are connected in $H$ . If $H$ is achievable via edges $p_1,\dots,p_k$ , then no edge of $p_1,\dots,p_k$ lies in $f(H)$ by construction of $f$ , so any path from $A$ to $B$ in $f(H)$ would have to cross one of these edges without using it, which is impossible; hence $f(H)$ is not achievable. Conversely, if $H$ is not achievable, the edges leaving the component of $A$ in $H$ all lie outside $H$ , and transposing them under $f$ produces a connected chain of edges of $f(H)$ joining $A$ to $B$ ; hence $f(H)$ is achievable. So $H$ is achievable exactly when $f(H)$ is not.