MathLabs

Problem 5

Let nn be a positive integer. There are n(n+1)n(n+1) rooms arranged in an (n+1)×n(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 SS and GG satisfying: (i) SS is in the first row and GG is in the (n+1)(n+1)-th row. (ii) GG can be reached from SS using only unlocked doors.
Step 2 of 5: Build a transpose-complement involution
Previous stepNext step
f(H):di,j∈f(H)  ⟺  dj,i∉H,ei,j∈f(H)  ⟺  ej,i∉H;f(f(H))=Hf(H):\quad d_{i,j}\in f(H)\iff d_{j,i}\notin H,\quad e_{i,j}\in f(H)\iff e_{j,i}\notin H;\qquad f(f(H))=H
Detailed analysis

Label the edges of G\mathcal{G} as di,jd_{i,j} for 1≤i,j≤n1\le i,j\le n and ei,je_{i,j} for 1≤i,j≤n−11\le i,j\le n-1, mirroring rows and columns of the grid. Define ff on subsets of edges of G\mathcal{G} by declaring, for each labelled edge, that it lies in f(H)f(H) exactly when the edge with its two indices swapped does not lie in HH. Because swapping indices twice returns the original edge and negating twice returns the original membership, f(f(H))=Hf(f(H))=H, so ff is an involution.