2008 USAMO Problems/Problem 3

Revision as of 19:59, 1 May 2008 by I like pie (talk | contribs) (Fixed link)

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 (ProblemsResources)
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>