Difference between revisions of "2012 AIME I Problems/Problem 11"

(Solution)
Line 13: Line 13:
 
\end{align*}
 
\end{align*}
 
</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> 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.
+
<math>\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}</math>
 +
<math>\textbf{Lemma:}</math> Any point in the form <math>x+y = 3n</math> and <math>x-y = 5m</math> is reachable.  
  
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
+
 
 +
\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>\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}<math>
 +
 
 +
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>
 
<cmath>
Line 25: Line 31:
 
</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.}$
  
 
== 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}}

Revision as of 22:48, 6 July 2015

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

$\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}$ $\textbf{Lemma:}$ Any point in the form $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,$$ (Error compiling LaTeX. Unknown error_msg)b,$$ (Error compiling LaTeX. Unknown error_msg)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.$\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}$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

<cmath> |x+y|=|3n|10033n33|xy|=|5m|10020m20. </cmath>

So there are$ (Error compiling LaTeX. Unknown error_msg)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 (ProblemsAnswer KeyResources)
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