Problem

Source: Stars Of Mathematics 2009 p5

Tags: combinatorics, Coloring, Color problem, linear algebra, matrix



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. Iurie Boreico (Moldova)