Suppose you have a partition of less than $ n$ paths. Then start from $ (0,n - 1)$ and work your way down to $ (0, - n)$ along the right edge of $ S_n$ performing the following algorithm when going from each point. (example of described path for $ S_4$) ...V... ..o>V.. .ooo>V. ooooo>V oooooV< .oooV<. ..oV<.. ...X... If a path already has the point you're coming from and the point you're going to as adjacent in the path, do nothing. If not the first case, and the point you're coming from and the point you're going to are both endpoints of paths, join them (one less path). If not the first case, and there is exactly one endpoint among the point you're coming from and the point you're going to, remove a segment from the one in the middle of a path (paths +1) and now you have two endpoints; join them (paths -1). If the point in the middle of the path is the one you're coming from, remove the segment that doesn't come from the point that came before it. The number of paths remains the same. If not the first case, and both points are in the middle of a path... well this is impossible. Since the two points are in the middle of the path, they are adjacent to two other points. But they are also adjacent to each other, so both are adjacent to at least three points. And now you can prove, looking at the path we're going to, that no two points adjacent to at least three others are travelled consecutively. So given any configuration we can create the path shown above without increasing the number of paths. The remaining points form $ S_{n-1}$. Now suppose for some positive integer $ n$, we have a partition into less than $ n$ paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than $ n-1$ paths. Apply the algorithm again. Repeat until we show that $ S_1$ is partitioned into less than $ 1$ path. This is absurd, and we're done.

Can anyone give me an estimation of how many points out of 7 that would be? Maybe 1 or 2?

MellowMelon in other topic wrote: You may as well face it that score estimates from people on this forum will almost certainly suck. Just don't worry about it. I won't estimate your score, but I can tell you your lemma that one path has at most $ 2n$ points is false. For $ S_3$, take the following path: $ (0,2) (0,1) (1,1) (1,0) (2,0) (2, - 1) (1, - 1) (0, - 1)$ $ (0,0) ( - 1,0) ( - 2,0) ( - 2, - 1) ( - 1, - 1) ( - 1, - 2) (0, - 2) (0, - 3)$ This path contains $ 16$ points, which is greater than $ 2 \cdot 3 = 6$.

Oh... Wow, that's disappointing... Well... I stand corrected...

So, suppose we have a valid pathing of S_i-1 with at least i-1 paths, as Mellow says. Then, how do we know the paths can't just be extended into the points in S_i but not S_i-1, and/or two paths in S_i-1 can be joined with no more than one new path? I don't quite follow your proof.

Mellow, I didnt read most of your proof, but I think i had the same general idea as you did.

Don't worry, my actual proof was a lot more rigorous.

This solution is different from the official so please critique it.

I know that solution is much longer than the official one, but does it work?

This is my scanned solution. I purposefully cut off the top so that people won't know my student number. I know it has a hole, but I hope it's worth 2 or 3 points

Very good solution, I didn't see the "hole" :

nealth wrote: This is my scanned solution. I purposefully cut off the top so that people won't know my student number. I know it has a hole, but I hope it's worth 2 or 3 points I've finally found a proof that is close to mine except that in the end I especially mentioned when N=2or 3, it takes at least 2,3 paths relatively...(and that my answer wasn't that full-proofed for I only had 15 minutes to write up the thing )

