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 "2012 AIME I Problems/Problem 11"

(→‎Problem 11)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
 +
First of all, it is easy to see by induction that for any <math>P(x,y)</math> in the frog's jump sequence, <math>x+y</math> will be a multiple of <math>3</math> and <math>x-y</math> will be a multiple of <math>5.</math> The base case <math>(x,y) = (0,0)</math> obviously satisfies the constraints and if <math>x+y = 3n</math> and <math>x-y = 5m,</math> any of the four transformations will maintain this fact:
 +
 +
<cmath>
 +
\begin{align*}
 +
(x+7)+(y+2) = x+y+9 \rightarrow 3(n+3) &\text{ and } (x+7)-(y+2) = x-y+5 \rightarrow 5(m+1)\\
 +
(x+2)+(y+7) = x+y+9 \rightarrow 3(n+3) &\text{ and } (x+2)-(y+7) = x-y-5 \rightarrow 5(m-1)\\
 +
(x-5)+(y-10) = x+y-15 \rightarrow 3(n-5) &\text{ and } (x-5)-(y-10) = x-y+5 \rightarrow 5(m+1)\\
 +
(x-10)+(y-5) = x+y-15 \rightarrow 3(n-5) &\text{ and } (x-10)-(y-5) = x-y-5 \rightarrow 5(m-1).\\
 +
\end{align*}
 +
</cmath>
 +
 +
So we know that any point the frog can reach will satisfy <math>x+y = 3n</math> and <math>x-y = 5m.</math> To show that the frog can reach any such point, denote the total ammounts of each specific transformation in the frog's jump sequence to be <math>a,</math> <math>b,</math> <math>c,</math> and <math>d</math> respectively. Then <math>x=7a+2b-5c-10d</math> and <math>y=2a+7b-10c-5d</math> and the equations <math>x+y = 9(a+b)-15(c+d) = 3n</math> and <math>x-y = 5(a-b)+5(c-d) = 5m</math> must be solvable in integers. But <math>3(a+b)-5(c+d) = n</math> implies <math>(c+d) \equiv n \mod 3</math> and thus <math>(a+b) = \lfloor{n/3}\rfloor + 2(c+d).</math> Similarly <math>(a-b)+(c-d) = m</math> implies <math>(a-b)</math> and <math>(c-d)</math> have the same parity. Now in order for an integer solution to exist, there must always be a way to ensure <math>(a+b)</math> and <math>(a-b)</math> have identical parities and also <math>(c+d)</math> and <math>(c-d)</math> have identical parities. The parity of <math>(a+b)</math> is completely dependent on <math>n,</math> so the parities of <math>(a-b)</math> and <math>(c-d)</math> must be chosen to match this value. But the parity of <math>(c+d)</math> can then be adjusted by adding or subtracting <math>3</math> until it is identical to the parity of <math>(c-d)</math> as chosen before, so we conclude that it is always possible to find an integer solution for <math>(a,b,c,d)</math> and thus any point that satisfies <math>x+y = 3n</math> and <math>x-y = 5m</math> can be reached by the frog.
 +
 +
To count the number of such points in the region <math>|x| + |y| \le 100,</math> we first note that any such point will lie on the intersection of one line of the form <math>y=x-5m</math> and another line of the form <math>y=-x+3n.</math> The intersection of two such lines will yield the point <math>(\frac{3n+5m}{2},\frac{3n-5m}{2}),</math> which will be integral if and only if <math>m</math> and <math>n</math> have the same parity. Now since <math>|x| + |y| = |x \pm y|,</math> we find that
 +
 +
<cmath>
 +
\begin{align*}
 +
|x + y| = |3n| \le 100 &\rightarrow -33 \le n \le 33\\
 +
|x - y| = |5m| \le 100 &\rightarrow -20 \le m \le 20.
 +
\end{align*}
 +
</cmath>
 +
 +
So there are <math>34</math> possible odd values and <math>33</math> possible even values for <math>n,</math> and <math>20</math> possible odd values and <math>21</math> possible even values for <math>m.</math> Every pair of lines described above will yield a valid accessible point for all pairs of <math>m</math> and <math>n</math> with the same parity, and the number of points <math>M</math> is thus <math>34 \cdot 20 + 33 \cdot 21 = 1373 \rightarrow \boxed{373.}</math>
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2012|n=I|num-b=10|num-a=12}}
 
