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

Revision as of 16:29, 3 May 2008

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}$ ).

Solution

Solution 1

I proved this the same way as in the official solution. Basically, color all the points in $S_{n}$ white or black such that each row of points starts and ends with a white point. This is essentially a checkerboard pattern, except that the middle two rows are identical. We have $2n$ more white points than black points, and we can only "recover" white points by having paths whose endpoints are both white (this can only happen $n - 1$ times, once for each path) or by using the adjacent white squares in the middle two rows (there are only $n$ such pairs). Therefore we can't make up for those $2n$ extra white points, so there's no partition into fewer than $n$ paths.

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.

(example of described path for $S_4$ ) [code]...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.

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.

Resources

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

<url>viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>

@@ Line 7: / Line 7: @@
 == Solution ==
 === Solution 1 ===
+I proved this the same way as in the official solution.  Basically, color all the points in <math>S_{n}</math> white or black such that each row of points starts and ends with a white point.  This is essentially a checkerboard pattern, except that the middle two rows are identical.  We have <math>2n</math> more white points than black points, and we can only "recover" white points by having paths whose endpoints are both white (this can only happen <math>n - 1</math> times, once for each path) or by using the adjacent white squares in the middle two rows (there are only <math>n</math> such pairs).  Therefore we can't make up for those <math>2n</math> extra white points, so there's no partition into fewer than <math>n</math> paths.
 === Solution 2 ===
+Suppose you have a partition of less than <math>n</math> paths. Then start from <math>(0,n - 1)</math> and work your way down to <math>(0, - n)</math> along the right edge of <math>S_n</math> performing the following algorithm when going from each point.
+(example of described path for <math>S_4</math>)
+[code]...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 <math>S_{n - 1}</math>. Now suppose for some positive integer <math>n</math>, we have a partition into less than <math>n</math> paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than <math>n - 1</math> paths. Apply the algorithm again. Repeat until we show that <math>S_1</math> is partitioned into less than <math>1</math> path. This is absurd, and we're done.
+=== Solution 3 ===
+We induct on <math>n</math> to prove that an <math>n - 1</math>-path partition is impossible. This can be restated as saying that we cannot fit <math>2n^2 - n + 1</math> 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 <math>n + 1</math>, and we'll prove it's possible for <math>n</math>.
+Call the 'complete' network (graph) of points <math>G_{n + 1}</math> and the <math>n</math>-path partition for <math>n + 1</math> is a subgraph of <math>G_{n + 1}</math>, <math>H_{n + 1}</math>. There are a total of <math>2(n + 1)^2 - n = 2n^2 + 3n + 2</math> edges in <math>H_{n + 1}</math> out of <math>4n^2 + 4n + 1</math> in <math>G_{n + 1}</math> (not hard to prove), and each vertex has maximum order 2. Now consider the complement of <math>H_{n + 1}</math> in <math>G_{n + 1}</math>, that is, take all the edges in <math>G_{n + 1}</math> that are not in <math>H_{n + 1}</math> and of course all the vertices. Call this <math>F_{n + 1}</math> We will trim <math>F_{n + 1}</math> down a bit to get <math>H_n</math>.
+First, call the points in <math>S_{n + 1}</math> but not <math>S_n</math> exterior points, and the points in <math>S_n</math> interior points. <math>F_{n + 1}</math> has <math>2n^2 + n - 1</math> edges. Since the interior points have degree 4 in <math>G_{n + 1}</math>, they have degree at least 2 in <math>F_{n + 1}</math>, for a total degree of <math>4n^2 + m</math> where <math>0\le m\le 2n - 2</math> since the total overall degree is <math>2(2n^2 + n - 1) = 4n^2 + 2n - 2</math>. This makes the total degree of the exterior points <math>2n - 2 - m</math>. Since the exterior points are not connected in <math>G_{n + 1}</math>, these <math>2n - 2 - m</math> edges must connect on exterior point to an interior point.
+I then take away <math>2n - 2</math> edges and the exterior points, yielding <math>2n^2 - n + 1</math> edges and the interior points, which is <math>H_n</math>, as follows: First take away those <math>2n - 2 - m</math> interior-exterior edges and shave off all the exterior points. Then the total degree (now just of the interior points) must be <math>4n^2 - 2n + 2 + 2m</math>.
+Let the number of 0-degree vertices be <math>a</math>, 1-degree vertices be <math>b</math>, 2-degree vertices be <math>c</math>, 3-degree vertices be <math>d</math>, and 4-degree vertices be <math>e</math>. Since all the vertices began as 2-degree or higher, <math>2a + b\le2n - 2 - m</math>. Moreover, the total degree is <math>b + 2c + 3d + 4e = 2(2n^2) + (d + 2e) - (b + 2a) = 4n^2 - 2n + 2 + 2m</math>. So <math>d + 2e = b + 2a - (2n - 2 + 2m)\le (2n - 2 - m) - (2n - 2 - 2m) = m</math> So we can use our last <math>m</math> edges to remove any excess degree on vertices with degree 3 or 4, yielding <math>H_n</math>.
 {{alternate solutions}}

Page

Toolbox

Search