Question 5
Let $n$ be a positive integer. There are $n(n+1)$ rooms arranged in an $(n+1)\times n$ grid. Every pair of adjacent rooms has a door between them. Find the number of ways to choose a subset of doors to lock such that there exist two rooms $S,G$ satisfying:
1. $S$ is in the first row and $G$ is in the $(n+1)$st row.
2. One can reach $G$ from $S$ using only unlocked doors.
1. $S$ is in the first row and $G$ is in the $(n+1)$st row.
2. One can reach $G$ from $S$ using only unlocked doors.