The South African Mathematical Olympiad Third Round

Suppose that $n$ squares have been coloured green, no two of them in the same row. This leaves $n-1$ empty squares in each row, which means that there are $(n-1{)}^n$ ways to colour $n$ of the remaining $n^2-n$ squares blue such that there are no two blue squares in the same row.

On the other hand, let $x_i$ be the number of squares in column $i$ that have not been coloured green. Clearly, $x_1+x_2+\cdots +x_n=n^2-n$. The number of ways to colour $n$ of the remaining $n^2-n$ squares blue in such a way that there are no two blue squares in the same column is $$x_1{x}_2\cdots x_n\le {\left(\frac{x_1+x_2+\cdots +x_n}{n}\right)}^n={\left(\frac{n^2-n}{n}\right)}^n=(n-1{)}^n$$ by the inequality between the arithmetic and geometric mean. For some configurations (e.g., all green squares in one column), this holds with strict inequality.

Hence we can conclude that there are more possible colourings for which there are no two green squares and no two blue squares in the same row than there are colourings for which there are no two green squares in the same row and no two blue squares in the same column.