This is pretty much MellowMelon's proof, except a lot less concise and much less clear (as I didn't include diagrams and felt the need to explain everything). It is evident that the set of lattice points satisfying this is composed of two isosceles triangular grids: one with a base with midpoint $ (0,0)$, base length $ 2(n-1)$, height $ n-1$, with its vertex at $ (0,n-1)$, and another which is the first one reflected over $ y=-\frac{1}{2}$ - that is, base midpoint at $ (0,-1)$, base length $ 2(n-1)$, height $ n-1$, and vertex at $ (0,-n)$. Now we define a side path to be a path between two side points of our figure (i.e. $ (x,y)$ is a side point of our figure if there are only two points which are in the figure out of $ (x+1,y),(x-1,y),(x,y+1),(x,y-1)$) with certain restrictions. Letting the two points be $ (a,b),(c,d)$ and letting the line through them be $ y=f(x)$ we need that every side point $ (x,y)$ satisfying $ y \le f(x)$ be in the path or every side point satisfying $ y\ge f(x)$ be in the path if the points are noncollinear. If they're collinear, then the side points in the path are either the ones on the line through them and between the two points, or the complement of that set. In addition, regardless of collinearity, the only other points in our path can be the points bordering at least two side points within the path. This (absolutely ridiculous, I'm sorry) definition is not as complicated as it sounds; it just means that every side point on the side of the figure "between" the two points is in the path, and the side path moves in a staircase fashion betwene them. Noting that by definition, each pair of side points has two possible side paths between them, we prove the following lemma: Lemma: Both side paths of a pair of side points $ (a,b),(c,d)$ are actually possible iff the two points are the vertices of the isosceles triangles. Otherwise, one path is achievable iff the two points are on the same side of the $ y$-axis. Proof: We prove the result that no side path can travel through points on both sides of the $ y$-axis, which quickly gives the desired result, because the second part is immediately equivalent and for the first part, two side points on the same side of the $ y$ axis have a line through them which self-evidently does not intersect the $ y$-axis within the boundaries of our figure; hence the path on the side of that line which doesn't contain the $ y$-axis is attainable while the other is not. The side path between the two vertices of the triangles is also easily shown to be attainable; move in a staircase fashion from top one (down one, right one, etc.) until one reaches $ (n-1,-1)$, then repeat the same process except as a reflection across $ y=-\frac{1}{2}$. On to the proof of our intermediate result: Suppose a side path went through side points on both sides of the $ y$-axis. Then it would have to pass through one of the vertices of the two isoceles triangles as they are the only side points linking the two side of our figure. WLOG, let the one it passes through be $ (0,-n)$. It must then also pass through $ (-1,-n+1)$ and $ (1,-n+1)$. But the only point adjacent to our triangle vertex is $ (0,-n+1)$ and from here only one of these two points can be reached, WLOG choose $ (1,-n+1)$ (since by definition going up again to $ (0,-n+2)$ would result in a non-side path). However, after the side path passes through $ (1,-n+1)$, by definition it can only travel along the side and bordering-side points, and so for the side path to reach $ (-1,-n+1)$ it must cross the $ y$-axis at the other end; through $ (0,n-1)$. But to get there, it must pass through $ (0,n-2)$, and then once it reaches that point, there are no other points bordering $ (0,n-1)$, so we're "stuck". Contradiction (and none too soon!). Now we prove another lemma: Lemma: Consider one of the side paths connecting the two isosceles triangles' vertices (WLOG the on the positive side of the $ y$-axis) and the side path connecting $ (-1,n-2)$ and $ (-1,-n+1)$. The minimal number of paths which our figure can be partitioned into can be attained with these in place. Proof: Consider a partition which attains the minimum, and specifically the path containing $ (-0,-n)$. It of course must connect to the point directly above it, or the partition wouldn't be optimal. Now, we show by a "smoothing" process that it is possible to change the partition to one with a side path from $ (-0,-n)$ to $ (0,n-1)$. without increasing the number of paths. Consider each successive point so that the paths in the given partition differ from a partition with such a side path; in particular consider the path that contains the point which would otherwise be in the side path. Case 1: The point which would otherwise be in the side path is a side point. In this case, this point must simply be connected to the next point in the side path (since each side point borders only two points), s we can simply connect the preceding point in the path to it. If the preceding point is already connected to another non-side path point, disconnect it - we can do this, as we merged two paths without disconnecting anything earlier. Case 2: The point is a point which borders the side points. If this point is connected to the side point following it on the would-be path, then we can simply use our above logic. If it's not connected to it but is also connected to only at most one of the non-side points it borders, we can disconnect it and connect it to the path without increasing the number of side paths. Finally, if it's connected to both of the non-side points it borders, we can't disconnect it without splitting a path in two, but we can compensate by linking it to both the existing side path and the next point in the side path, hence connecting two existing paths. We can do this without forming a loop because each side point only borders two other points. We can apply the same logic to the other path (by symmetry), and so our lemma follows. Finally, we prove our claim by induction. We have two base cases; note that when $ n=1$ or $ 2$, by inspection (if I could draw a diagram I would be more rigorous, I swear) we can't partition the figure $ S_n$ into fewer than $ n$ paths. Now, suppose that we can't partition $ S_n$ into fewer than $ n$ paths for $ n=k-2$. By our lemma, if it were possible to partition $ S_k$ into fewer than $ k$ paths, we could do it with the side paths (call them $ a,b$) mentioned in our lemma in place. However, $ S_k\setminus (a\cup b)$ is just $ S_{k-2}$, which means that $ S_{k-2}$ could be partitioned into fewer than $ k-2$ paths - contradiction. The result follows.

