Track / Stage 6 / 232 of 400 #1712 of 2444

Problem 1712

National Olympiad, first round

Combinatorics Difficulty 6.5 Prove it Local Mathematical Competitions · Romania

The cells of a $(n^2 - n + 1) \times (n^2 - n + 1)$ matrix are coloured using $n$ colours. A colour is called dominant on a row (or a column) if there are at least $n$ cells of this colour on that row (or column). A cell is called extremal if its colour is dominant both on its row, and its column. Find all $n \ge 2$ for which there is a colouring with no extremal cells.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

The answer is that there exist such colourings for $n = 2$ (almost trivial), and $n = 3$ (following a detailed and tedious case analysis). For $n = 4$ one must exhibit a colouring with no extremal cells (again a very tedious labor). The colourings with no extremal cells for $n \ge 5$ are built inductively, using a beautifully symmetric pattern based on the model for $n - 1$ (this being the elegant combinatorial part of the problem).

A detailed proof for this problem can be found in no. 4/2006, pages 22-25, of the on-line magazine Mathematical Reflections
http://reflections.awesomemath.org/2006_4/2006_4_solutions.pdf.

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