Baltic Way 2010 · Problem 6

Combinatorics

An $n \times n$ board is coloured in $n$ colours such that the main diagonal (from top-left to bottom-right) is coloured in the first colour; the two adjacent diagonals are coloured in the second colour; the two next diagonals (one from above and one from below) are coloured in the third colour, etc.; the two corners (top-right and bottom-left) are coloured in the $n$ -th colour. It happens that it is possible to place on the board $n$ rooks, no two attacking each other and such that no two rooks stand on cells of the same colour. Prove that $n \equiv 0(\bmod 4)$ or $n \equiv 1$ $(\bmod 4)$ .

Change pool

When you’re ready

Review material becomes available with the next Daily.

Review

Topics

Invariants and monovariants

Solutions

Solution

Use the usual coordinate system for which the cells of the main diagonal have coordinates $(k, k)$ , where $k = 1, \dots, n$ . Let $(k, f(k))$ be the coordinates of the $k$ -th rook. Then by color restrictions for rooks we have

\sum_{k=1}^{n} (f(k) - k)^2 = \sum_{i=0}^{n-1} i^2 = \frac{n(n-1)(2n-1)}{6}.

Since the rooks are non-attacking we have

\sum_{k=1}^{n} (f(k))^2 = \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}.

By subtracting these equalities we obtain

\sum_{k=1}^{n} k f(k) = \frac{n(2n^2 + 9n + 1)}{12}.

Now it is trivial to check that the last number is integer if and only if $n \equiv 0 \text{ or } 1 \pmod{4}$ .

Contest context

Results from Baltic Way 2010

10 teams

Mean score: 0.9 / 5
Scores of 4 or 5: 2 / 10
Estonia: 4 / 5

Score distribution

All team scores

Team	Score
Poland	5 / 5
Lithuania	0 / 5
Germany	0 / 5
Latvia	0 / 5
Denmark	0 / 5
Sweden	0 / 5
Estonia	4 / 5
Norway	0 / 5
Finland	0 / 5
Iceland	0 / 5

Review

Topics

Solutions

Contest context

Elsewhere