{{AIME box|year=2012|n=I|num-b=10|num-a=12}}

Revision as of 03:43, 17 March 2012

Problem 11

A frog begins at $P_0 = (0,0)$ and makes a sequence of jumps according to the following rule: from $P_n = (x_n, y_n),$ the frog jumps to $P_{n+1},$ which may be any of the points $(x_n + 7, y_n + 2),$ $(x_n + 2, y_n + 7),$ $(x_n - 5, y_n - 10),$ or $(x_n - 10, y_n - 5).$ There are $M$ points $(x, y)$ with $|x| + |y| \le 100$ that can be reached by a sequence of such jumps. Find the remainder when $M$ is divided by $1000.$

Solution

First of all, it is easy to see by induction that for any $P(x,y)$ in the frog's jump sequence, $x+y$ will be a multiple of $3$ and $x-y$ will be a multiple of $5.$ The base case $(x,y) = (0,0)$ obviously satisfies the constraints and if $x+y = 3n$ and $x-y = 5m,$ any of the four transformations will maintain this fact:

\begin{align*} (x+7)+(y+2) = x+y+9 \rightarrow 3(n+3) &\text{ and } (x+7)-(y+2) = x-y+5 \rightarrow 5(m+1)\\ (x+2)+(y+7) = x+y+9 \rightarrow 3(n+3) &\text{ and } (x+2)-(y+7) = x-y-5 \rightarrow 5(m-1)\\ (x-5)+(y-10) = x+y-15 \rightarrow 3(n-5) &\text{ and } (x-5)-(y-10) = x-y+5 \rightarrow 5(m+1)\\ (x-10)+(y-5) = x+y-15 \rightarrow 3(n-5) &\text{ and } (x-10)-(y-5) = x-y-5 \rightarrow 5(m-1).\\ \end{align*}

So we know that any point the frog can reach will satisfy $x+y = 3n$ and $x-y = 5m.$ To show that the frog can reach any such point, denote the total ammounts of each specific transformation in the frog's jump sequence to be $a,$ $b,$ $c,$ and $d$ respectively. Then $x=7a+2b-5c-10d$ and $y=2a+7b-10c-5d$ and the equations $x+y = 9(a+b)-15(c+d) = 3n$ and $x-y = 5(a-b)+5(c-d) = 5m$ must be solvable in integers. But $3(a+b)-5(c+d) = n$ implies $(c+d) \equiv n \mod 3$ and thus $(a+b) = \lfloor{n/3}\rfloor + 2(c+d).$ Similarly $(a-b)+(c-d) = m$ implies $(a-b)$ and $(c-d)$ have the same parity. Now in order for an integer solution to exist, there must always be a way to ensure $(a+b)$ and $(a-b)$ have identical parities and also $(c+d)$ and $(c-d)$ have identical parities. The parity of $(a+b)$ is completely dependent on $n,$ so the parities of $(a-b)$ and $(c-d)$ must be chosen to match this value. But the parity of $(c+d)$ can then be adjusted by adding or subtracting $3$ until it is identical to the parity of $(c-d)$ as chosen before, so we conclude that it is always possible to find an integer solution for $(a,b,c,d)$ and thus any point that satisfies $x+y = 3n$ and $x-y = 5m$ can be reached by the frog.

To count the number of such points in the region $|x| + |y| \le 100,$ we first note that any such point will lie on the intersection of one line of the form $y=x-5m$ and another line of the form $y=-x+3n.$ The intersection of two such lines will yield the point $(\frac{3n+5m}{2},\frac{3n-5m}{2}),$ which will be integral if and only if $m$ and $n$ have the same parity. Now since $|x| + |y| = |x \pm y|,$ we find that

\begin{align*} |x + y| = |3n| \le 100 &\rightarrow -33 \le n \le 33\\ |x - y| = |5m| \le 100 &\rightarrow -20 \le m \le 20. \end{align*}

So there are $34$ possible odd values and $33$ possible even values for $n,$ and $20$ possible odd values and $21$ possible even values for $m.$ Every pair of lines described above will yield a valid accessible point for all pairs of $m$ and $n$ with the same parity, and the number of points $M$ is thus $34 \cdot 20 + 33 \cdot 21 = 1373 \rightarrow \boxed{373.}$

See also

2012 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_AIME_I_Problems/Problem_11&oldid=45574"