Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution 1: asy)
m
 
(6 intermediate revisions by 4 users not shown)
Line 2: Line 2:
 
(''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>
 
<cmath>\left|x\right| + \left|y + \frac {1}{2}\right| < n</cmath>
−
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>).
 +
 
 +
== Solutions ==
  
−
__TOC__
 
−
== Solution ==
 
 
=== Solution 1 ===
 
=== Solution 1 ===
 +
Color all the points in <math>S_{n}</math> red or black such that each row of points starts and ends with a red point, and alternates between red and black for each point in the row. This creates a checkerboard pattern, except that the middle two rows are identical. 
 
<center><asy>
 
<center><asy>
 
/* variable declarations */
 
/* variable declarations */
Line 23: Line 24:
 
  }
 
  }
 
}
 
}
−
draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a red line */
+
draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */
−
</asy>
+
</asy>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<asy>
−
<div style="font-size:85%">Example for <math>n=4</math></div></center>
+
/* variable declarations */
−
Color all the points in <math>S_{n}</math> red or black such that each row of points starts and ends with a red point, and alternates between red and black for each point in the row. This creates a checkerboard pattern, except that the middle two rows are identical.
+
int n = 4;
 +
 
 +
/* code */
 +
pen r = red, b = black;
 +
int absol(int k){if(k >= 0) return k; else return -1*k-1;}
 +
pen col(bool k){if(k) return r; else return b;}
 +
 
 +
for(int y = -n; y < n; ++y){
 +
bool b = true;
 +
for(int x = absol(y)-n+1; x < n-absol(y); ++x){
 +
  dot((x,y),col(b));
 +
  b = !b;
 +
}
 +
}
 +
draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */
 +
draw((-1,2)--(-1,1)--(0,1)--(1,1)--(1,0),linewidth(0.7)); draw((1,0)--(1,-1),linetype("3 3")+linewidth(0.7)); draw((1,-1)--(1,-2)--(2,-2),linewidth(0.7));
 +
</asy><div style="font-size:85%">Examples for <math>n=4</math></div></center>
 +
 
 +
Suppose there is a partition of <math>m < n</math> paths that works. For each of the <math>m</math> paths, we break a path into two separate paths wherever there are consecutive red points. This only happens only with the <math>n</math> red pairs in the middle two rows. We now have <math>m + l,\, l \le n</math> paths whose colors are strictly alternating. In a path with alternating colors, there can be at most one more red dot than the number of black dots (which occurs when both endpoints are red). Thus there can be no more than <math>m + l</math> red dots than black dots in <math>S_n</math>.  
  
−
There are <math>2n</math> more red points than black points, and we can only "recover" red points by having paths whose endpoints are both red (this can only happen <math>n - 1</math> times, once for each path) or by using the adjacent red squares in the middle two rows (there are only <math>n</math> such pairs).  Therefore we can't make up for those <math>2n</math> extra red points, so there's no partition into fewer than <math>n</math> paths.
+
There are <math>2n</math> more red points than black points, so
 +
<cmath>2n \le m + l \le m + n</cmath>
 +
which implies that <math>n \le m</math>, contradiction.  
  
 
=== Solution 2 ===
 
=== Solution 2 ===
 
Suppose you have a partition of less than <math>n</math> paths. Then start from <math>(0,n - 1)</math> and work your way down to <math>(0, - n)</math> along the right edge of <math>S_n</math> performing the following algorithm when going from each point.
 
Suppose you have a partition of less than <math>n</math> paths. Then start from <math>(0,n - 1)</math> and work your way down to <math>(0, - n)</math> along the right edge of <math>S_n</math> performing the following algorithm when going from each point.
  
−
(example of described path for <math>S_4</math>)
+
<center><asy>
−
[code]...V...
+
/* variable declarations */
−
..o>V..
+
int n = 4;
−
.ooo>V.
+
 
−
ooooo>V
+
/* code */
−
oooooV<
+
int absol(int k){if(k >= 0) return k; else return -1*k-1;}
−
.oooV<.
+
 
