Competition problem — Combinatorics

Library / /21 of 22

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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.