2008 USAMO Problems/Problem 3

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

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>Forum/viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>

Page

Toolbox

Search