Competition problem — Combinatorics

Library / /18 of 27

Combinatorics Difficulty 6.5 National olympiad Prove it 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.

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.

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.