Kanada 2014

The answer is $m+n-2$ if $m,n\ge 3$ and $\max \{m,n\}$ if one of $m,n$ is equal to $1$.

Note that it is not possible that all rows are red-dominated and all columns are blue-dominated. This is true, since the number of rows and columns are both odd, the number of squares is odd. Hence, there are more squares of one color than the other. Without loss of generality, suppose there are more red squares than blue squares. Then it is not possible that for every column, there are more blue squares than red squares. Hence, every column cannot be blue-dominated.

If one of $m,n$ is equal to $1$, say $m$ without loss of generality, then by the claim, the answer is less than $n+1$. The example where there are $n$ blue-dominated columns is by painting every square blue. There are $0$ red-dominated rows. The sum of the two is $n=\max \{m,n\}$.

Now we handle the case $m,n\ge 3$.

There are $m$ rows and $n$ columns on the board. Hence, the answer is at most $m+n$. We have already shown that the answer cannot be $m+n$.

Since $m,n$ are odd, let $m=2a-1$ and $n=2b-1$ for some positive integers $a,b$. Since $m,n\ge 3$, $a,b\ge 2$. We first show that the answer is not $m+n-1$. By symmetry, it suffices to show that we cannot have all rows red-dominated and all-but-one column blue-dominated. If all rows are red-dominated, then each row has at least $b$ red squares. Hence, there are at least $bm=(2a-1)b$ red squares. Since all-but-one column is blue-dominated, there are at least $2b-2$ blue-dominated columns. Each such column then has at least $a$ blue squares. Therefore, there are at least $a(2b-2)$ blue squares. Therefore, the board has at least $(2a-1)b+a(2b-2)=4ab-b-2a$ squares. But the total number of squares on the board is $$(2a-1)(2b-1)=4ab-2a-2b+1=4ab-2a-b-b+1<4ab-2a-b,$$ which is true since $b\ge 2$. This is a contradiction. Therefore, the answer is less than $m+n-1$.

We now claim that there is a colouring of the board such that the number of blue-dominated columns plus the number of red-dominated rows is $m+n-2$; Colour the first column entirely red, and the first row, minus the top-left corner, entirely blue. The remaining uncoloured square is an even-by-even board. Colour the remaining board in an alternating pattern (i.e. checkerboard pattern). Hence, on this even-by-even board, each row has the same number of red squares as blue squares and each column has the same number of red squares as blue squares. Then on the whole board, since the top row, minus the top-left square is blue, all columns, but the leftmost column, are blue-dominated. Hence, there are $n-1$ blue-dominated columns. Since the left column is red, all rows but the top row are red dominated. Hence, there are $m-1$ red-dominated rows. The sum of these two quantities is $m+n-2$, as desired.