Problem

Source: RMO 2017 P4

Tags: combinatorics, pigeonhole principle



Consider \(n^2\) unit squares in the \(xy\) plane centered at point \((i,j)\) with integer coordinates, \(1 \leq i \leq n\), \(1 \leq j \leq n\). It is required to colour each unit square in such a way that whenever \(1 \leq i < j \leq n\) and \(1 \leq k < l \leq n\), the three squares with centres at \((i,k),(j,k),(j,l)\) have distinct colours. What is the least possible number of colours needed?