Problem

Source: Romanian Master Of Mathematics 2012

Tags: floor function, ceiling function, geometry, rectangle, combinatorics proposed, combinatorics, double counting



Given a positive integer $n\ge 3$, colour each cell of an $n\times n$ square array with one of $\lfloor (n+2)^2/3\rfloor$ colours, each colour being used at least once. Prove that there is some $1\times 3$ or $3\times 1$ rectangular subarray whose three cells are coloured with three different colours. (Russia) Ilya Bogdanov, Grigory Chelnokov, Dmitry Khramtsov