, 2022

We will prove that the required smallest possible value is $n$. Let $A_i$-s are the rows and $B_j$-s are the columns of a square table $n \times n$ in which the value in row $i$ and column $j$ is $(n-1)i + j$. So all differences for the $A_i$-s are equal to $1$ and all differences for the $B_j$-s are equal to $n$.

Let $a$ be the smallest natural number such that the set $\{1, 2, \dots, a\}$ contains some of the considered $2n$ sets, $A_1$ for example. Without loss of generality, we can assume that $a \in B_1$ or $a \notin B_j$ for all $j$. Consider the numbers $a+1, a+2, \dots, a+n-2$ (which are at most $n-2$) and the sets $B_2, B_3, \dots, B_n$ (which are $n-1$). It follows from Dirichlet's principle that at least one of them, for example $B_2$, does not contain any of these numbers. Since $a \notin B_2$ (because either $a \in B_1$ and $B_1 \cap B_2 = \emptyset$, or $a \notin B_j$ for all $j$) $B_2$ contains at least one number $x \ge a+n-1$ (otherwise the set $\{1, 2, \dots, a-1\}$ contains $B_2$, which is contradiction with the minimality of $a$).
Let $b_1 > b_2 > \dots > b_m$ are the elements of $B_2$ and mark the elements of $B_2 \cap A_1$. Consider $x \ge a+n-1$, such that $b_j$ is a marked number and the number of elements (in the ordering of $B_2$) between $x$ and $b_j$ is minimal. For $x \ge b_j$ (the case $x < b_j$ is analogous) we consider the largest $b_k \le x$ of $B_2$ (not necessarily marked; $k=j$ is allowed). Obviously $b_k < a+n-1$ (otherwise we have a contradiction because the number of elements between $b_k$ and $b_j$ is less than between $x$ and $b_j$) and because $a+1, a+2, \dots, a+n-2$ are not in $B_2$, and also $a \notin B_2$ from above, we get $b_k \le a-1$. Hence $x$ and $b_k$ are adjacent elements in $B_2$ with a difference of at least $a+n-1-(a-1)=n$, as desired.