−
..oV<..
+
for(int y = -n; y < n; ++y){
−
...X...
+
for(int x = absol(y)-n+1; x < n-absol(y); ++x){
 +
  dot((x,y),black);
 +
  /* label((string) x + " " + (string) y, (x,y), SE); */
 +
 +
  /* addendum */
 +
 
 +
  if((x==n-absol(y)-1 && y >= 0) || (x==n-absol(y)-2 && y < 0)){
 +
  draw((x,y-0.2)--(x,y-0.8),EndArrow);
 +
  }
 +
  if(x==n-absol(y)-2 && y >= 0){
 +
  draw((x+0.2,y)--(x+0.8,y),EndArrow);
 +
  }
 +
  if(x==n-absol(y)-1 && y < 0 && y > -n){
 +
  draw((x-0.2,y)--(x-0.8,y),EndArrow);
 +
  }
 +
}
 +
}
 +
draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */
 +
dot((0,-n),linewidth(5)+red);
 +
 
 +
</asy>
 +
<div style="font-size:85%">Example for <math>S_4</math></div></center>
  
 
If a path already has the point you're coming from and the point you're going to as adjacent in the path, do nothing.
 
If a path already has the point you're coming from and the point you're going to as adjacent in the path, do nothing.
Line 49: Line 91:
 
If not the first case, and there is exactly one endpoint among the point you're coming from and the point you're going to, remove a segment from the one in the middle of a path (paths +1) and now you have two endpoints; join them (paths -1). If the point in the middle of the path is the one you're coming from, remove the segment that doesn't come from the point that came before it. The number of paths remains the same.
 
If not the first case, and there is exactly one endpoint among the point you're coming from and the point you're going to, remove a segment from the one in the middle of a path (paths +1) and now you have two endpoints; join them (paths -1). If the point in the middle of the path is the one you're coming from, remove the segment that doesn't come from the point that came before it. The number of paths remains the same.
  
−
If not the first case, and both points are in the middle of a path... well this is impossible. Since the two points are in the middle of the path, they are adjacent to two other points. But they are also adjacent to each other, so both are adjacent to at least three points. And now you can prove, looking at the path we're going to, that no two points adjacent to at least three others are travelled consecutively.
+
If not the first case, and both points are in the middle of a path, which is impossible. Since the two points are in the middle of the path, they are adjacent to two other points. But they are also adjacent to each other, so both are adjacent to at least three points. Then, no two points adjacent to at least three others are travelled consecutively.
  
−
So given any configuration we can create the path shown above without increasing the number of paths. The remaining points form <math>S_{n - 1}</math>. Now suppose for some positive integer <math>n</math>, we have a partition into less than <math>n</math> paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than <math>n - 1</math> paths. Apply the algorithm again. Repeat until we show that <math>S_1</math> is partitioned into less than <math>1</math> path. This is absurd, and we're done.
+
Thus, given any configuration we can create the path shown above without increasing the number of paths. The remaining points form <math>S_{n - 1}</math>. Now suppose for some positive integer <math>n</math>, we have a partition into less than <math>n</math> paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than <math>n - 1</math> paths. Apply the algorithm again. Repeat until we show that <math>S_1</math> is partitioned into less than <math>1</math> path, contradiction.
  
 
=== Solution 3 ===
 
=== Solution 3 ===
Line 63: Line 105:
  
 
Let the number of 0-degree vertices be <math>a</math>, 1-degree vertices be <math>b</math>, 2-degree vertices be <math>c</math>, 3-degree vertices be <math>d</math>, and 4-degree vertices be <math>e</math>. Since all the vertices began as 2-degree or higher, <math>2a + b\le2n - 2 - m</math>. Moreover, the total degree is <math>b + 2c + 3d + 4e = 2(2n^2) + (d + 2e) - (b + 2a) = 4n^2 - 2n + 2 + 2m</math>. So <math>d + 2e = b + 2a - (2n - 2 + 2m)\le (2n - 2 - m) - (2n - 2 - 2m) = m</math> So we can use our last <math>m</math> edges to remove any excess degree on vertices with degree 3 or 4, yielding <math>H_n</math>.
 
