MathDB

A matrix

A=(a_{ij})

is called nice, if it has the following properties: (i) the set of all entries of

A

\{1,2,\dots,2t\}

for some integer

t

; (ii) the entries are non-decreasing in every row and in every column:

a_{i,j} \le a_{i,j+1}

and

a_{i,j} \le a_{i+1,j}

; (iii) equal entries can appear only in the same row or the same column: if

a_{i,j}=a_{k,\ell}

, then either

i=k

j=\ell

; (iv) for each

s=1,2,\dots,2t-1

, there exist

i \ne k

and

j \ne \ell

such that

a_{i,j}=s

and

a_{k,\ell}=s+1

.
Prove that for any positive integers

m

and

n

, the number of nice

m \times n

matrixes is even. For example, the only two nice

2 \times 3

matrices are

\begin{pmatrix} 1 & 1 & 1\\2 & 2 & 2 \end{pmatrix}

and

\begin{pmatrix} 1 & 1 & 3\\2 & 4 & 4 \end{pmatrix}

9