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 |
Contents
- 1 Unformatted Solutions
- 1.1 Problem 1
- 1.2 Solution 1
- 1.3 Problem 2
- 1.4 Solution 2
- 1.5 Problem 3
- 1.6 Problem 4
- 1.7 Solution 4
- 1.8 Problem 5
- 1.9 Solution 5
- 1.10 Problem 6
- 1.11 Solution 6
- 1.12 Problem 7
- 1.13 Solution 7
- 1.14 Problem 8
- 1.15 Solution 8
- 1.16 Problem 9
- 1.17 Solution 9
- 1.18 Problem 10
- 1.19 Solution 10
- 1.20 Problem 11
- 1.21 Solution 11
- 1.22 Problem 12
- 1.23 Solution 12
- 1.24 Problem 13
- 1.25 Solution 13
- 1.26 Problem 14
- 1.27 Solution 14
- 1.28 Problem 15
- 1.29 Solution 15
Unformatted Solutions
- Written by the problem authors. See the external links at Mock AIME 2 2010.
Problem 1
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
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
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
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$ (Error compiling LaTeX. ! Package amsmath Error: \begin{align*} allowed only in paragraph mode.)\{\frac{1}{1}, \frac{1}{2}, \ldots, \frac{1}{p-1}\}\{1, 2, \ldots, p-1\}p$, 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*}$ (Error compiling LaTeX. ! Package amsmath Error: \begin{align*} allowed only in paragraph mode.) 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*}$ (Error compiling LaTeX. ! Package amsmath Error: \begin{align*} allowed only in paragraph mode.) giving us an answer of .