The South African Mathematical Olympiad Third Round

Split the table into four smaller tables of size $n\times n$. The upper left quarter is now filled with $1$s, the lower right quarter with $-1$s, and each of the remaining two quarters in a checkerboard pattern (if $n$ is odd, fill them in such a way that one of the quarters contains more $1$s than $-1$s, and the other more $-1$s than $1$s). If $n$ is even, then each of the rows and columns contains either $n/2$ $1$s and $3n/2$ $-1$s, or vice versa, so that $M=n$. If $n$ is odd, then each of the rows and columns contains either $(n-1)/2$ $1$s ($-1$s) and $(3n+1)/2$ $-1$s ($1$s), or $(n+1)/2$ $1$s ($-1$s) and $(3n-1)/2$ $-1$s ($1$s); it follows that $M=n-1$ in this case.

Now we show that $M$ cannot be larger. If there is a row or column that contains as many $1$s as $-1$s, then $M=0$, and we are done. Otherwise, split the set of all $4n$ rows and columns into two subsets: those that contain more $1$s than $-1$s, and those that contain more $-1$s than $1$s.

One of these two sets must contain at least $2n$ elements. Without loss of generality, assume that there are at least $2n$ rows and columns (of which $k$ are rows and $\ell$ columns) that contain more $1$s than $-1$s. In each of these rows and columns, there are at least $n+M/2$ $1$s and at most $n-M/2$ $-1$s. The total number of $1$s in all these rows and columns is therefore at least $$(k+\ell )\left(n+\frac{M}{2}\right)-k\ell ,$$ where the last term accounts for those $1$s that are possibly double-counted. Hence we have $$2n^2\ge (k+\ell )\left(n+\frac{M}{2}\right)-k\ell \ge (k+\ell )\left(n+\frac{M}{2}\right)-\frac{1}{4}(k+\ell {)}^2$$ and thus, with $r=k+\ell$, $$M\le \frac{2n^2+r^2/4-rn}{r/2}=\frac{4n^2}{r}+\frac{r}{2}-2n=n-\frac{(r-2n)(4n-r)}{2r}\le n,$$ since $2n\le r\le 4n$ by assumption. Hence we have $M\le n$, which completes the proof in the case that $n$ is even. If $n$ is odd, $M=n$ is impossible, since all row sums and all column sums must be even (sum of an even number of odd numbers), so that we must have $M\le n-1$.

We conclude that the largest possible value of $M$ is $n$ if $n$ is even and $n-1$ if $n$ is odd.