Unfriendly neighbours

Consider the numbers $\color{#20A900}{\text{1 to 381}}$ and $\color{#20A900}{\text{1200 to 1600}}$ .

The numbers $\color{#20A900}{\text{1 to 381}}$ must be in at least 20 roles while the numbers $\color{#20A900}{\text{1200 to 1600}}$ must be in at least 21 roles. So, one of the numbers from $\color{#20A900}{\text{1 to 381}}$ must be in the same role as one of the numbers $\color{#20A900}{\text{1200 to 1600}}$ .

$\color{#20A900}{\text{1200-381=819.}}$

But we are not done.

To show 819 is possible, imagine that the 40 by 40 square is cut along the middle vertical line into 2 20 by 40 rectangles. Then, in one of the 20 by 40 rectangles, place the numbers $\color{#D61F06}{\text{1 to 800}}$ in order. I.e. first row is 1,2,3,...20. Second row is 21,22,...40.

Then, in the other 20 by 40 rectangle, place the number $\color{#D61F06}{\text{801 to 1600}}$ in a similar way.

Then the 40 by 40 rectangle would be:

1st row: 1,2,...,20,800,801,802,803,...820

2nd row: 21.22.23... 821,822,...840

Since the maximum and minimum number both increases by 20, the maximum difference for each row is 819.

1st column: 1,21,41,61...781

2nd column: 2,22,42,62...782

21st column: 801,821,841,...1581

22nd column: 802,822,842,...1582

Here, since the maximum and minimum value increases by 1. the maximum difference for each column is 781-1=780.

And thus 819 is possible and the maximum value of N.

For a set of integers $S \subset \{1, 2, \cdots , 1600\},$ let $r(S), c(S)$ be the smallest integers $r(S)$ and $c(S)$ such that all numbers in $S$ appear a $r(S) \times c(S)$ subgrid. Notice that a total of $r(S)c(S)$ numbers appear in those $r(S)$ rows and $c(S)$ columns, so $r(S)c(S) \geq |S| \implies r(S) + c(S) \geq 2 \sqrt{|S|}.$ Let $S_1= \{1, 2, \cdots , 381\}.$ It's easy to verify that

$\left( \dfrac{39}{2} \right) ^2 < |S_1| \implies 39 < 2 \sqrt{|S_1|} \implies r(S_1) + c(S_1) > 39 \\ \implies r(S_1) + c(S_1) \geq 40.$

Let $S_2= \{1200, 1201, \cdots , 1600\}.$ Notice that $|S_2| = 401 > 400 \implies 2|S_2| > 40 \implies r(S_2) + c(S_2) > 40.$ Combining them, we find out that $r(S_1) + r(S_2) + c(S_1) + c(S_2) > 80.$ Hence, $\max \{r(S_1) + r(S_2), c(S_1) + c(S_2)\} > 40.$ WLOG assume $r(S_1) + r(S_2) > 40$ (otherwise flip the board by $90^{\circ}$ ).

Since $r(S_1) + r(S_2)$ exceeds the total number of rows, some of these rows must overlap, so there must exist a $a \in S_1$ and $b \in S_2$ in the same row. But, the minimum of $b-a$ is $1200- 381 = 819,$ so there must exist two numbers in the same row differing by at least $819$ .

Consider a board where the $i^{\text{th}}$ row and $j^{\text{th}}$ column has the number $20(i-1)+j$ written on it if $j \leq 20$ and $720 + 20i + j$ if $j>20$ . It is easy to see that this construction ensures that the difference between any two numbers doesn't exceed $819$ .

Hence, our answer is $\boxed{819}.$

Got what the question asked for, here is the formula:

T (n+2) = T (n) + 2 n + 3 where T (0) = 2, {T (1) = 0}

T (40) = 819.

Answer wanted is 819.