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
Solution 2
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>