Problem

Source: RMO 2018 P4

Tags: combinatorics



Let $E$ denote the set of $25$ points $(m,n)$ in the $\text{xy}$-plane, where $m,n$ are natural numbers, $1\leq m\leq5,1\leq n\leq5$. Suppose the points of $E$ are arbitrarily coloured using two colours, red and blue. SHow that there always exist four points in the set $E$ of the form $(a,b),(a+k,b),(a+k,b+k),(a,b+k)$ for some positive integer $k$ such that at least three of these four points have the same colour. (That is, there always exist four points in the set $E$ which form the vertices of a square with sides parallel to the axes and having at least three points of the same colour.)