Difference between revisions of "2008 USAMO Problems/Problem 3"

Revision as of 18:59, 1 May 2008

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

@@ Line 14: / Line 14: @@
 {{USAMO newbox|year=2008|num-b=2|num-a=4}}
-* <url>Forum/viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>
+* <url>viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>
 [[Category:Olympiad Combinatorics Problems]]

Page

Toolbox

Search