Difference between revisions of "2012 AIME I Problems/Problem 11"
m (→Solution) |
|||
| Line 29: | Line 29: | ||
== 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}} | ||
Revision as of 19:28, 4 July 2013
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 
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 
and 
respectively. Then 
and 
and the equations 
and 
must be solvable in integers. But 
implies 
and thus 
Similarly 
implies 
and 
have the same parity. Now in order for an integer solution to exist, there must always be a way to ensure 
and have identical parities and also 
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 
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. 
