Difference between revisions of "2012 AIME I Problems/Problem 11"
m (Formatting+ Grammar.) |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==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{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. | ||
Line 38: | Line 37: | ||
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. | 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 49: | 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 | + | 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 20:32, 24 January 2021
Problem
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
such that there exists 2 integers
and
that satisfy
and
is reachable.
Denote the total amounts of each specific transformation in the frog's jump sequence to be
and
respectively. Then
,
,
, and
together must have integral solutions. But
implies
and thus
Similarly, implies that
and
have the same parity. Now in order for an integral solution to exist, there must always be a way to ensure that the pairs
and
and
and
have identical parities. The parity of
is completely dependent on
so the parities of
and
must be chosen to match this value. But the parity of
can then be adjusted by adding or subtracting
until it is identical to the parity of
as chosen before, so we conclude that it is always possible to find an integer solution for
and thus any point that satisfies
and
can be reached by the frog.
To count the number of such points in the region we first note that any such point will lie on the intersection of one line of the form
and another line of the form
The intersection of two such lines will yield the point
which will be integral if and only if
and
have the same parity. Now since
we find that
So there are possible odd values and
possible even values for
and
possible odd values and
possible even values for
Every pair of lines described above will yield a valid accessible point for all pairs of
and
with the same parity, and the number of points
is thus
.
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.