NMO Selection Tests

Let $(i, j)$ denote the cell on the $i$-th row and the $j$-th column, where $(1, 1)$ is the lower left cell. The required minimum is $n-1$ and is achieved by placing the monsters in the cells $(k, n-k+1), k=2, \dots, n$, to force Turbo move rightwards from $(1, 1)$ to $(1, n)$ and thence upwards to $(n, n)$.

To prove that the $n \times n$ array must contain at least $n-1$ monsters, induct on $n$. The base case, $n=2$, is trivial.

For the inductive step, let $n \ge 3$. If necessary, switch rows and columns to assume that Turbo first moves upwards to $(2, 1)$. Note that Turbo enters $(n, n)$ either from $(n, n-1)$ or from $(n-1, n)$.

Case 1. Turbo visits $(n, n-1)$. Consider the subarray $\{(i, j) : 2 \le i \le n, 1 \le j \le n-1\}$. As it inherits uniqueness of a safe path for Turbo, it contains at least $n-2$ monsters, by the induction hypothesis. Furthermore, the path from $(1, 1)$ to $(n, n)$ lying outside the subarray must contain at least one monster, for otherwise it would have offered an alternative to Turbo, contradicting uniqueness. Consequently, the $n \times n$ array contains at least $(n-2)+1 = n-1$ monsters, as desired. This establishes Case 1.

Case 2. Turbo visits $(n-1, n)$. Note that $(2, 1)$ and $(n-1, n)$ are separated by the diagonal joining the lower left cell to the upper right cell, so Turbo's safe path must cross this diagonal at some (unique) cell $(k, k)$, where $2 \le k \le n-1$.

Consider the subarrays $\{(i, j) : 1 \le i, j \le k\}$ and $\{(i, j) : k \le i, j \le n\}$. They both inherit uniqueness of a safe path for Turbo, so the former contains at least $k-1$ monsters and the latter at least $n-k$, accounting for at least $(k-1)+(n-k) = n-1$ monsters in the $n \times n$ array, as desired. This establishes Case 2 and completes the solution.