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
I proved this the same way as in the official solution. Basically, color all the points in 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
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
times, once for each path) or by using the adjacent white squares in the middle two rows (there are only
such pairs). Therefore we can't make up for those
extra white points, so there's no partition into fewer than
paths.
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.
(example of described path for )
[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 . 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. This is absurd, and we're done.
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>