Difference between revisions of "2008 USAMO Problems/Problem 3"

Latest revision as of 00:00, 14 August 2014

Problem

(Gabriel Carroll) Let $n$ be a positive integer. Denote by $S_n$ the set of points $(x, y)$ with integer coordinates such that $\left|x\right| + \left|y + \frac {1}{2}\right| < n$ A path is a sequence of distinct points $(x_1 , y_1 ), (x_2 , y_2 ), \ldots , (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \ldots , \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}$ ).

Solutions

Solution 1

Color all the points in $S_{n}$ red or black such that each row of points starts and ends with a red point, and alternates between red and black for each point in the row. This creates a checkerboard pattern, except that the middle two rows are identical.

$[asy] /* variable declarations */ int n = 4; /* code */ pen r = red, b = black; int absol(int k){if(k >= 0) return k; else return -1*k-1;} pen col(bool k){if(k) return r; else return b;} for(int y = -n; y < n; ++y){ bool b = true; for(int x = absol(y)-n+1; x < n-absol(y); ++x){ dot((x,y),col(b)); b = !b; } } draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */ [/asy]$ $[asy] /* variable declarations */ int n = 4; /* code */ pen r = red, b = black; int absol(int k){if(k >= 0) return k; else return -1*k-1;} pen col(bool k){if(k) return r; else return b;} for(int y = -n; y < n; ++y){ bool b = true; for(int x = absol(y)-n+1; x < n-absol(y); ++x){ dot((x,y),col(b)); b = !b; } } draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */ draw((-1,2)--(-1,1)--(0,1)--(1,1)--(1,0),linewidth(0.7)); draw((1,0)--(1,-1),linetype("3 3")+linewidth(0.7)); draw((1,-1)--(1,-2)--(2,-2),linewidth(0.7)); [/asy]$

Examples for $n=4$

Suppose there is a partition of $m < n$ paths that works. For each of the $m$ paths, we break a path into two separate paths wherever there are consecutive red points. This only happens only with the $n$ red pairs in the middle two rows. We now have $m + l,\, l \le n$ paths whose colors are strictly alternating. In a path with alternating colors, there can be at most one more red dot than the number of black dots (which occurs when both endpoints are red). Thus there can be no more than $m + l$ red dots than black dots in $S_n$ .

There are $2n$ more red points than black points, so $2n \le m + l \le m + n$ which implies that $n \le m$ , contradiction.

Solution 2

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.

$[asy] /* variable declarations */ int n = 4; /* code */ int absol(int k){if(k >= 0) return k; else return -1*k-1;} for(int y = -n; y < n; ++y){ for(int x = absol(y)-n+1; x < n-absol(y); ++x){ dot((x,y),black); /* label((string) x + " " + (string) y, (x,y), SE); */ /* addendum */ if((x==n-absol(y)-1 && y >= 0) || (x==n-absol(y)-2 && y < 0)){ draw((x,y-0.2)--(x,y-0.8),EndArrow); } if(x==n-absol(y)-2 && y >= 0){ draw((x+0.2,y)--(x+0.8,y),EndArrow); } if(x==n-absol(y)-1 && y < 0 && y > -n){ draw((x-0.2,y)--(x-0.8,y),EndArrow); } } } draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */ dot((0,-n),linewidth(5)+red); [/asy]$

Example for $S_4$

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, which 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. Then, no two points adjacent to at least three others are travelled consecutively.

Thus, 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, contradiction.

Solution 3

We induct on $n$ to prove that an $n - 1$ -path partition is impossible. This can be restated as saying that we cannot fit $2n^2 - n + 1$ edges into the graph with each vertex having degree at most 2. The base case is trivial (2 edges when there only is 1). Suppose it was possible for $n + 1$ , and we'll prove it's possible for $n$ .

Call the 'complete' network (graph) of points $G_{n + 1}$ and the $n$ -path partition for $n + 1$ is a subgraph of $G_{n + 1}$ , $H_{n + 1}$ . There are a total of $2(n + 1)^2 - n = 2n^2 + 3n + 2$ edges in $H_{n + 1}$ out of $4n^2 + 4n + 1$ in $G_{n + 1}$ (not hard to prove), and each vertex has maximum order 2. Now consider the complement of $H_{n + 1}$ in $G_{n + 1}$ , that is, take all the edges in $G_{n + 1}$ that are not in $H_{n + 1}$ and of course all the vertices. Call this $F_{n + 1}$ We will trim $F_{n + 1}$ down a bit to get $H_n$ .

First, call the points in $S_{n + 1}$ but not $S_n$ exterior points, and the points in $S_n$ interior points. $F_{n + 1}$ has $2n^2 + n - 1$ edges. Since the interior points have degree 4 in $G_{n + 1}$ , they have degree at least 2 in $F_{n + 1}$ , for a total degree of $4n^2 + m$ where $0\le m\le 2n - 2$ since the total overall degree is $2(2n^2 + n - 1) = 4n^2 + 2n - 2$ . This makes the total degree of the exterior points $2n - 2 - m$ . Since the exterior points are not connected in $G_{n + 1}$ , these $2n - 2 - m$ edges must connect on exterior point to an interior point.

I then take away $2n - 2$ edges and the exterior points, yielding $2n^2 - n + 1$ edges and the interior points, which is $H_n$ , as follows: First take away those $2n - 2 - m$ interior-exterior edges and shave off all the exterior points. Then the total degree (now just of the interior points) must be $4n^2 - 2n + 2 + 2m$ .

Let the number of 0-degree vertices be $a$ , 1-degree vertices be $b$ , 2-degree vertices be $c$ , 3-degree vertices be $d$ , and 4-degree vertices be $e$ . Since all the vertices began as 2-degree or higher, $2a + b\le2n - 2 - m$ . Moreover, the total degree is $b + 2c + 3d + 4e = 2(2n^2) + (d + 2e) - (b + 2a) = 4n^2 - 2n + 2 + 2m$ . So $d + 2e = b + 2a - (2n - 2 + 2m)\le (2n - 2 - m) - (2n - 2 - 2m) = m$ So we can use our last $m$ edges to remove any excess degree on vertices with degree 3 or 4, yielding $H_n$ .

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

2008 USAMO (Problems • Resources)
Preceded by Problem 2	Followed by Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search