2008 USAMO Problems/Problem 3
Problem
(Gabriel Carroll) Let be a positive integer. Denote by the set of points with integer coordinates such that A path is a sequence of distinct points in such that, for , the distance between and is (in other words, the points and are neighbors in the lattice of points with integer coordinates). Prove that the points in cannot be partitioned into fewer than paths (a partition of into paths is a set of nonempty paths such that each point in appears in exactly one of the paths in ).
Solution
Solution 1
Color all the points in 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.
Suppose there is a partition of paths that works. For each of the paths, we break a path into two separate paths wherever there are consecutive red points. This only happens only with the red pairs in the middle two rows. We now have 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 red dots than black dots in .
There are more red points than black points, so which implies that , contradiction.
Solution 2
Suppose you have a partition of less than paths. Then start from and work your way down to along the right edge of performing the following algorithm when going from each point.
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 . Now suppose for some positive integer , we have a partition into less than paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than paths. Apply the algorithm again. Repeat until we show that is partitioned into less than path, contradiction.
Solution 3
We induct on to prove that an -path partition is impossible. This can be restated as saying that we cannot fit 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 , and we'll prove it's possible for .
Call the 'complete' network (graph) of points and the -path partition for is a subgraph of , . There are a total of edges in out of in (not hard to prove), and each vertex has maximum order 2. Now consider the complement of in , that is, take all the edges in that are not in and of course all the vertices. Call this We will trim down a bit to get .
First, call the points in but not exterior points, and the points in interior points. has edges. Since the interior points have degree 4 in , they have degree at least 2 in , for a total degree of where since the total overall degree is . This makes the total degree of the exterior points . Since the exterior points are not connected in , these edges must connect on exterior point to an interior point.
I then take away edges and the exterior points, yielding edges and the interior points, which is , as follows: First take away those interior-exterior edges and shave off all the exterior points. Then the total degree (now just of the interior points) must be .
Let the number of 0-degree vertices be , 1-degree vertices be , 2-degree vertices be , 3-degree vertices be , and 4-degree vertices be . Since all the vertices began as 2-degree or higher, . Moreover, the total degree is . So So we can use our last edges to remove any excess degree on vertices with degree 3 or 4, yielding .
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>