Does this proof work? It's pretty similar to MellowMelon's. Assume that it is possible to partition the region into fewer than $n-1$ paths. Consider the staircase-shaped path, $P$, formed along the right edge of the region. If any unit segment of $P$ is not joined in the partition, then draw it in. Then, if necessary, erase the segment that now sticks out from a point in $P$ to an adjacent point to the left. Clearly the number of paths does not increase. Then, we are left with $S_{n-1}$ which is partitioned with fewer than $n-2$ paths. Then keep going, until you have one point left, but no paths, a contradiction.

which USAMO is this?

luie1168e wrote: which USAMO is this? It's from 2008. Sorry for reviving it. I keep thinking my solution is too simple, so I was hoping someone could tell me if I'm missing something obvious.

Here's the major problem I see with your solution: "Clearly the number of paths does not increase." It's true (as the me of almost 3 years ago showed in the first reply), but to say it's "clearly" true is handwaving.

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. We proceed by induction on $n$. The base case $n=1$ is clear, so suppose $n > 1$. Let $A$ denote the set of points \[ A = \left\{ (x,y) : x + \left\lvert y+\frac12 \right\rvert \ge n - 2 \right\}. \] An example when $n=4$ is displayed below. [asy][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); [/asy][/asy] For any minimal partition $\mathcal P$ of $S_n$, let $P$ denote the path passing through $(n-1,0)$. Pick $\mathcal P$ such that $\left\lvert P \cap A \right\rvert$ is maximal. We claim that in this case $P = A$. Assume not. Starting from $(n-1,0)$, walk along $P$ in any direction until we encounter a vertex $v$ such that $v$ is not adjacent to any vertex in $A$ we have not already seen. We consider three cases. If $v = (0,n-1)$ or $v = (0,-n)$, then this is clearly an endpoint of $P$. In that case $P$ spans all of $A$, as desired. If $v$ is an endpoint other than that, then let $a$ be the "next" vertex in $A$. By minimality of $\mathcal P$, $a$ must not be an endpoint. Now delete any vertex adjacent to $a$, and add the edge $av$. This increases $\left\lvert P \cap A \right\rvert$ without affecting the number of paths, contradiction. If $v$ is not an endpoint, again let $a$ be the "next" vertex in $A$. Delete the edge joining $v$ to the vertex not in $A$, and add the edge $va$. We again arrive at a contradiction. This forces $A \subseteq P$. Clearly this implies $P=A$. 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. Moral of the story: look at maximal things.

There's a very short proof by coloring the points. Let's color the points that $ y \geq 0 $ by coloring the most outside points black and coloring the inside points to have no white points next to a white point and no black point next to a black point alternatively. And color the points that $ y < 0 $ by doing the same thing above. Now let's say the number of paths are $ m $ and $ k $ be the number of $ x $ that there exist a path that goes through the segment $ (x,0),(x,-1) $. Now let's delete the segments $ (x,0),(x,-1) $. Then, we get total $ m+k $ paths and no path goes through the line $ y=0 $ and $ y=-1 $. So, the maximum number of black points - white points on each path is at most 1, so the paths on $ y \geq 0 $ and $ y<0 $ must be at least $ n $. Which means that $ m+k \geq 2n $. But,we know that $ k \leq n $. So, we get $ m \geq n $.

