APMO 2026 Problem 5

Let $n$ be a positive integer. There exist $n(n+1)$ rooms arranged in a $(n+1) \times n$ grid. For each two adjacent rooms, there is a door between them. Find the number of ways to choose a subset of doors and lock them such that there are two rooms $S$ and $G$ satisfying the following properties:

(i) $S$ is in the first row and $G$ is in the $(n+1)$-th row.

(ii) One can reach $G$ from $S$ only through unlocked doors.