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 5 of 5: Restore the free doors to finish
Previous stepNext step
answer=2 n2+(n−1)2−1⋅22(n−1)=22n2−2\text{answer}=2^{\,n^2+(n-1)^2-1}\cdot 2^{2(n-1)}=2^{2n^2-2}
Detailed analysis

Each of the 2 n2+(n−1)2−12^{\,n^2+(n-1)^2-1} achievable choices of locks on the edges of G\mathcal{G} may be freely combined with any of the 22(n−1)2^{2(n-1)} ways of locking the doors internal to the first and last rows (Step 1), since those doors do not affect whether AA and BB are connected. This gives 22n2−22^{2n^2-2} total ways to lock doors so that some room of the first row reaches some room of the last row.