Mock AIME 2 2010 Answer Key
Return to Mock AIME 2 2010
- 804
- 683
- 401
- 392
- 416
- 108
- 756
- 028
- 135
- 041
- 164
- 256
- 385
- 167
- 860
Mock AIME 2 2010 (Problems • Answer Key • Resources) | ||
Preceded by Mock AIME 1 2010 |
Followed by Mock AIME 1 2011 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
Unformatted Solutions
- Written by the problem authors. See the external links at Mock AIME 2 2010.
There are 2010 lemmings. At each step, we may separate the lemmings into groups of 5 and purge the remainder, separate them into groups of 3 and purge the remainder, or pick one lemming and purge it. Find the smallest number of steps necessary to remove all 2010 lemmings. (Alex Zhu)
%%Solution 1
Notice that removing as many lemmings as possible at each step (i.e., using the greedy algorithm) is optimal. This can be easily proved through strong induction. Starting from 2010, which is a multiple of 15, we must first purge 1 lemming. We can then purge 4 lemmings by using groups of 5. Then, we can use groups of 3 followed by groups of 5 to reduce it to 5 less. We can repeat this step again, and we will end up at . This process can be repeated every for every 15 lemmings, so since it takes 6 steps to clear 15 lemmings, it will take us
to remove all the lemmings.
%%Problem 2
Let
be nonnegative integers such that
, and define
so that
, with
for
. Given that
can take on
distinct values, find the remainder when
is divided by 1000. (Alex Zhu)
%%Solution 2
For any , since
for
, therefore,
. Also, note that for any
that satisfies
, there exists a corresponding
such that
(let
for
, and
.) Therefore, we are just trying to count the number of
that satisfy
. To do this, we note that for any of the
possible ways to pick
, there is exactly 1 possible value of
that works. Therefore, the total number of possibilities is
.
%%Problem 3
Five gunmen are shooting each other. At the same moment, each randomly chooses one of the other four to shoot. The probability that there are some two people shooting each other can be expressed in the form
, where
are relatively prime positive integers. Find
. (Tim Wu)
We will count how many distinct arrangements (choices of target for each gunman) result in a pair shooting each other, and divide this by the total number of arrangements, . For any pair to shoot each other, the two shoot each other in exactly one way, while the other three people shoot any of their 4 targets. There are 10 possible pairs, giving a count of
this way. However, we must account for the overcount caused by 2 pairs shooting each other simultaneously. We can choose one person who is not in the pair in 5 ways, and then of the following people, say A, B, C, and D, we make A shoot one of the others in 3 possible ways (the remaining people can shoot each other in only one other way.) Finally, the lone person can shoot whomever he so desires in 4 ways, giving
total possibilities. Our probability is then
, so our answer is
.
%%Problem 4
Anderson is bored in physics class. His favorite numbers are 1, 7, and 33. He randomly writes 0., and then writes down a long string consisting of those numbers juxtaposed against one another (e.g., 0.1337173377133...) on a sheet of paper. Since physics class is infinitely long, he writes an infinitely long decimal number. If the expected value of the number he wrote down is of the form
, where
and
are relatively prime positive integers, find
. (Alex Zhu)
%%Solution 4
Let be the expected value of the number Anderson writes. Consider the first segment of the number Anderson writes. If it is 1, then the number will begin with 1, and the remaining part will have an expected value of
(the expected value of the original number only moved down a digit). Thus, in this case, his number will average
. Similarly, if he writes 7, his number will average
, and if he writes 33, his number will average
. Each of these cases happens with equal probability, so we have
\begin{align*}
E&=
\\
300E &= 10+10E+70+10E+33+E \\
279E &= 113 \\
E &=
.
\end{align*}
Our answer is therefore
.
%%Problem 5
Let
. Find the three rightmost nonzero digits of the product of the coefficients of
. (Alex Zhu)
%%Solution 5
First, note that each of the possible coefficients is multiplied by a different power of
, because there are also
different powers of
in total (this follows from the fact that every positive integer can be written uniquely as a sum of powers of 2; the coefficient of
, where
, is obtained from multiplying together all
with
.) Therefore, we are trying to find the product of the product of all of the elements of subsets of the set
(where the product of the elements of the empty set is taken to be 1). If we pair each subset
with its complement, we will have 16 pairs of subsets, each of which multiply together to
, so the product of all of the subsets is
. Since we want the last three nonzero digits, we simply wish to find
. To make this easier, we will find it modulo 8 and modulo 125 and use the Chinese remainder theorem to find the answer.
, and
.
We can now see that because and
, the only number that is
and
is
.
%%Problem 6
\item
Let
denote the set
, and define
, where
is a subset of the positive integers, to output the greatest common divisor of all elements in
, unless
is empty, in which case it will output 0. Find the last three digits of
, where
ranges over all subsets of
. (George Xing)
%%Solution 6
Let denote the number of subsets
such that
. Our answer will be the sum
.
For any positive integer , we note that the non-empty sets satisfying the property that
is a multiple of
are exactly the non-empty sets whose elements are multiples of
. Hence, the number of such sets is
, where
(as there are
multiples of
between 1 and 10 inclusive.) On the other hand, the number of such sets is
, that is, the sum of the number of sets
such that
is
,
is
,
is
, etc., so we have that
. By setting
, we see that
\begin{align*}
a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7 + a_8 + a_9 + a_{10} &= 2^{10} - 1 = 1023 \\
a_2 + a_4 + a_6 + a_8 + a_{10} &= 2^5 - 1 = 31 \\
a_3 + a_6 + a_9 &= 2^3 - 1 = 7 \\
a_4 + a_8 &= 2^2 - 1 = 3 \\
a_5 + a_{10} &= 2^2 - 1 = 3 \\
a_6 &= 2^1 - 1 = 1 \\
a_7 &= 2^1 - 1 = 1 \\
a_8 &= 2^1 - 1 = 1 \\
a_9 &= 2^1 - 1 = 1 \\
a_{10} &= 2^1 - 1 = 1
\end{align*}
We can easily solve this system of equations to find ,
,
,
,
, and
. Our answer is therefore
.
%%Problem 7
\setcounter{enumi}{6}
Find the number of functions from
to itself such that
for all
. (Alex Zhu)
%%Solution 7
For a function , let
be the set of values that are fixed, let
be the set of values that evaluate to an element in
but are not elements of
themselves, and let
be the set of the remaining values. Notice that all possible values of
are in
, so
must be nonempty. We will now use casework on the size of
.
\textbf{Case 1: } .\\
WLOG, let
, so we will multiply our result by 5 at the end. Now, let
, so
. We must have
for all
, so each element
in
must satisfy
for some
in
, because
and the only other numbers for which
are the elements of b. This also implies
. Conversely, it is easy to check any function satisfying
works, so the total number of functions in this case is
because there are
ways to choose the elements in
, and each of the
elements in C can map to any of the
elements in B. This sum evaluates to
, so there are 205 functions in this case.
\textbf{Case 2: } .\\
This is very similar to case 1, except for the fact that each element in
can now correspond to one of two possible elements in
, so this adds a factor of
. The sum is
, so there are 380 functions in this case.
\textbf{Case 3: } .\\
The sum is
, so there are 150 functions in this case.
\textbf{Case 4: } .\\
There are clearly
functions in this case.
\textbf{Case 5: } .\\
There is a total of 1 function (the identity) in this case.
Adding everything up, we see that our final answer is .
%%Problem 8
\setcounter{enumi}{7}
In triangle ,
,
, and
. In addition, there is a point
lying on segment
such that
. Given that the length of the radius of the circle through
and
that is tangent to side
can be expressed in the form
, where
and
are relatively prime integers, find
. (Alex Zhu)
%%Solution 8
\begin{sol1}
Let be the point of tangency of the circle with
. By power of a point,
, that is,
, giving
and
. Since
,
, so
and
. Since the circle is tangent to
, we have that
. By the extended law of sines, the circumdiameter of
(that is, the radius of our circle) is
. Therefore, the radius is
, giving an answer of
.
\end{sol1}
\begin{sol2}
Let O be the center of the circle, and let points E and F to be the perpendiculars from O to AC and BC, respectively. First, by power of a point, we have , so
, giving
and
. Now, let
be the radius of the circle. We have
, so
. By the Pythagorean theorem on triangle FOB, we have
. Finally, we have
, so
. Hence,
, giving us an answer of
.
\end{sol2}
%%Problem 9
\setcounter{enumi}{8}
Given that are reals such that
, the largest possible value of
can be expressed in the form
, where
and
are integers,
is a positive integer not divisible by the square of any prime, and
is a positive integer such that
. Find
. (Alex Zhu)
%%Solution 9
\begin{align*}
16\sin^4(x+y) + 49\cos^4(x+y)
&= \sin^2(2x + 2y)\left(8\sin^2(x+z) + 6\cos^2(y+z)\right) \\
&\leq 14 \sin^2(2x + 2y) \\
&= 56(\sin(x+y) \cos(x+y))
\end{align*}
Hence, , yielding
, or
, for some integer
. Furthermore, we must have
, so
and
for some integers
and
. Hence,
, so
. Hence,
, giving us
. This is attained when
, which indeed occurs if we pick
,
, and
, so our answer is
.
%%Problem 10
\setcounter{enumi}{9}
How many positive integers satisfy
, where
is the number of positive integers less than or equal to
relatively prime to
? (Alex Zhu)
%%Solution 10
If , then
. Now, suppose
is not a power of 2. Let
, where
is odd.
. If
, where
and
are distinct odd prime numbers and
is some integer, then
. Since
and
are odd,
and
are even, so
. Hence,
, so
.
It follows that has at most one other prime factor, so
is of the form
.
, so
. Hence,
, so
. But
, so we must have that
.
We now note that ,
, is even, and hence does not divide
. But
, so we wish to find the number of integers less than or equal to 2010 of the form
such that
implies
.
When ,
giving one possible value of
. For any larger
(as
), we have
, yieding
possible values of
. Summing these values for
gives us the answer of
.
%%Problem 11
\setcounter{enumi}{10}
Let be a function such that
For example,
, where we are summing over the triples
, and
. Find the last three digits of
. (Mitchell Lee)
%%Solution 11
. For any
that divides
, the number of sums that
will be in is exactly three the number of ordered pairs
we can find such that
, which in turn is just
, where
is the number of divisors of
(
can be any divisor of
, and
.) (The factor of three arises from the fact that
and
are to be taken account as well.) Hence,
. Since the set
is the same as the set
,
, that is,
for all
.
Note that if and
are relatively prime integers, then
and
. Hence,
since every divisor of
can be expressed uniquely as a product of a divisor of
and as a divisor of
(upon expanding the product using the distributive property, it follows that we are summing over the set of all numbers of the form
, where
and
, which is exactly the set divisors of
.)
It follows that
\begin{align*}
3 f(30^3)
&= 3 \sum_{d | 30^3} d \tau(d) \\
&= 3 \left(\sum_{d | 2^3} d \tau(d) \right) \left(\sum_{d | 3^3} d \tau(d) \right) \left(\sum_{d | 5^3} d \tau(d) \right) \\
&= 3 \left(1 \cdot 1 + 2 \cdot 2 + 3 \cdot 4 + 4 \cdot 8 \right) \left(1 \cdot 1 + 2 \cdot 3 + 3 \cdot 9 + 4 \cdot 27\right) \left( 1 \cdot 1 + 2 \cdot 5 + 3 \cdot 25 + 4 \cdot 125 \right) \\
&= 3 \cdot 49 \cdot 142 \cdot 586
\end{align*}
The last three digits of this product can easily be computed to be .
%%Problem 12
\setcounter{enumi}{11}
Let Find the sum of digits of
in base-100. (Tim Wu)
%%Solution 12
\begin{sol1}
Let We seek to find
.
We shall prove by induction that . Our base case,
, follows from the fact that
by the binomial theorem. Now, we note that
. Assuming that
for all integers
with
, we have that
\begin{align*}
f(n,k)&=\sum_{i=0}^{k} \binom{k}{i} f(n-1,i) \\
&= \sum_{i=0}^k \binom{k}{i} n^i \\
&= (n+1)^k,
\end{align*}
where the last step follows from the binomial theorem.
Thus, we have . To express this in base-100, we notice that
. Since
, there are no ``carry-overs, so the sum of digits in base-100 will simply be
.
\end{sol1}
\begin{sol2}
Let . The number of 101-tuples of sets
, such that
is equal to
;
tells the number of ways to pick
elements from
,
elements from
, etc.
We shall now count another way. Consider all 8-digit (leading digits can be 0) base 101 integers; there are clearly
such integers. Let
be the set of all
such that the
-th digit is greater than or equal to
; then we have that
. Conversely, for any 101-tuple of sets
such that
, we can construct an 8-digit base 101 integer from this set, by having the digit
be the largest integer
such that
.
Hence, . We proceed as we did before to find the sum of the digits of
when it is written in base 100 to arrive at our answer of
.
\end{sol2}
%%Problem 13
\setcounter{enumi}{12}
is inscribed in circle
. The radius of
is 285, and
. When the incircle of
is reflected across segment
, it is tangent to
. Given that the inradius of
can be expressed in the form
, where
and
are positive integers and
is not divisible by the square of any prime, find
. (Alex Zhu)
%%Solution 13
\begin{sol1}
We shall prove that in a circle with center
, radius
, a chord
with midpoint
such that
, and a point
on
such that the incircle
of
with radius
, when reflected across
, is tangent to
, we have that
.
Let be the incenter of
, let
be the reflection of
across
(hence, it is the center of the reflection of the incircle of
across
), and let
be the reflection of
across
.
is an isosceles trapezoid, so it is cyclic. Hence, by Ptolemy's theorem,
. In other words,
, since
and
. But
, since the reflection of
across
is tangent to
, and
by Euler's distance formula, so
, yielding
.
It therefore suffices to find . By the Pythagorean theorem, since
is right, we have that
, so
\begin{align*}
m
&= \sqrt{285^2 - \frac{567^2}{4}} \\
&= \sqrt{\frac{570^2 - 567^2}{4}} \\
&= \frac{\sqrt{(570 - 567)(570 + 567)}}{2} \\
&= \frac{\sqrt{3 \cdot 1137}}{2} \\
&= \frac{3 \sqrt{379}}{2}.
\end{align*}
Hence,
, giving us an answer of
.
\end{sol1}
\begin{sol2}
We shall prove that in another way that a circle with center
, radius
, a chord
with midpoint
such that
, and a point
on
such that the incircle
of
with radius
, when reflected across
, is tangent to
, we have that
.
Let be the incenter of
, and let
be the reflection of
across
(hence, it is the center of the reflection of the incircle of
across
.) Let
be the foot of the perpendicular from
to
. We have that
and
by Euler's distance formula, so
. In addition,
and
, since the reflection of
across
is tangent to
. Sine
is right, we have that
, that is,
, again yielding
.
We simply compute the answer the way we did before to arrive at an answer of .
\end{sol2}
%%Problem 14
\setcounter{enumi}{13} Alex and Mitchell decide to play a game. In this game, there are 2010 pieces of candy on a table, and starting with Alex, the two take turns eating some positive integer number of pieces of candy. Since it is bad manners to eat the last candy, whoever eats the last candy loses. The two decide that the amount of candy a person can pick will be a set equal to the positive divisors of a number less than 2010 that each person picks (individually) from the beginning. For example, if Alex picks 19 and Mitchell picks 20, then on each turn, Alex must eat either 1 or 19 pieces, and Mitchell must eat 1, 2, 4, 5, 10, or 20 pieces. Mitchell knows Alex well enough to determine with certainty that Alex will either be immature and pick 69, or be clich\'ed and pick 42. How many integers can Mitchell pick to guarantee that he will not \emph{lose the game}? (George Xing)
%%Solution 14
We claim that Mitchell has a winning strategy if and only if the number he picks is a multiple of 12. To show that he has a winning strategy whenever the number he picks is a multiple of 5, it is clearly sufficient to show that Mitchell has a winning strategy when Mitchell's number is 12.
Note that Mitchell has 1, 2, 3, and 4 among his divisors, and that no matter which number Alex chooses, Alex will not have a multiple of 4. Therefore, after Alex's first turn, let Mitchell choose one of his divisors so that the remaining number of pieces of candy on the table is congruent to 1 modulo 4. As Alex cannot decrease the amount of candy by a multiple of 4, he cannot force Mitchell to lose (as Mitchell can only be forced to lose if he is left with 1 piece of candy on the table.) Because Mitchell cannot be forced to lose, Mitchell has a winning strategy.
We shall now show that if Mitchell does not pick a multiple of 3, then Mitchell cannot guarantee a victory. Alex can pick 42, which have 1, 2, and 3 among its divsiors. Therefore, Alex can play so that he always forces Mitchell to carry out his move when the number of pieces remaining on the table is congruent to 1 modulo 3. As the number of pieces of candy that Mitchell removes cannot be a multiple of 3, Alex will never have to move on a table with the number of pieces on the table congruent to 1 modulo 3. Hence, Alex cannot be forced to lose, so Alex has a winning strategy, and Mitchell does not.
We shall now show that if Mitchell does not pick a multiple of 4, then he cannot guarentee a victory. Alex can pick 42, which have 1, 2, and 3 among its divisors. On Alex's first turn, he can pick a 1. Thereon, as Mitchell cannot pick a number that is a multiple of 4, Alex can play so that after his move, the number of pieces of candy remaining on the board is congruent to 1 modulo 4. Again, as Mitchell cannot pick a number that is a multiple of 4, Alex will never have to make his move when the number of pieces of candy remaining is congruent to 1 modulo 4, so he can never be forced to lose. Hence, he has a winning stratgecy, and Mitchell does not.
First, let us consider what happens if Alex picks 69. If Mitchell picks an odd number, then each person can only take odd numbers of candies. This means that on Alex's turn, he will always have an even amount left, so he will always be able to move, whereas Mitchell will always have an odd number left, and eventually be forced to take the last candy. However, if Mitchell picks an even number, then he can take an even amount of candies on his first turn and force Alex to always have an odd amount of candies, forcing him to lose. Therefore, Mitchell must pick an even number.
With this information, our answer simply becomes the number of multiples of 12 below 2010, which is .
\emph{Remark: }I lost.
%%Problem 15
\setcounter{enumi}{14}
Given that can be expressed in the form
, where
and
, find the unique integer
between 0 and 982 inclusive such that
divides
. [Note: 983 is a prime.] (Alex Zhu)
%%Solution 15
Let ,
,
,
, and let
. Note that the following:
The sets , for
, are equal (since
.)
, since
if and only if
.
The sets
is equal to the set
, since
or
if and only if
or
.
. This is because
is the set of all complex numbers of the form
, where
and
are integers between 1 and 491 inclusive, which is the same as the set of all complex numbers of the form
, where
and
are integers between 1 and 491 inclusive. The latter set is clearly comprised of exactly the conjugates of the elements of
.
It follows that
\begin{align*}
\sum_{z \in S} \frac{1}{z^4 - 1}
&= \frac{1}{4} \sum_{z \in S'} \frac{1}{z^4 - 1} \\
&= \frac{1}{8} \sum_{z \in S'} \left(\frac{1}{z^2 - 1} - \frac{1}{z^2 + 1} \right) \\
&= \frac{1}{8} \left(\sum_{z \in S'} \frac{1}{z^2 - 1} - \sum_{z \in S'} \frac{1}{z^2 + 1} \right) \\
&= \frac{1}{8} \left(\sum_{z \in S'} \frac{1}{z^2 - 1} - \sum_{z \in S'} \frac{1}{(iz)^2 + 1} \right) \\
&= \frac{1}{8} \left(\sum_{z \in S'} \frac{1}{z^2 - 1} - \sum_{z \in S'} \frac{1}{-z^2 + 1}\right) \\
&= \frac{1}{4} \left(\sum_{z \in S'} \frac{1}{z^2 - 1}\right) \\
&= \frac{1}{2} \left(\sum_{z \in S_1 \cup S_4} \frac{1}{z^2 - 1}\right) \\
&= \sum_{z \in S_1} \frac{\frac{1}{z^2 - 1} + \frac{1}{\bar{z}^2 - 1}}{2} \\
&= \sum_{z \in S_1} \frac{\frac{1}{z^2 - 1} + \overline{\left(\frac{1}{z^2 - 1}\right)}}{2} \\
&= \sum_{z \in S} \mbox{Re } \frac{1}{z^2 - 1} \\
&= \frac{1}{2}\mbox{Re} \left(\sum_{z \in S} \frac{1}{z-1} - \frac{1}{z+1} \right) \\
&= \frac{1}{2} \mbox{Re} \left(\sum_{b=1}^{491} \sum_{a=1}^{491} \frac{1}{(a-1) + bi} - \frac{1}{(a+1) + bi}\right) \\
&= \frac{1}{2} \mbox{Re} \left(\sum_{b=1}^{491} \left(\frac{1}{bi} + \frac{1}{1 + bi} - \frac{1}{491 + bi} - \frac{1}{492 + bi} \right)\right) \\
&= \frac{1}{2} \sum_{b=1}^{491} \left(\mbox{Re} \left(\frac{1}{bi} + \frac{1}{1 + bi} - \frac{1}{491 + bi} - \frac{1}{492 + bi} \right)\right) \\
&= \frac{1}{2} \left(\sum_{b=1}^{491} \left(\frac{1}{1 + b^2} - \frac{491}{491^2 + b^2} - \frac{492}{492^2 + b^2}\right) \right)
\end{align*}
We seek the integer such that
, that is, we seek the value of
modulo 983, that is, the value of
modulo 983. Since the product of a quadratic residue and a quadratic nonresidue is a quadratic nonresidue, and -1 is a quadratic residue mod 983 (as 983 is congruent to 3 modulo 4), it follows that
,
, and
are never divisible by
, so the denominators of the above sum is never divisible by
. (Alternatively, upon noticing that
, the problem statement implies that none of the denominators are divisible by
.) As the above sum that we have arrived at is real, and none of its denominators are divisible of
, we may manipulate the sum modulo 983.
We note that , so
, yielding
. Hence, our sum taken modulo
is just
mod
. Let this sum equal
. We have that
\begin{align*}
8T
&\equiv 4\sum_{b=1}^{491} \frac{1}{1 + b^2} \\
&\equiv 2\left(\sum_{b=1}^{491} \frac{1}{1 + b^2} + \sum_{b=1}^{491} \frac{1}{1 + (983 - b)^2}\right) \\
&\equiv 2\left(\sum_{b=1}^{491} \frac{1}{1 + b^2} + \sum_{b=492}^{982} \frac{1}{1+b^2}\right) \\
&\equiv 2 \sum_{b=1}^{982} \frac{1}{1+b^2} \pmod{983}.
\end{align*}
Since
is a permutation of
modulo
, we have that
\begin{align*}
2 \sum_{b=1}^{982} \frac{1}{1+b^2}
&\equiv \sum_{b=1}^{982} + \sum_{b=1}^{982} \frac{1}{1 + \left(\frac{1}{b}\right)^2} \\
&\equiv \sum_{b=1}^{982} \frac{1}{b^2+1} + \sum_{b=1}^{982} \frac{b^2}{b^2 + 1} \\
&\equiv \sum_{b=1}^{982} 1 \\
&= 982 \pmod{983}.
\end{align*}$Hence,
\begin{align*}
T
&\equiv \frac{982}{8} \\
&\equiv \frac{491}{4} \\
&\equiv \frac{491 + 983}{4} \\
&\equiv \frac{737}{2} \\
&\equiv \frac{737 + 983}{2} \\
&\equiv 860 \pmod{983}
\end{align*}
giving us an answer of$ (Error compiling LaTeX. Unknown error_msg)\boxed{860}$.