Difference between revisions of "2008 USAMO Problems/Problem 3"
(create template) |
m (fix) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
(''Gabriel Carroll'') Let <math>n</math> be a positive integer. Denote by <math>S_n</math> the set of points <math>(x, y)</math> with integer coordinates such that | (''Gabriel Carroll'') Let <math>n</math> be a positive integer. Denote by <math>S_n</math> the set of points <math>(x, y)</math> with integer coordinates such that | ||
− | + | <cmath>\left|x\right| + \left|y + \frac {1}{2}\right| < n</cmath> | |
− | \left|x\right| + \left|y + \frac {1}{2}\right| < n | ||
− | |||
A path is a sequence of distinct points <math>(x_1 , y_1 ), (x_2 , y_2 ), \ldots , (x_\ell, y_\ell)</math> in <math>S_n</math> such that, for <math>i = 2, \ldots , \ell</math>, the distance between <math>(x_i , y_i )</math> and <math>(x_{i - 1} , y_{i - 1} )</math> is <math>1</math> (in other words, the points <math>(x_i , y_i )</math> and <math>(x_{i - 1} , y_{i - 1} )</math> are neighbors in the lattice of points with integer coordinates). Prove that the points in <math>S_n</math> cannot be partitioned into fewer than <math>n</math> paths (a partition of <math>S_n</math> into <math>m</math> paths is a set <math>\mathcal{P}</math> of <math>m</math> nonempty paths such that each point in <math>S_n</math> appears in exactly one of the <math>m</math> paths in <math>\mathcal{P}</math>). | A path is a sequence of distinct points <math>(x_1 , y_1 ), (x_2 , y_2 ), \ldots , (x_\ell, y_\ell)</math> in <math>S_n</math> such that, for <math>i = 2, \ldots , \ell</math>, the distance between <math>(x_i , y_i )</math> and <math>(x_{i - 1} , y_{i - 1} )</math> is <math>1</math> (in other words, the points <math>(x_i , y_i )</math> and <math>(x_{i - 1} , y_{i - 1} )</math> are neighbors in the lattice of points with integer coordinates). Prove that the points in <math>S_n</math> cannot be partitioned into fewer than <math>n</math> paths (a partition of <math>S_n</math> into <math>m</math> paths is a set <math>\mathcal{P}</math> of <math>m</math> nonempty paths such that each point in <math>S_n</math> appears in exactly one of the <math>m</math> paths in <math>\mathcal{P}</math>). | ||
Line 18: | Line 16: | ||
* <url>Forum/viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url> | * <url>Forum/viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url> | ||
− | |||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] |
Revision as of 19:23, 1 May 2008
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>Forum/viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>