Square Matrix

We will show that the minimum possible value of $D$ is 1000.

First, let's find an example of $D=1000$ . Fortunately, this can be easily constructed by setting $A_{ij}=i+1000(j-1)$ . It looks like this:

$A=\begin{pmatrix} 1 & 2 & \cdots & 1000 \\ 1001 & 1002 & \cdots & 2000 \\ \vdots & \vdots & \ddots & \vdots \\ 1000^2-999 & 1000^2-998 & \cdots & 1000^2 \end{pmatrix}$

Consider the numbers being entered in sequential order. WLOG, we may assume that a row gets entirely filled before (or at the same time) a column gets entirely filled, and this happens when we add in the number $n$ . Then, consider the state of the matrix immediately after adding $n$ , which has several unfilled entries. For each column, it has at least one entry (as a row is filled), and for all but possibly the one column $n$ is in, we can ensure there is an unfilled entry present. Hence, at the moment we add $n$ we can find adjacent pairs within columns outside of $n$ 's column where one entry is filled and another entry is not filled. Let's denote these 999 pairs of entries in columns $A$ outside $n$ 's column by $\{(a_{i,\text{filled}}, a_{i,\text{unfilled}})\}$ for $1\leq i \leq 999$ .

Since we just filled in $n$ and we have chosen 999 distinct filled numbers outside of the column $n$ is in, the numbers in the filled entries $a_{i,\text{filled}}$ are all at most $n-1$ . The minimum of the filled entries is then $\min_i a_{i,\text{filled}} \leq n - 1 - 998 = n-999$ . Then, if we continue entering numbers in sequential order, the number assigned to the unfilled entry $a_{i,\text{unfilled}}$ in each of the $999$ columns is $\geq n + 1$ . Hence, the difference of these two terms in $\geq (n+1) - (n-999) = 1000$ at the minimum filled entry.

This means that in all matrices of this type, we have $D\ge 1000$ . Since we have an easy example of $D=1000$ , the answer must be $1000$ .

Of course, all of this generalizes to any size matrix, and you can even generalize to higher dimensions. (In $d$ dimensions, it should be $n^{d-1}$ if we have a $\underbrace{n\times n \times \cdots n}_{\text{d times}}$ grid).

[Credit to Calvin Lin for rephrasing the middle section for clarity]