Fall Mathematical Competition

Denote by $a_{pq}$ the number in the $p$-th row and $q$-th column, by $A_0(p)$ (resp. $A_1(p)$) the number of the zeros (resp. ones) in the $p$-th row, and by $B_0(q)$ (resp. $B_1(q)$) the number of the zeros (resp. ones) in the $q$-th column.

Lemma. If exactly three of the numbers $a_{ik}$, $a_{il}$, $a_{jk}$ and $a_{jl}$, $i\ne j$, $k\ne l$, are the same, then $m=n$.

Proof. We can assume without loss of generality that $a_{ik}=a_{il}=a_{jk}=0$ and $a_{jl}=1$. Then $a_{jl}=1$ implies that $A_1(j)=B_1(l)$ and it follows from $a_{ik}=a_{il}=a_{jk}=0$ that $A_0(j)=B_0(k)=A_0(i)=B_0(l)$. Hence $A_1(j)=B_1(l)$ and $A_0(j)=B_0(l)$, which means that $m=n$.

An example of a square table ($m=n$) is the all-zero table (or the table with zeros at the main diagonal and ones in the remaining cells).

Assume now that $n>m$. It is clear that any permutation of the rows or the columns does not affect the required property. Thus we can assume that the first row begins with its ones and continues with its zeros, and similarly for the first column: it begins with its ones and continues with its zeros. Then $a_{11}=1$ shows that the ones in the first row are as much as the ones in the first column. Denote this number by $t$. Now it follows from the Lemma that $a_{pq}=1$ for every $p,q=1,2,\dots ,t$.

Case 1. Let $n>m=t$. Then $n>t$ and $a_{pq}=0$ for every $q>t$. Therefore $n-t=t$, i.e. $n=2t=2m$.

Case 2. Let $n>m>t$. If $a_{pq}=1$ for some $p>t$ and $1\le q\le t$ then the Lemma implies that $m=n$ (since $a_{pq}=a_{11}=a_{1q}=1$ and $a_{p1}=0$). Therefore $a_{pq}=0$ for $p>t$ and $1\le q\le t$. Analogously $a_{pq}=0$ for $q>t$ and $1\le p\le t$.

Assume that $a_{pq}=0$ for some $p>t$ and $q>t$. Again the Lemma shows that $m=n$, a contradiction. Hence $a_{pq}=1$ for every $p>t$ and $q>t$. Now $a_{mn}=1$ gives $m-t=n-t$, i.e. $m=n$, a contradiction.

We finally obtain that $m=n$ or $n=2m$. For the last case, an example is a table which consists of two $m\times m$ tables, one of them having only zeros, and the other only ones.