Q5 Matemática  (Romanian Masters of Mathematics Collection 2012)

Dado um inteiro positivo $n\ge 3$, pinte cada célula de um array quadrado $n\times n$ com uma das cores $\lfloor (n+2{)}^2/3\rfloor$, cada cor sendo usada pelo menos uma vez. Prove que existe um subarranjo retangular $1\times 3$ ou $3\times 1$ cujas três células são coloridas com três cores diferentes. (Rússia) Ilya Bogdanov, Grigory Chelnokov, Dmitry Khramtsov