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> | ||
− | + | <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,< | + | |
+ | \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< | + | 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 and makes a sequence of jumps according to the following rule: from the frog jumps to which may be any of the points or There are points with that can be reached by a sequence of such jumps. Find the remainder when is divided by
Solution
First of all, it is easy to see by induction that for any in the frog's jump sequence, will be a multiple of and will be a multiple of The base case obviously satisfies the constraints and if and any of the four transformations will sustain this property:
So we know that any point the frog can reach will satisfy and
Any point in the form and is reachable.
\textbf{Proof:}a,$$ (Error compiling LaTeX. Unknown error_msg)b,$$ (Error compiling LaTeX. Unknown error_msg)c,dx=7a+2b-5c-10dy=2a+7b-10c-5dx+y = 9(a+b)-15(c+d) = 3nx-y = 5(a-b)+5(c-d) = 5m3(a+b)-5(c+d) = n(c+d) \equiv n \mod 3(a+b) = \lfloor{n/3}\rfloor + 2(c+d).(a-b)+(c-d) = m(a-b)(c-d)(a+b)(a-b)(c+d)(c-d)(a+b)n,(a-b)(c-d)(c+d)3(c-d)(a,b,c,d)x+y = 3nx-y = 5m\noindent\makebox[\linewidth]{\rule{\paperwidth}{0.4pt}}|x| + |y| \le 100,y=x-5my=-x+3n.(\frac{3n+5m}{2},\frac{3n-5m}{2}),mn|x| + |y| = |x \pm y|,$we find that
<cmath>
So there are$ (Error compiling LaTeX. Unknown error_msg)3433n,2021m.mnM34 \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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.