Let $A$ be the point $(0,n-1)$ and take some partition of $S_n$. We will give a series of steps that does not increase the number of paths while shifting the path through $A$ to the rightmost one; i.e. the series of steps $(0,n-1), (0,n-2), (1,n-2), (1,n-3),..., (n-1,0)$. Let $P$ be the path containing $(0,n-1)$ and suppose that $P$ goes through $(x,n-1-x)$ but not $(x,n-2-x)$ for some $x$. Then deleting the edges out of $(x,n-2-x)$ will add at most one path to the partition. However, now connect $(x+1,n-2-x), (x, n-2-x), (x,n-1-x)$. This connects two paths in the partition, decreasing the size of the partition by one, and thus after this algorithm the size of the partition does not increase. Now suppose that $P$ goes through $(x, n-2-x)$ but not $(x+1,n-2-x)$ for some $x$. Deleting the edges out of $(x,n-2-x)$; this adds at most one path to the partition. But then by connecting $(x,n-2-x)$ to $(x+1,n-2-x)$ will connect two paths, reducing the size of the partition by one yet again. By repeating this process, we eventually get a path from $(0,n-1)$ to $(n-1,0)$. Similarly, we can get a path from $(0,-n)$ to $(n-1,-1)$. If $(n-1,-1)$ and $(n-1,0)$ are not connected, then we can simply connect them to decrease the number of paths by one (as those two vertices cannot be connected to any other vertex). But now we have a path $P$ such that when taken out, the graph $S_{n-1}$ remains. It's easy to check that $S_1$ has needs at least $1$ path in its partition, so by induction it follows that $S_n$ cannot be partitioned into fewer than $n$ parts.

Color the points of (rotated) $S_n$ as follows. [asy][asy] int n = 5; for (int i = -n; i < n; ++i) for (int j = -n; j < n; ++j) { if (abs(j) + abs(i+1/2) < n) { dot((i, j), (abs(2*j) + abs(2*i+1) - 2*n - 1) % 4 == 0 ? red : black); }} for (int i = -(n-1); i <= (n-1); i += 2) { draw((0, i)--(-1, i), dotted); } [/asy][/asy] Then there are $2n$ more black points than red ones, and $n$ black-black dotted segments. This is the only information about $S_n$ we will use. For each path $P$, let $f(P)$ denote $\#(\text{black points on } P) - \#(\text{red points on } P)$ and $g(P)$ denote the number of dotted segments used by $P$. The main idea is to use the following (obvious) inequality: for any path $P$, \[g(P) \ge f(P) - 1.\]Considering $S_n = P_1 \sqcup \dots \sqcup P_k$, summing the above inequality \[\big(g(P_1) + \dots + g(P_k)\big) \ge \big(f(P_1) + \dots + f(P_k)\big) - k\]or $g(P_1) + \dots + g(P_k) \ge 2n - k$. But the sum of the $g$'s is at most $n$ (number of dotted segments), so $k \ge n$ as desired.

Induct on $n$, base case $n=1$ trivial. Assume we need at least $n-1$ paths for $S_{n-1}$. Suppose we have a configuration of less than $n$ paths for $S_n$. Claim: There exists a configuration with the same number of paths, one of whose paths is the rightmost double-staircase: the path that starts at $(0,n-1)$ and ends at $(0,-n)$ sticking to the right edge of $S_n$. Proof: The main idea is to construct the rightmost staircase by rearranging paths to get what we need. Suppose we have the staircase from $(0,n-1)$ till $A$. Say we need to add horizontal edge $AB$, assuming it doesn't already exist. Rearrange by deleting the next edge coming out of $A$ and instead connecting $AB$; this creates one new path and joins two paths, keeping the total number of paths invariant.

The edge containing $B$ in its path must have been vertically below, since we assumed $AB$ is empty initially. So this process also adds the necessary vertical edge after $B$ to continue the staircase. (Alternatively, a similar rearrangement works for getting necessary vertical edges.) We end this process with the staircase from $(0,n-1)$ to $(n-1,0)$. Similarly, make the staircase from $(0,-n)$ to $(n-1,-1)$. Finally connect the two staircases if they aren't already; this will not increase the number of paths. $\blacksquare$ Now remove the double-staircase and we are left with $S_{n-1}$, which by induction needs at least $n-1$ paths. Adding the one path implies we need at least $n$ paths, contradiction.

