Problem: Let $n$ be a positive integer.  Denote by $S_n$ the set of points $(x, y)$
with integer coordinates such that
\[ \left\lvert x\right\rvert + \left\lvert y + \half \right\rvert < 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$.

Prove that the points in $S_n$ cannot be partitioned into fewer than $n$ paths.

Solution: \paragraph{First solution (local).}
We proceed by induction on $n$.
The base case $n=1$ is clear, so suppose $n > 1$.
Let $S$ denote the set of points
\[ S = \left\{ (x,y) : x + \left\lvert y+\frac12 \right\rvert \ge n - 2  \right\}. \]
An example when $n=4$ is displayed below.
\begin{center}
\begin{asy}
int n = 4;
for (int a=-4; a<=4; ++a) {
for (int b=-4; b<=4; ++b) {
if (abs(a) + abs(b+0.5) < n) {
if (a + abs(b+0.5) > n-2) dot( (a,b), red+4 );
else dot( (a,b), black+3 );
}
}
}
draw((0,3)--(0,2)--(1,2)--(1,1)--(2,1)--(2,0)--(3,0)--(3,-1)--(2,-1)--(2,-2)--(1,-2)--(1,-3)--(0,-3)--(0,-4), red);
draw(CR((3,0), 0.3), deepgreen);
label("$a$", (3.3,0), dir(0), deepgreen);
\end{asy}
\end{center}
For any minimal partition $\mathcal P$ of $S_n$,
let $P$ denote the path passing through the point $a = (n-1,0)$.
Then the intersection of $P$ with $S$ consists of several disconnected paths;
let $N$ be the number of nodes in the component containing $a$, and
pick $\mathcal P$ such that $N$ is maximal.
We claim that in this case $P = S$.

Assume not.
First, note $a = (n-1,0)$ must be connected to $b = (n-1, -1)$
(otherwise join them to decrease the number of paths).

Now, starting from $a = (n-1,0)$ walk along $P$ away from $b$
until one of the following three conditions is met:
\begin{itemize}
  \ii We reach a point $v$ not in $S$.
  Let $w$ be the point before $v$,
  and $x$ the point in $S$ adjacent to $w$.
  Then delete $vw$ and add $wx$.
  This increases $N$ while leaving the number of edges unchanged:
  so this case can't happen.

  \ii We reach an endpoint $v$ of $P$ (which may be $a$),
  lying inside the set $S$, which is not the topmost point $(0,n-1)$.
  Let $w$ be the next point of $S$.
  Delete any edge touching $w$ and add edge $vw$.
  This increases $N$ while leaving the number of edges unchanged:
  so this case can't happen.

  \ii We reach the topmost point $(0,n-1)$.
\end{itemize}
Thus we see that $P$ must follow $S$ until reaching the topmost point $(0,n-1)$.
Similarly it must reach the bottom-most point $(0,-n)$.
Hence $P=S$.

The remainder of $S_n$ is just $S_{n-1}$,
and hence this requires at least $n-1$ paths to
cover by the inductive hypothesis.
So $S_n$ requires at least $n$ paths, as desired.

%A bit easy for a \#3, seeing that I got this during while trying to sleep on a train ride to visit my grandmother (and I normally suck at combo). This is more or less equivalent to MellowMelon's solution, but here's how I phrased it in my head.

\begin{remark*}
  [Motivational comments from Evan]
  Basically the idea is that I wanted to peel away the
  right path $S$ highlighted in red in the figure, so that one could induct.
  But the problem is that the red path might not actually exist,
  e.g.\ the set of paths might contain the mirror of $S$ instead.

  Nonetheless, in those equality cases I found I could perturb some edges
  (e.g.\ change from $(-1,n-2)$--$(0,n-2)$ to $(0,n-2)$--$(1,n-2)$).
  So the idea then was to do little changes and try to convert
  the given partition into one where the red path $S$ exists,
  (and then peel it away for induction)
  without decreasing the total number of paths.

  To make this work, you actually want the incisions to begin
  ear the points $a$ and $b$,
  because that's the point of $S$ that is most constrained
  (e.g.\ you get $a$--$b$ right away for free),
  and assemble the path from there.
  (If you try to do it from the top, it's much less clear what's happening.)
  That's why the algorithm starts the mutations from around a.
\end{remark*}

\paragraph{Second solution (global).}
Here is a much shorter official solution,
which is much trickier to find, and ``global'' in nature.

Color the upper half of the diagram with a blue/red checkerboard pattern
such that the uppermost point $(n-1,0)$ is blue.
Reflect it over to the bottom, as shown.
\begin{center}
\begin{asy}
bool even(int x) {
  return (x % 2 ==  0
  );
}
int n = 4;
for (int a=-4; a<=4; ++a) {
for (int b=-4; b<=4; ++b) {
if (abs(a) + abs(b+0.5) < n) {
if ( (b >= 0) && even(a+b+n+1)) dot( (a,b), blue+4 );
else if ( (b < 0) && even(a+b+n)) dot( (a,b), blue+4 );
else dot( (a,b), red+3 );
}
}
}
\end{asy}
\end{center}

Assume there are $m$ paths.
Cut in two any paths with two adjacent blue points;
this occurs only along the horizontal symmetry axis.
Thus:
\begin{itemize}
  \ii After cutting there are at most $m+n$ paths,
  since at most $n$ cuts occur.
  \ii On the other hand,
  there are $2n$ more blue points than red points.
  Hence after cutting there must be at least $2n$ paths
  (since each path alternates colors, except possibly for double-red pairs).
\end{itemize}
So $m+n \ge 2n$, hence $m \ge n$.


\begin{remark*}
  This problem turned out to be known already.
  It appears in this reference:
  \begin{quote}
  Nikolai Beluhov, Nyakolko Zadachi po Shahmatna
  Kombinatorika, \emph{Matematika Plyus},
  2006, issue 4, pages 61--64.
  \end{quote}
  Section 1 of 2 was reprinted with revisions as
  Nikolai Beluhov, Dolgii Put Korolya, \emph{Kvant},
  2010, issue 4, pages 39--41.
  The reprint is available at
  \url{http://kvant.ras.ru/pdf/2010/2010-04.pdf}.
\end{remark*}

\begin{remark*}
  [Nikolai Beluhov]
  As pointed out in the reference above,
  this problem arises naturally when we try to
  estimate the greatest possible length of a closed king tour
  on the chessboard of size $n \times n$ with $n$ even,
  a question posed by Igor Akulich in Progulki
  Korolya, \emph{Kvant}, 2000, issue 3, pages 47--48.
  Each one of the two references above contains a proof
  that the answer is $n + \sqrt{2}(n^2 - n)$.
\end{remark*}