Идея построения ломаной ясна из рисунка 1: мы делим квадрат на $n$ вертикальных полосок и затем обходим все точки «змейкой»: первую слева полоску проходим сверху вниз, следующую — снизу вверх и т. д. Сумма длин звеньев ломаной не больше суммы длин их проекций на вертикальную и горизонтальную стороны квадрата. Сумма вертикальных проекций, как легко видеть, не превосходит $n$, а сумму горизонтальных проекций можно оценить так. Горизонтальная проекция звена, не пересекающего границ полосок, не превосходит $\dfrac1n$, а проекция звена, пересекающего $k$ вертикальных отрезков границ полосок, не превосходит $\dfrac{k+1}{n}=\dfrac{k}{n}+\dfrac{1}{n}$. Общее число вертикальных границ полосок равно $n-1$, поэтому сумма всех $n^2-1$ горизонтальных проекций не больше
$$
\dfrac{n^2-1}{n}+\dfrac{n-1}{n}=n+1-\dfrac2n \le n+1.
$$
Таким образом, для длины всей ломаной мы получаем оценку $2n+1$.
Рис. 1
Задача а) решена, а чтобы доказать б), надо улучшить оценку на 1.
Для этого слегка изменим нашу конструкцию. Разделим квадрат на $n$ полос разной ширины ($h_1$, $h_2$, $\ldots$, $h_n$) так, чтобы в каждой полосе было ровно по $n$ точек («граничные» точки можно относить и влево, и вправо). Соединим все верхние точки полос и все нижние точки отрезками попеременно красного и синего цветов (рис. 2). Мы можем выбрать начало ломаной-змейки так, чтобы она прошла либо по всем синим отрезкам, либо по всем красным. Сумма горизонтальных проекций $2(n-1)$ красных и синих отрезков ломаной вместе не больше 2; если мы выберем тот цвет, для которого эта сумма меньше 1, то получим для суммы всех горизонтальных проекций оценку
$$
(n-1)(h_1+h_2+\ldots+h_n)+1\le n.
$$
Сумма вертикальных проекций, как и прежде, не больше $n$.
Рис. 2
Итак, мы построили ломаную длины не больше $2n$, — решили б).
Пример «плотного» расположения точек в вершинах треугольной решётки (рис. 3; при большом $n$, чтобы уместить в квадрате $1\times1$ $n^2$ точек, нужно взять длину стороны треугольничка, равной примерно $\sqrt{2/{\sqrt3}}/n$) показывает, что константу 2 в условии задачи заведомо нельзя (даже для больших $n$) заменить числом, меньшим $\sqrt{2/{\sqrt3}}$.
Рис. 3