My approach is similar to Cantonmathguy's except expressed less elegantly. What a magical problem. Define $T_n$ to be the set of points $(x,y)$ satisfying $n-1<|x|+|y+1/2|<n$, so $S_n=T_n\cup T_{n-1}\cup\cdots \cup T_1$. Observe that any two points in $S_n$ with distance $1$ from each other must be in some $T_i$ and $T_{i-1}$ unless they are the pair $(i,0),(i,-1)$ or $(-i,0),(-i,-1)$. Draw an edge between any two adjacent elements of a path. Then, the total number of edges, $E$, is upper-bounded by \[2|T_{n-1}|+2|T_{n-3}|+\cdots + \varepsilon\]where $\varepsilon$ is the sum of the number of pairs of points with distance $1$ away from each other in each of $T_n,T_{n-2},\dots$ because every edge is either counted by $\sum_i 2|T_{n-2i-1}|$ or by $\varepsilon$ and any edge between adjacent elements of some $T_{n-2i-1}$ is counted twice by this sum. Observe that if $n=2k$ then $\varepsilon=2k$ and if $n=2k+1$ then $\varepsilon=2k+1$, so $\varepsilon=n$. Remark that the number of paths is $2n^2-|E|$ because there are $2n^2$ points in $S_n$ so the result follows by viewing $S_n$ as a forest with edges $E$. Hence it suffices to demonstrate \[n^2-n\ge |T_{n-1}|+|T_{n-3}|+\cdots .\]Remark that each $T_i$ contains $4i-2$ elements: $2i-1$ with $y\ge 0$ and $2i-1$ with $y<0$. If $n$ is even and equal to $2k$, this sum is \[\sum_{i=1}^k (4(2i-1)-2)=\sum_{i=1}^k (8i-6)=4(k^2+k)-6k=4k^2-2k=n^2-n.\]If $n$ is odd and equal to $2k+1$, this sum is \[\sum_{i=1}^k (4\cdot 2k-2)=4(k^2+k)-2k=4k^2+2k=(2k+1)^2-2k-1=n^2-n.\]Either way, we are done.

Redacted

Note that $S_n$ can be thought of as the manhattan metric semicircle with radius $n - 1$, reflected across $y = -\frac{1}{2}$. Note that if we create a path along the sides of the diagonal with length two edges by zigzagging up then down, this allows us to induct to the case of $n - 1$. It remains to show that any optimal partition into paths contains this edge path. Note that we can WLOG assume that the length two edges are in the same path by connecting if needed. Claim: Consider the two points on the border a zig-zag apart. Take an optimal config. It is possile to connect the two points into the same path while not disconnecting any two other border points while remaining optimal, under the assumption that neither point is on the edge. Proof. Suppose a partition is optimal and does not have the two points in the same path. Consider the common neighbor of both of them. We can disconnect this common neighbor from neighbor paths and connect them to the two points. If this point connects either to one of the two points or only once, it can be seen that the number of paths is preserved. Else, this breaks a path through the common neighbor point with its other two neighbors. However, this can just be repeated by connecting those two neighbors with their other common neighbor point until this is finished. $\blacksquare$ In the case of one of the point being a corner, this could break the corner point connecting to another point. Then, we can repeat this to connect all the zig-zags on the edge. This then must be the edge path, so we induct downward and finish.

, and this immediately became one of my favorite problems. Color the points in the region black and white such that the points around the outer rim are black, and except for $n$ vertical segments in the middle two rows, every black point only borders white points. The argument here becomes clear: consider taking paths away from the region, and look at $\Delta$, the difference between the number of black and white points. Originally, $\Delta = 2n$. For some path $P$, denote by $f(P)$ the number of vertical black segments in $P$. For $g(P)$ the change in $\Delta$ after removing $P$, we have $g(P) \leq f(P) + 1$. Suppose we have a partition into $k$ paths; then, $$2n = \sum_{i=1}^k g(P_i) \leq \sum_{i=1}^k f(P_i) + k = n+k.$$Therefore $k \geq n$.

