67th NMO Selection Tests for BMO and IMO

a) Let $C$ be an $n$-point configuration in the closed unit square $[0,1]\times [0,1]$, let $m=\lfloor \sqrt{n}\rfloor$, and consider the snake going horizontally from $0\times 0$ to $1\times 0$, then vertically up from $1\times 0$ to $1\times 1/m$, then horizontally back from $1\times 1/m$ to $0\times 1/m$, vertically up from $0\times 1/m$ to $0\times 2/m$, horizontally over to $1\times 2/m$, and so on and so forth all the way up to $1\times 1$ or $0\times 1$, depending on whether $m$ is even or odd. The length of the snake is $m+1+m\cdot 1/m=m+2\le \sqrt{n}+2$. Of course, the snake does not necessarily pass through any point in $C$, but it comes within $1/(2m)$ of $C$. Thus, in tracing the snake, visit each point of $C$ by darting out, if necessary, to the nearest points in $C$ abreast within $1/(2m)$, and then dart back. This increases the length by at most $n\cdot 2\cdot 1/(2m)=n/m<\sqrt{n}+2$, so the length of the visiting path is certainly less than $2\sqrt{n}+4$.

b) Let again $m=\lfloor \sqrt{n}\rfloor$, and consider an $n$-point subconfiguration $C$ of the lattice $\{i/m\times j/m:i,j=0,1,\dots ,m\}$. Since any two distinct points in the lattice are at least $1/m$ distance apart, the length of a path through all of $C$ is at least $(n-1)\cdot 1/m\ge (n-1)/\sqrt{n}\ge \sqrt{n}-1$.