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 18: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 ).
Contents
[hide]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>