Does this work? I feel like i phrased it differently The idea is to induct down, base case n=1 trivial. Now look locally: In the diagram, we can change the paths slightly to not make more paths, but have the path stay along the right staircase. and um oops i understnad that the graph is not correct, jstu ingnore the rightmost and leftmost two corners. so basically since this does not change \# of paths, you can keep perturbing that it stays in shape of staircase. so now indicuct down to at least n-1.

Welp I'm not very good at combo (this took a while) Label the topmost point $A_1$ and the bottommost point $A_{4n-2}$. Traveling along the left edge of $S_n$, label the $i$th point from the top $A_i$. The idea is to split and merge paths while not increasing the number of paths to obtain a path $A_1\to A_2\to \dots\to A_{4n-2}$. This will complete the question by induction (the base case of $n=1$ is easy). Turns out it's not very difficult to do so. Assume that we currently have a path $A_1\to A_2\to \dots \to A_k \to B_1\to B_2\to \dots \to B_{\ell}$ where $B_1\neq A_{k+1}$. The goal is to show we can modify the paths to have $B_1=A_{k+1}$. In particular, it's possible to have $A_{k+1}\in \{B_2,B_3,\dots,B_{\ell}\}$. When $k$ is odd, then $\ell=0$. This is trivial as the only location for $B_1$ otherwise is the point $A_{k+1}$. Now split a path so that $A_{k+1}$ is an endpoint. This increases the path count by at most $1$. Evidently $A_{k+1}$ is not a part of our current path ($\ell=0$) hence we can merge $A_k\to A_{k+1}$ and decrease the path count by $1$. This is fine. When $k$ is even, then $A_{k+1}$ is an endpoint of its path. Now if $B_{\ell}=A_{k+1}$, it turns out that removing $A_k\to B_1$ and replacing with $A_k\to B_{\ell}=A_{k+1}$ suffices. Otherwise $A_{k+1}$ is not part of our current path, hence remove the edge $A_k\to B_1$. The path count has increased by at most $1$, and now $A_k$ and $A_{k+1}$ are endpoints of their own (distinct) paths. So merge these, decreasing the path count by $1$. All cases are exhausted, done! Actually, we need to handle the case where $A_k$ is at the middle of $S_n$. Luckily, the same concepts work.

Color the points on or above the $x$-axis black and white in a checkerboard pattern, and separately color the points below the $x$-axis black and white in a checkerboard pattern, such that both of the leftmost points in $S$ are white. Cut each path at any point where it has two consecutive white points. There are only $n$ pairs of consecutive white points, so the number of paths increases by at most $n$. The final number of paths is at least $2n$, because there are $2n$ more white than black points, and each path has at most one more white than black point on it. This finishes the proof.

Definitions, problem restatement: With $m$ paths, notice that there are $2m$ points with degree 1 and the remaining points have degree 2. Notice that any configuration of edges such that each point has a degree of at most 2 produces a valid partition of $\mathcal{P}$ into paths. Therefore, it suffices to maximize the number of edges to minimize the number of paths (since less points with degree 1). Color all the points with the highest x value for each y value red. For all red points, number them starting from 1 for the topmost point such that points with the numbers $l$ and $l + 1$ are adjacent. Actual Solution: We induct. The base case where $n = 1$ is trivial (line). Induction, assume true for $n$, will prove for $n + 1$ Consider a random partition of points into paths. If there is not an edge connecting points $k$ and $k + 1$, then simply draw this edge. If $k$ is odd, point $k$ can't have a degree of more than 2 and so we simply remove an edge connected to point $k + 1$ if its degree is greater than 2. Likewise, if $k + 1$ is odd, point $k + 1$ can't have a degree of more than 2 so we simply remove an edge connected to point $k$ if its degree is greater than 2. Do this process repeatedly to eventually arrive at a new partition of $\mathcal{P}$ with the same or more edges as compared to the original partition and with all red points connected. Now, the min number of paths for the remaining points is $n$ so the minimum overall is $n + 1$.