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 AIME II Problems/Problem 10"

(will finish)
(→‎Solution)
 
(2 intermediate revisions by 2 users not shown)
Line 15: Line 15:
 
We label our points using coordinates <math>0 \le x,y \le 3</math>, with the bottom-left point being <math>(0,0)</math>. By the [[Pythagorean Theorem]], the distance between two points is <math>\sqrt{d_x^2 + d_y^2}</math> where <math>0 \le d_x, d_y \le 3</math>; these yield the possible distances (in decreasing order)
 
We label our points using coordinates <math>0 \le x,y \le 3</math>, with the bottom-left point being <math>(0,0)</math>. By the [[Pythagorean Theorem]], the distance between two points is <math>\sqrt{d_x^2 + d_y^2}</math> where <math>0 \le d_x, d_y \le 3</math>; these yield the possible distances (in decreasing order)
 
<cmath>\sqrt{18},\ \sqrt{13},\ \sqrt{10},\ \sqrt{9},\ \sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2},\ \sqrt{1}</cmath>  
 
<cmath>\sqrt{18},\ \sqrt{13},\ \sqrt{10},\ \sqrt{9},\ \sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2},\ \sqrt{1}</cmath>  
−
As these define <math>9</math> lengths, so the maximum value of <math>m</math> is <math>10</math>. Because it is difficult to immediately impose restrictions on a path with increasing distances, we consider the paths in ''shrinking'' fashion. Note that the ''shrinking paths'' and ''growing paths'' are equivalent, but there are restrictions upon the locations of the first edges of the former.  
+
As these define <math>9</math> lengths, so the maximum value of <math>m</math> is <math>10</math>. For now, we assume that <math>m = 10</math> is achievable. Because it is difficult to immediately impose restrictions on a path with increasing distances, we consider the paths in ''shrinking'' fashion. Note that the ''shrinking paths'' and ''growing paths'' are equivalent, but there are restrictions upon the locations of the first edges of the former.  
  
−
The <math>\sqrt{18}</math> length is only possible for one of the long diagonals, which can be placed in <math>2</math> ways.
+
The <math>\sqrt{18}</math> length is only possible for one of the long diagonals, so our path must start with one of the <math>4</math> corners of the grid. [[Without loss of generality]] (since the grid is rotationally symmetric), we let the vertex be <math>(0,0)</math> and the endpoint be <math>(3,3)</math>.  
 
<center><asy>
 
<center><asy>
 
unitsize(0.25inch);
 
unitsize(0.25inch);
Line 27: Line 27:
 
dot((0,0)^^(3,3),s); draw((0,0)--(3,3));  
 
dot((0,0)^^(3,3),s); draw((0,0)--(3,3));  
 
</asy></center>
 
</asy></center>
−
Continuing,
+
The <math>\sqrt{13}</math> length can now only go to <math>2</math> points; due to reflectional symmetry about the main diagonal, we may WLOG let the next endpoint be <math>(1,0)</math>.
 
<center><asy>
 
<center><asy>
 
unitsize(0.25inch);
 
unitsize(0.25inch);
Line 35: Line 35:
 
for(j = 0; j < 4; ++j)
 
for(j = 0; j < 4; ++j)
 
dot(((real)i, (real)j));
 
dot(((real)i, (real)j));
−
dot((0,0)^^(3,3)^^(1,0),s); draw((0,0)--(3,3)); draw((3,3)--(1,0),c);  
+
dot((0,0)^^(3,3)^^(1,0),s); draw((0,0)--(3,3),c); draw((3,3)--(1,0));  
 
</asy></center>
 
</asy></center>
−
The rest are determined:
+
From <math>(1,0)</math>, there are two possible ways to move <math>\sqrt{10}</math> away, either to <math>(0,3)</math> or <math>(2,3)</math>. However, from <math>(0,3)</math>, there is no way to move <math>\sqrt{9}</math> away, so we discard it as a possibility.
 +
 
 +
From <math>(2,3)</math>, the lengths of <math>\sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2}</math> fortunately are all determined, with the endpoint sequence being <math>(2,3)-(2,0)-(0,2)-(2,1)-(0,1)-(1,2)</math>.
 
<center><asy>
 
<center><asy>
 
unitsize(0.25inch);
 
unitsize(0.25inch);
Line 46: Line 48:
 
dot(((real)i, (real)j));
 
dot(((real)i, (real)j));
 
dot((0,0)^^(3,3)^^(1,0)^^(2,3)^^(2,0)^^(0,2)^^(2,1)^^(0,1)^^(1,2),s); draw((0,0)--(3,3)--(1,0)--(2,3)--(2,0)--(0,2)--(2,1)--(0,1)--(1,2));
 
