Finding the smallest integer for filling a m×n board with consecutive integers in each row and column

Question

Let $m$ and $n$ be positive integers. Find the smallest positive integer $s$ for which there exists an $m \times n$ rectangular array of positive integers such that:

1. Each row contains $n$ distinct consecutive integers in some order,
2. Each columm contains $m$ distinct consecutive integers in some order,
3. Each entry is less than or equal to $s$

For example, $$\begin{bmatrix} 1 & 2 & 4 & 3\\ 2 & 1 & 3 & 4 \end{bmatrix} $$ is a legal (and in fact minimal in terms of $s$) solution when $m = 2, n=4$.

I can show that if $m=n$ then the answer is $m$. But can someone help me with the other cases?

Answer 1

I think there may be a point of confusion over the word 'consecutive'. I believe it is a universal understanding that it means each successive integer is one more than the preceding one, i.e that the values are $N, N+1, N+2, ..., N+K$ for some $N, K.$ In that case, assuming the (say) upper-left corner of the matrix is $1$, then the value of $s$ is $(m + n - 1)$. Example for $m=3$, $n=4$:

 1 2 3 4
 2 3 4 5
 3 4 5 6

If you mean something else, please clarify.

Answer 2

I give a partial answer (an upper bound on $s$ which I also believe is the lower bound).

Claim: $s \leq m + n - \gcd(m,n)$

Proof: Let $g:= \gcd(m,n)$. Divide the matrix into square blocks of size $g$. Write $m = r g, n = c g$, so $r$ is the number of block rows and $c$ is the number of block columns. Denote each block as $B_{i,j}$, so our original rectangular array can be written as such.

$$\begin{bmatrix} B_{1,1} &\dots &B_{1,c}\\ \vdots & &\vdots\\ B_{r,1} &\dots & B_{r,c} \end{bmatrix} $$

Note that each block is square, and so given any $k$ consecutive numbers, a block can be legally filled by filling the first row with the given numbers, and then applying consecutive cyclic shifts to the numbers to fill each subsequent row.

A solution can always be obtained by filling the blocks as follows. Start in the upper left corner and then fill each diagonal as follows. Fill the upper left block with $\{1,\dots,g\}$, then fill blocks $B_{1,2}$ and $B_{2,1}$ with the numbers $\{g+1, \dots, 2g\}$, etc. In general, fill block $B_{i,j}$ with the numbers $\{ (i+j-2)g + 1, \dots, (i+j-2)g + g\}$. The maximum number reached will be in block $B_{r,c}$, and it will be $(r+c-2)g + g = m + n - g$.

Answer 3

Letting $a_{i,j}$ denote the number in the $i$th row, $j$th column, we see by looking at the first row that $$ a_{1,n} - a_{1,1} = n-1. $$

Similarly, looking at the last column, we see that $$ a_{m, n} - a_{1,n} = m-1. $$ Adding these together, we get that $$ a_{m,n} - a_{1,1} = n + m - 2. $$ So if $a_{1,1} = 1$, then $a_{m,n} = 1 + (n-1) + (m-1) = n + m - 1$.

So to fill up the whole array, you need the numbers $1, 2, \ldots, n+m-1$.