【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|y+\frac{1}{2}\right| \geq n-2\right\}$$
An example when $n=4$ is displayed below. !
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:
- 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 $v w$ and add $w x$. This increases $N$ while leaving the number of edges unchanged: so this case can't happen.
- 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 $v w$. This increases $N$ while leaving the number of edges unchanged: so this case can't happen.
- We reach the topmost point $(0, n-1)$.
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.
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 near 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$.