Library / South African Mathematical Olympiad Third Round /29 of 31

South African Mathematical Olympiad Third Round

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it South Africa

Let $n > 1$ be an integer. An $n \times n$ -square is divided into $n^2$ unit squares. Of these smaller squares, $n$ are coloured green and $n$ are coloured blue. All remaining squares are coloured white. Are there more such colourings for which there are no two green squares in a row, and no two blue squares in a column, or colourings for which there are neither two green squares in a row nor two blue squares in a column?

Solution

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 + \dots + 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.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.