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"

m (More rigid wording.)
 
(4 intermediate revisions by 4 users not shown)
Line 1: Line 1:
−
==Problem 11==
+
==Problem==
 
A frog begins at <math>P_0 = (0,0)</math> and makes a sequence of jumps according to the following rule: from <math>P_n = (x_n, y_n),</math> the frog jumps to <math>P_{n+1},</math> which may be any of the points <math>(x_n + 7, y_n + 2),</math> <math>(x_n + 2, y_n + 7),</math> <math>(x_n - 5, y_n - 10),</math> or <math>(x_n - 10, y_n - 5).</math> There are <math>M</math> points <math>(x, y)</math> with <math>|x| + |y| \le 100</math> that can be reached by a sequence of such jumps. Find the remainder when <math>M</math> is divided by <math>1000.</math>
 
A frog begins at <math>P_0 = (0,0)</math> and makes a sequence of jumps according to the following rule: from <math>P_n = (x_n, y_n),</math> the frog jumps to <math>P_{n+1},</math> which may be any of the points <math>(x_n + 7, y_n + 2),</math> <math>(x_n + 2, y_n + 7),</math> <math>(x_n - 5, y_n - 10),</math> or <math>(x_n - 10, y_n - 5).</math> There are <math>M</math> points <math>(x, y)</math> with <math>|x| + |y| \le 100</math> that can be reached by a sequence of such jumps. Find the remainder when <math>M</math> is divided by <math>1000.</math>
  
Line 14: Line 14:
 
</cmath>
 
</cmath>
 
So we know that any point the frog can reach will satisfy <math>x+y = 3n</math> and <math>x-y = 5m.</math>  
 
So we know that any point the frog can reach will satisfy <math>x+y = 3n</math> and <math>x-y = 5m.</math>  
 +
---------------
 +
<math>\textbf{Lemma:}</math> Any point <math>(x,y)</math> such that there exists 2 integers <math>m</math> and <math>n</math> that satisfy <math>x+y = 3n</math> and <math>x-y = 5m</math> is reachable.
 +
 +
 +
<math>\textbf{Proof:}</math> Denote the total amounts 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>,
 +
 +
<math>y=2a+7b-10c-5d</math>,
 +
 +
<math>x+y = 9(a+b)-15(c+d) = 3n</math>, and
 +
 +
<math>x-y = 5(a-b)+5(c-d) = 5m</math>
  
−
<math>\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}</math>
+
together must have integral solutions. But
−
<math>\textbf{Lemma:}</math> Any point <math>(x,y)</math> such that there exists 2 integers <math>m</math> and <math>n</math> that satisfy <math>x+y = 3n</math> and <math>x-y = 5m</math> is reachable.
+
 
 +
<math>3(a+b)-5(c+d) = n</math> implies
  
 +
<math>(c+d) \equiv n \mod 3</math> and thus
  
−
<math>\textbf{Proof:}</math> Denote the total amounts 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.
+
<math>(a+b) = \lfloor{n/3}\rfloor + 2(c+d).</math>
−
<math>\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}</math>
 
  
 +
Similarly, <math>(a-b)+(c-d) = m</math> implies that <math>(a-b)</math> and <math>(c-d)</math> have the same parity. Now in order for an integral solution to exist, there must always be a way to ensure that the pairs <math>(a+b)</math> and <math>(a-b)</math> and <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>\left(\frac{3n+5m}{2},\frac{3n-5m}{2}\right),</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
 
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>\left(\frac{3n+5m}{2},\frac{3n-5m}{2}\right),</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
  
Line 31: Line 47:
 
</cmath>
 
</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>
+
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>.
 +
 
 +
== Video Solution by Richard Rusczyk ==
 +
 
 +
https://artofproblemsolving.com/videos/amc/2012aimei/351
 +
 
 +
~ dolphin7
  
 
== 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}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 19:32, 24 January 2021

Problem

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 sustain this property:

\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.$

$\textbf{Lemma:}$ Any point $(x,y)$ such that there exists 2 integers $m$ and $n$ that satisfy $x+y = 3n$ and $x-y = 5m$ is reachable.


$\textbf{Proof:}$ Denote the total amounts of each specific transformation in the frog's jump sequence to be $a,$ $b,$ $c,$ and $d$ respectively. Then

$x=7a+2b-5c-10d$,

$y=2a+7b-10c-5d$,

$x+y = 9(a+b)-15(c+d) = 3n$, and

$x-y = 5(a-b)+5(c-d) = 5m$

together must have integral solutions. 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 that $(a-b)$ and $(c-d)$ have the same parity. Now in order for an integral solution to exist, there must always be a way to ensure that the pairs $(a+b)$ and $(a-b)$ and $(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 $\left(\frac{3n+5m}{2},\frac{3n-5m}{2}\right),$ 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}$.

Video Solution by Richard Rusczyk

https://artofproblemsolving.com/videos/amc/2012aimei/351

~ dolphin7

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

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=2012_AIME_I_Problems/Problem_11&oldid=143152"