2008 USAMO Problems/Problem 3
(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 ).
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)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|
- <url>viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>