Question 148
Let $n$ be a positive integer. Denote by $S_n$ the set of points $(x, y)$ with integer coordinates such that
$$
|x| + \left|y + \frac{1}{2}\right| \lt n.
$$
A path is a sequence of distinct points $(x_1, y_1), (x_2, y_2), \dots, (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \dots, \ell$, the distance between $(x_i, y_i)$ and $(x_{i-1}, y_{i-1})$ is 1 (in other words, the points $(x_i, y_i)$ and $(x_{i-1}, y_{i-1})$ are neighbors in the lattice of points with integer coordinates).
Prove that the points in $S_n$ cannot be partitioned into fewer than $n$ paths (a partition of $S_n$ into $m$ paths is a set $\mathcal{P}$ of $m$ nonempty paths such that each point in $S_n$ appears in exactly one of the $m$ paths in $\mathcal{P}$).
$$
|x| + \left|y + \frac{1}{2}\right| \lt n.
$$
A path is a sequence of distinct points $(x_1, y_1), (x_2, y_2), \dots, (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \dots, \ell$, the distance between $(x_i, y_i)$ and $(x_{i-1}, y_{i-1})$ is 1 (in other words, the points $(x_i, y_i)$ and $(x_{i-1}, y_{i-1})$ are neighbors in the lattice of points with integer coordinates).
Prove that the points in $S_n$ cannot be partitioned into fewer than $n$ paths (a partition of $S_n$ into $m$ paths is a set $\mathcal{P}$ of $m$ nonempty paths such that each point in $S_n$ appears in exactly one of the $m$ paths in $\mathcal{P}$).