dot((0,0)^^(3,3)^^(1,0)^^(2,3)^^(2,0)^^(0,2)^^(2,1)^^(0,1)^^(1,2),s); draw((0,0)--(3,3)--(1,0)--(2,3)--(2,0)--(0,2)--(2,1)--(0,1)--(1,2));
−
The answer is $mr = 10 \cdot 24 = \boxed{240}$.
 
 
</asy></center>
 
</asy></center>
 +
From <math>(1,2)</math>, there are <math>3</math> possible lengths of <math>\sqrt{1}</math> (to either <math>(1,1),(2,2),(1,3)</math>). Thus, the number of paths is <math>r = 4 \cdot 2 \cdot 3 = 24</math>, and the answer is <math>mr = 10 \cdot 24 = \boxed{240}</math>.
  
 
== See also ==
 
== See also ==
Line 53: Line 55:
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 08:44, 25 November 2019

Problem

The diagram below shows a $4\times4$ rectangular array of points, each of which is $1$ unit away from its nearest neighbors.

[asy] unitsize(0.25inch); defaultpen(linewidth(0.7)); int i, j; for(i = 0; i < 4; ++i) for(j = 0; j < 4; ++j) dot(((real)i, (real)j)); [/asy]

Define a growing path to be a sequence of distinct points of the array with the property that the distance between consecutive points of the sequence is strictly increasing. Let $m$ be the maximum possible number of points in a growing path, and let $r$ be the number of growing paths consisting of exactly $m$ points. Find $mr$.

Solution

We label our points using coordinates $0 \le x,y \le 3$, with the bottom-left point being $(0,0)$. By the Pythagorean Theorem, the distance between two points is $\sqrt{d_x^2 + d_y^2}$ where $0 \le d_x, d_y \le 3$; these yield the possible distances (in decreasing order) \[\sqrt{18},\ \sqrt{13},\ \sqrt{10},\ \sqrt{9},\ \sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2},\ \sqrt{1}\] As these define $9$ lengths, so the maximum value of $m$ is $10$. For now, we assume that $m = 10$ is achievable. Because it is difficult to immediately impose restrictions on a path with increasing distances, we consider the paths in shrinking fashion. Note that the shrinking paths and growing paths are equivalent, but there are restrictions upon the locations of the first edges of the former.

The $\sqrt{18}$ length is only possible for one of the long diagonals, so our path must start with one of the $4$ corners of the grid. Without loss of generality (since the grid is rotationally symmetric), we let the vertex be $(0,0)$ and the endpoint be $(3,3)$.

[asy] unitsize(0.25inch); defaultpen(linewidth(0.7)); dotfactor = 4; pen s = linewidth(4); int i, j; for(i = 0; i < 4; ++i) for(j = 0; j < 4; ++j) dot(((real)i, (real)j)); dot((0,0)^^(3,3),s); draw((0,0)--(3,3)); [/asy]

The $\sqrt{13}$ length can now only go to $2$ points; due to reflectional symmetry about the main diagonal, we may WLOG let the next endpoint be $(1,0)$.

[asy] unitsize(0.25inch); defaultpen(linewidth(0.7)); dotfactor = 4; pen s = linewidth(4); pen c = rgb(0.5,0.5,0.5); int i, j; for(i = 0; i < 4; ++i) for(j = 0; j < 4; ++j) dot(((real)i, (real)j)); dot((0,0)^^(3,3)^^(1,0),s); draw((0,0)--(3,3),c); draw((3,3)--(1,0)); [/asy]

From $(1,0)$, there are two possible ways to move $\sqrt{10}$ away, either to $(0,3)$ or $(2,3)$. However, from $(0,3)$, there is no way to move $\sqrt{9}$ away, so we discard it as a possibility.

From $(2,3)$, the lengths of $\sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2}$ fortunately are all determined, with the endpoint sequence being $(2,3)-(2,0)-(0,2)-(2,1)-(0,1)-(1,2)$.

[asy] unitsize(0.25inch); defaultpen(linewidth(0.7)); dotfactor = 4; pen s = linewidth(4); pen c = rgb(0.5,0.5,0.5); int i, j; for(i = 0; i < 4; ++i) for(j = 0; j < 4; ++j) dot(((real)i, (real)j)); dot((0,0)^^(3,3)^^(1,0)^^(2,3)^^(2,0)^^(0,2)^^(2,1)^^(0,1)^^(1,2),s); draw((0,0)--(3,3)--(1,0)--(2,3)--(2,0)--(0,2)--(2,1)--(0,1)--(1,2)); [/asy]

From $(1,2)$, there are $3$ possible lengths of $\sqrt{1}$ (to either $(1,1),(2,2),(1,3)$). Thus, the number of paths is $r = 4 \cdot 2 \cdot 3 = 24$, and the answer is $mr = 10 \cdot 24 = \boxed{240}$.

See also

2008 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 9 		Followed by
Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME 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_AIME_II_Problems/Problem_10&oldid=112160"