Let the number of 0-degree vertices be <math>a</math>, 1-degree vertices be <math>b</math>, 2-degree vertices be <math>c</math>, 3-degree vertices be <math>d</math>, and 4-degree vertices be <math>e</math>. Since all the vertices began as 2-degree or higher, <math>2a + b\le2n - 2 - m</math>. Moreover, the total degree is <math>b + 2c + 3d + 4e = 2(2n^2) + (d + 2e) - (b + 2a) = 4n^2 - 2n + 2 + 2m</math>. So <math>d + 2e = b + 2a - (2n - 2 + 2m)\le (2n - 2 - m) - (2n - 2 - 2m) = m</math> So we can use our last <math>m</math> edges to remove any excess degree on vertices with degree 3 or 4, yielding <math>H_n</math>.
 +
  
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
−
== Resources ==
+
== See also==
 +
* <url>viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>
 +
 
 
{{USAMO newbox|year=2008|num-b=2|num-a=4}}
 
{{USAMO newbox|year=2008|num-b=2|num-a=4}}
−
 
−
* <url>viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>
 
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 00:00, 14 August 2014

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}$).

Solutions

Solution 1

Color all the points in $S_{n}$ red or black such that each row of points starts and ends with a red point, and alternates between red and black for each point in the row. This creates a checkerboard pattern, except that the middle two rows are identical.

[asy] /* variable declarations */ int n = 4; /* code */ pen r = red, b = black; int absol(int k){if(k >= 0) return k; else return -1*k-1;} pen col(bool k){if(k) return r; else return b;} for(int y = -n; y < n; ++y){ bool b = true; for(int x = absol(y)-n+1; x < n-absol(y); ++x){ dot((x,y),col(b)); b = !b; } } draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */ [/asy]         [asy] /* variable declarations */ int n = 4; /* code */ pen r = red, b = black; int absol(int k){if(k >= 0) return k; else return -1*k-1;} pen col(bool k){if(k) return r; else return b;} for(int y = -n; y < n; ++y){ bool b = true; for(int x = absol(y)-n+1; x < n-absol(y); ++x){ dot((x,y),col(b)); b = !b; } } draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */ draw((-1,2)--(-1,1)--(0,1)--(1,1)--(1,0),linewidth(0.7)); draw((1,0)--(1,-1),linetype("3 3")+linewidth(0.7)); draw((1,-1)--(1,-2)--(2,-2),linewidth(0.7)); [/asy]
Examples for $n=4$

Suppose there is a partition of $m < n$ paths that works. For each of the $m$ paths, we break a path into two separate paths wherever there are consecutive red points. This only happens only with the $n$ red pairs in the middle two rows. We now have $m + l,\, l \le n$ paths whose colors are strictly alternating. In a path with alternating colors, there can be at most one more red dot than the number of black dots (which occurs when both endpoints are red). Thus there can be no more than $m + l$ red dots than black dots in $S_n$.

There are $2n$ more red points than black points, so \[2n \le m + l \le m + n\] which implies that $n \le m$, contradiction.

Solution 2

Suppose you have a partition of less than $n$ paths. Then start from $(0,n - 1)$ and work your way down to $(0, - n)$ along the right edge of $S_n$ performing the following algorithm when going from each point.

[asy] /* variable declarations */ int n = 4; /* code */ int absol(int k){if(k >= 0) return k; else return -1*k-1;} for(int y = -n; y < n; ++y){ for(int x = absol(y)-n+1; x < n-absol(y); ++x){ dot((x,y),black); /* label((string) x + " " + (string) y, (x,y), SE); */ /* addendum */ if((x==n-absol(y)-1 && y >= 0) || (x==n-absol(y)-2 && y < 0)){ draw((x,y-0.2)--(x,y-0.8),EndArrow); } if(x==n-absol(y)-2 && y >= 0){ draw((x+0.2,y)--(x+0.8,y),EndArrow); } if(x==n-absol(y)-1 && y < 0 && y > -n){ draw((x-0.2,y)--(x-0.8,y),EndArrow); } } } draw((0.5,0.5)--(0.5,1.5),white); /* to force rendering by using a white line */ dot((0,-n),linewidth(5)+red); [/asy]
Example for $S_4$

