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 4 of 5: Exactly half of the subsets are achievable

Previous step Next step

\#\{H: H\text{ achievable}\}=2^{\,n^2+(n-1)^2-1}

Detailed analysis

Since $f$ is a bijection on the $2^{n^2+(n-1)^2}$ subsets of edges of $\mathcal{G}$ that pairs each achievable $H$ with the non-achievable $f(H)$ , the achievable and non-achievable subsets are in bijection with each other and partition all $2^{n^2+(n-1)^2}$ subsets; hence exactly $2^{\,n^2+(n-1)^2-1}$ of the subsets are achievable.