Problem

Source: Romania TST 2016 Day 2 P4

Tags: combinatorics



Given any positive integer $n$, prove that: (a) Every $n$ points in the closed unit square $[0,1]\times [0,1]$ can be joined by a path of length less than $2\sqrt{n}+4$; and (b) There exist $n$ points in the closed unit square $[0,1]\times [0,1]$ that cannot be joined by a path of length less than $\sqrt{n}-1$.