If a path already has the point you're coming from and the point you're going to as adjacent in the path, do nothing.

If not the first case, and the point you're coming from and the point you're going to are both endpoints of paths, join them (one less path).

If not the first case, and there is exactly one endpoint among the point you're coming from and the point you're going to, remove a segment from the one in the middle of a path (paths +1) and now you have two endpoints; join them (paths -1). If the point in the middle of the path is the one you're coming from, remove the segment that doesn't come from the point that came before it. The number of paths remains the same.

If not the first case, and both points are in the middle of a path, which is impossible. Since the two points are in the middle of the path, they are adjacent to two other points. But they are also adjacent to each other, so both are adjacent to at least three points. Then, no two points adjacent to at least three others are travelled consecutively.

Thus, given any configuration we can create the path shown above without increasing the number of paths. The remaining points form $S_{n - 1}$. Now suppose for some positive integer $n$, we have a partition into less than $n$ paths. Apply the algorithm to make the path shown above. Then the remaining points are partitioned into less than $n - 1$ paths. Apply the algorithm again. Repeat until we show that $S_1$ is partitioned into less than $1$ path, contradiction.

Solution 3

We induct on $n$ to prove that an $n - 1$-path partition is impossible. This can be restated as saying that we cannot fit $2n^2 - n + 1$ edges into the graph with each vertex having degree at most 2. The base case is trivial (2 edges when there only is 1). Suppose it was possible for $n + 1$, and we'll prove it's possible for $n$.

Call the 'complete' network (graph) of points $G_{n + 1}$ and the $n$-path partition for $n + 1$ is a subgraph of $G_{n + 1}$, $H_{n + 1}$. There are a total of $2(n + 1)^2 - n = 2n^2 + 3n + 2$ edges in $H_{n + 1}$ out of $4n^2 + 4n + 1$ in $G_{n + 1}$ (not hard to prove), and each vertex has maximum order 2. Now consider the complement of $H_{n + 1}$ in $G_{n + 1}$, that is, take all the edges in $G_{n + 1}$ that are not in $H_{n + 1}$ and of course all the vertices. Call this $F_{n + 1}$ We will trim $F_{n + 1}$ down a bit to get $H_n$.

First, call the points in $S_{n + 1}$ but not $S_n$ exterior points, and the points in $S_n$ interior points. $F_{n + 1}$ has $2n^2 + n - 1$ edges. Since the interior points have degree 4 in $G_{n + 1}$, they have degree at least 2 in $F_{n + 1}$, for a total degree of $4n^2 + m$ where $0\le m\le 2n - 2$ since the total overall degree is $2(2n^2 + n - 1) = 4n^2 + 2n - 2$. This makes the total degree of the exterior points $2n - 2 - m$. Since the exterior points are not connected in $G_{n + 1}$, these $2n - 2 - m$ edges must connect on exterior point to an interior point.

I then take away $2n - 2$ edges and the exterior points, yielding $2n^2 - n + 1$ edges and the interior points, which is $H_n$, as follows: First take away those $2n - 2 - m$ interior-exterior edges and shave off all the exterior points. Then the total degree (now just of the interior points) must be $4n^2 - 2n + 2 + 2m$.

Let the number of 0-degree vertices be $a$, 1-degree vertices be $b$, 2-degree vertices be $c$, 3-degree vertices be $d$, and 4-degree vertices be $e$. Since all the vertices began as 2-degree or higher, $2a + b\le2n - 2 - m$. Moreover, the total degree is $b + 2c + 3d + 4e = 2(2n^2) + (d + 2e) - (b + 2a) = 4n^2 - 2n + 2 + 2m$. So $d + 2e = b + 2a - (2n - 2 + 2m)\le (2n - 2 - m) - (2n - 2 - 2m) = m$ So we can use our last $m$ edges to remove any excess degree on vertices with degree 3 or 4, yielding $H_n$.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

  • <url>viewtopic.php?t=202936 Discussion on AoPS/MathLinks</url>
2008 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_USAMO_Problems/Problem_3&oldid=63056"