75th 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.