NMO Selection Tests for the Balkan and International Mathematical Olympiads

We first show that there exists a rectangle with monochromatic vertices, then subdivide it into $n^2$ rectangles by subdividing each side into $n$ congruent segments, and show that (at least) one of these smaller rectangles has (at least) three monochromatic vertices – here is where the assumption that $n$ be odd comes in. To find a rectangle with monochromatic vertices, consider a line $a$ in the plane and a five-element monochromatic subset $A$ of $a$. Project $A$ orthogonally on another line $b$ which is parallel to $a$, and consider a three-element monochromatic subset $B$ of the image of $A$ under projection. If the colours of $A$ and $B$ agree, we are done. Otherwise, project $B$ on a third line $c$ which is parallel to both $a$ and $b$, and consider a two-element monochromatic subset $C$ of the image of $B$ under projection. Clearly, the two points of $C$ together with their orthogonal projections on either $A$ or $B$ are monochromatic. Without loss of generality, we may (and will) assume that the vertices of the square $[0,n]\times [0,n]$ are monochromatic. Since $n$ is odd, and the points $0\times 0$ and $n\times 0$ (respectively, $0\times n$) are monochromatic, there exists $p$ (respectively, $q$) in $\{0,1,\dots ,n-1\}$ such that the points $p\times 0$ and $(p+1)\times 0$ (respectively, $0\times q$ and $0\times (q+1)$) be monochromatic. We now show that (at least) one of the unit squares $$[i,i+1]\times [q,q+1],i=0,1,\dots ,p,$$ $$[p,p+1]\times [j,j+1],j=0,1,\dots ,q,$$ has (at least) three monochromatic vertices. Suppose that each of the first $p$ (respectively, $q$) horizontal (respectively, vertical) unit squares above has two vertices of each colour. Then the colours of the lattice points alternate in the same way along both horizontal segments $[0,p]\times q$ and $[0,p]\times (q+1)$, according to the parity of the abscissae, and in the same way along both vertical segments $p\times [0,q]$ and $(p+1)\times [0,q]$, according to the parity of the ordinates. Consequently, the vertical pair $(p\times q,p\times (q+1))$ and the horizontal pair $(p\times q,(p+1)\times q)$ are both monochromatic; that is, the unit square $[p,p+1]\times [q,q+1]$ has (at least) three monochromatic vertices.