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
![\[\left|x\right| + \left|y + \frac {1}{2}\right| < n\]](http://latex.artofproblemsolving.com/8/3/3/8334c1293747ba6149c9e89d65a64c248b66a3af.png)
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>
