Difference between revisions of "Mock AIME 2 2010 Answer Key"
m (Formated Subtitles) |
Alexxie2013 (talk | contribs) (→Problem 4) |
||
(53 intermediate revisions by 37 users not shown) | |||
Line 19: | Line 19: | ||
{{AIME box|year = Mock|n = 2 2010|before=[[Mock AIME 1 2010]]|after=[[Mock AIME 1 2011]]}} | {{AIME box|year = Mock|n = 2 2010|before=[[Mock AIME 1 2010]]|after=[[Mock AIME 1 2011]]}} | ||
− | == | + | ==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. | + | 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. |
− | + | ==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 <math>2010-15=1995</math>. This process can be repeated every for every 15 lemmings, so since it takes 6 steps to clear 15 lemmings, it will take us <math>2010\cdot\frac{6}{15}=\boxed{804}</math> to remove all the lemmings. | 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 <math>2010-15=1995</math>. This process can be repeated every for every 15 lemmings, so since it takes 6 steps to clear 15 lemmings, it will take us <math>2010\cdot\frac{6}{15}=\boxed{804}</math> to remove all the lemmings. | ||
− | + | ==Problem 2== | |
− | |||
− | |||
− | |||
+ | Let <math>a_1, a_2, \ldots, a_{10}</math> be nonnegative integers such that <math>a_1 + a_2 + \ldots + a_{10} = 2010</math>, and define <math>f</math> so that <math>f((a_1, a_2, \ldots, a_{10})) = (b_1, b_2, \ldots, b_{10})</math>, with <math>0 \le b_i \le 2, 3|a_i-b_i</math> for <math>1 \le i \le 10</math>. Given that <math>f</math> can take on <math>K</math> distinct values, find the remainder when <math>K</math> is divided by 1000. | ||
− | + | ==Solution 2== | |
− | For any <math>a_1, a_2, \ldots, a_{10}</math>, since <math>b_i\equiv a_i \pmod{3}</math> for <math>1\le i\le 10</math>, therefore, <math>b_1+b_2+\ldots+b_{10}\equiv a_1+a_2+\ldots+a_{10} = 2010 \equiv 0 \pmod{3}</math>. Also, note that for any <math>(b_1, b_2, \ldots, b_{10})</math> that satisfies <math>b_1+b_2+\ldots+b_{10}\equiv 0 \pmod{3}</math>, there exists a corresponding <math>(a_1, a_2, \ldots, a_{10})</math> such that <math>a_1+a_2+\ldots+a_{10}=2010</math> (let <math>a_i = b_i</math> for <math>1 \leq i \leq 9</math>, and <math>a_{10} = 2010 - (b_1 + b_2 + \ldots + b_9)</math>.) Therefore, we are just trying to count the number of <math>(b_1, b_2, \ldots, b_{10})</math> that satisfy <math>b_1+b_2+\ldots+b_{10}\equiv 0 \pmod{3}</math>. To do this, we note that for any of the <math>3^9</math> possible ways to pick <math>b_1, b_2, \dots, b_9</math>, there is exactly 1 possible value of <math>b_{10}</math> that works. Therefore, the total number of possibilities is <math>3^9= | + | For any <math>a_1, a_2, \ldots, a_{10}</math>, since <math>b_i\equiv a_i \pmod{3}</math> for <math>1\le i\le 10</math>, therefore, <math>b_1+b_2+\ldots+b_{10}\equiv a_1+a_2+\ldots+a_{10} = 2010 \equiv 0 \pmod{3}</math>. Also, note that for any <math>(b_1, b_2, \ldots, b_{10})</math> that satisfies <math>b_1+b_2+\ldots+b_{10}\equiv 0 \pmod{3}</math>, there exists a corresponding <math>(a_1, a_2, \ldots, a_{10})</math> such that <math>a_1+a_2+\ldots+a_{10}=2010</math> (let <math>a_i = b_i</math> for <math>1 \leq i \leq 9</math>, and <math>a_{10} = 2010 - (b_1 + b_2 + \ldots + b_9)</math>.) Therefore, we are just trying to count the number of <math>(b_1, b_2, \ldots, b_{10})</math> that satisfy <math>b_1+b_2+\ldots+b_{10}\equiv 0 \pmod{3}</math>. To do this, we note that for any of the <math>3^9</math> possible ways to pick <math>b_1, b_2, \dots, b_9</math>, there is exactly 1 possible value of <math>b_{10}</math> that works. Therefore, the total number of possibilities is <math>3^9=\boxed{19683}</math>. |
− | + | ==Problem 3== | |
− | |||
<math>\setcounter{enumi}{2}</math> | <math>\setcounter{enumi}{2}</math> | ||
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 <math>\frac{a}{b}</math>, where <math>a, b</math> are relatively prime positive integers. Find <math>a+b</math>. (Tim Wu) | 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 <math>\frac{a}{b}</math>, where <math>a, b</math> are relatively prime positive integers. Find <math>a+b</math>. (Tim Wu) | ||
− | + | ==Solution 3== | |
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, <math>4^5</math>. 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 <math>4^3\cdot10=640</math> 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 <math>5\cdot3\cdot4=60</math> total possibilities. Our probability is then <math>\frac{640-60}{4^5}=\frac{580}{4^5}=\frac{145}{256}</math>, so our answer is <math>\boxed{401}</math>. | 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, <math>4^5</math>. 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 <math>4^3\cdot10=640</math> 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 <math>5\cdot3\cdot4=60</math> total possibilities. Our probability is then <math>\frac{640-60}{4^5}=\frac{580}{4^5}=\frac{145}{256}</math>, so our answer is <math>\boxed{401}</math>. | ||
− | + | ==Problem 4== | |
− | |||
<math>\setcounter{enumi}{3}</math> | <math>\setcounter{enumi}{3}</math> | ||
− | 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 <math>\frac{a}{b}</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers, find <math>a+b</math>. (Alex Zhu) | + | Anderson is bored in physics class. His favorite numbers are <math>1</math>, <math>7</math>, and <math>33</math>. He randomly writes <math>0</math>., and then writes down a long string consisting of those numbers juxtaposed against one another (e.g., <math>0.1337173377133</math>...) 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 <math>\frac{a}{b}</math>, where <math>a</math> and <math>b</math> are relatively prime positive integers, find <math>a+b</math>. (Alex Zhu) |
− | + | ==Solution 4== | |
− | |||
Let <math>E</math> 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 <math>\frac{E}{10}</math> (the expected value of the original number only moved down a digit). Thus, in this case, his number will average <math>\frac{1}{10}+\frac{E}{10}</math>. Similarly, if he writes 7, his number will average <math>\frac{7}{10}+\frac{E}{10}</math>, and if he writes 33, his number will average <math>\frac{33}{100}+\frac{E}{100}</math>. Each of these cases happens with equal probability, so we have | Let <math>E</math> 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 <math>\frac{E}{10}</math> (the expected value of the original number only moved down a digit). Thus, in this case, his number will average <math>\frac{1}{10}+\frac{E}{10}</math>. Similarly, if he writes 7, his number will average <math>\frac{7}{10}+\frac{E}{10}</math>, and if he writes 33, his number will average <math>\frac{33}{100}+\frac{E}{100}</math>. Each of these cases happens with equal probability, so we have | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
− | E&= | + | E&=\dfrac{\frac{1}{10}+\frac{E}{10}+\frac{7}{10}+\frac{E}{10}+\frac{33}{100}+\frac{E}{100}}{3} \\ |
300E &= 10+10E+70+10E+33+E \\ | 300E &= 10+10E+70+10E+33+E \\ | ||
279E &= 113 \\ | 279E &= 113 \\ | ||
− | E &= | + | E &=\frac{113}{279}. |
− | \end{align*} | + | \end{align*}</cmath> |
Our answer is therefore <math>113+279=\boxed{392}</math>. | Our answer is therefore <math>113+279=\boxed{392}</math>. | ||
− | + | ==Problem 5== | |
<math>\setcounter{enumi}{4}</math> | <math>\setcounter{enumi}{4}</math> | ||
Line 76: | Line 69: | ||
− | + | ==Solution 5== | |
− | First, note that each of the <math>2^{5}</math> possible coefficients is multiplied by a different power of <math>x</math> | + | First, note that each of the <math>2^{5}</math> possible coefficients is multiplied by a different power of <math>x</math> because there are also <math>2^5</math> different powers of <math>x</math> 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 <math>x^n = x^{\sum 2^i b_i}</math>, where <math>b_i \in \{0,1\}</math>, is obtained from multiplying together all <math>i x^i</math> with <math>b_i = 1</math>.) Therefore, we are trying to find the product of all of the elements of subsets of the set <math>S=\{ 1,2,3,4,5\}</math> (where the product of the elements of the empty set is taken to be 1). If we pair each subset <math>P</math> with its complement, we will have 16 pairs of subsets, each of which multiplies together to <math>5!</math>, so the product of all of the subsets is <math>(5!)^{16}=120^{16}</math>. Since we want the last three nonzero digits, we simply wish to find <math>12^{16} \pmod{1000}</math>. To make this easier, we will find it modulo 8 and modulo 125 and use the Chinese remainder theorem to find the answer. |
<math>12^{16}\equiv 0 \pmod{8}</math>, and <math>12^{16}\equiv 144^8\equiv 19^8\equiv 361^4\equiv (-14)^4\equiv 196^2\equiv 71^2\equiv 41 \pmod{125}</math>. | <math>12^{16}\equiv 0 \pmod{8}</math>, and <math>12^{16}\equiv 144^8\equiv 19^8\equiv 361^4\equiv (-14)^4\equiv 196^2\equiv 71^2\equiv 41 \pmod{125}</math>. | ||
Line 85: | Line 78: | ||
− | + | ==Problem 6== | |
− | <math> | + | If <math>z</math> is twice <math>x</math> , then what is <math>5x+10+z-10+2z</math> in terms of <math>x</math> ? |
− | |||
− | |||
− | + | ==Solution 6== | |
− | |||
Let <math>a_i</math> denote the number of subsets <math>S \subseteq S_{10}</math> such that <math>f(S)=i</math>. Our answer will be the sum <math>\sum_{i=0}^{10} ia_i</math>. | Let <math>a_i</math> denote the number of subsets <math>S \subseteq S_{10}</math> such that <math>f(S)=i</math>. Our answer will be the sum <math>\sum_{i=0}^{10} ia_i</math>. | ||
Line 98: | Line 88: | ||
For any positive integer <math>d \leq 10</math>, we note that the non-empty sets satisfying the property that <math>f(S)</math> is a multiple of <math>d</math> are exactly the non-empty sets whose elements are multiples of <math>d</math>. Hence, the number of such sets is <math>2^k - 1</math>, where <math>k=\lfloor \frac{10}{d} \rfloor</math> (as there are <math>k</math> multiples of <math>d</math> between 1 and 10 inclusive.) On the other hand, the number of such sets is <math>a_d + a_{2d} + \ldots + a_{kd}</math>, that is, the sum of the number of sets <math>S</math> such that <math>f(S)</math> is <math>d</math>, <math>f(S)</math> is <math>2d</math>, <math>f(S)</math> is <math>3d</math>, etc., so we have that <math>a_d + a_{2d} + \ldots + a_{kd} = 2^k - 1</math>. By setting <math>d = 1, 2, 3, \ldots, 10</math>, we see that | For any positive integer <math>d \leq 10</math>, we note that the non-empty sets satisfying the property that <math>f(S)</math> is a multiple of <math>d</math> are exactly the non-empty sets whose elements are multiples of <math>d</math>. Hence, the number of such sets is <math>2^k - 1</math>, where <math>k=\lfloor \frac{10}{d} \rfloor</math> (as there are <math>k</math> multiples of <math>d</math> between 1 and 10 inclusive.) On the other hand, the number of such sets is <math>a_d + a_{2d} + \ldots + a_{kd}</math>, that is, the sum of the number of sets <math>S</math> such that <math>f(S)</math> is <math>d</math>, <math>f(S)</math> is <math>2d</math>, <math>f(S)</math> is <math>3d</math>, etc., so we have that <math>a_d + a_{2d} + \ldots + a_{kd} = 2^k - 1</math>. By setting <math>d = 1, 2, 3, \ldots, 10</math>, we see that | ||
− | \begin{align*} | + | <cmath>\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_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_2 + a_4 + a_6 + a_8 + a_{10} &= 2^5 - 1 = 31 \\ | ||
Line 109: | Line 99: | ||
a_9 &= 2^1 - 1 = 1 \\ | a_9 &= 2^1 - 1 = 1 \\ | ||
a_{10} &= 2^1 - 1 = 1 | a_{10} &= 2^1 - 1 = 1 | ||
− | \end{align*} | + | \end{align*}</cmath> |
We can easily solve this system of equations to find <math>a_1 = 983</math>, <math>a_2 = 26</math>, <math>a_3 = 5</math>, <math>a_4 = 2</math>, <math>a_5 = 2</math>, and <math>a_6 = a_7 = a_8 = a_9 = a_{10} = 1</math>. Our answer is therefore <math>1 \cdot 983 + 2 \cdot 26 + 3 \cdot 5 + 4 \cdot 8 + 5 \cdot 2 + 6\cdot 1 + 7 \cdot 1 + 8 \cdot 1 + 9 \cdot 1 + 10 \cdot 1 = 1\boxed{108}</math>. | We can easily solve this system of equations to find <math>a_1 = 983</math>, <math>a_2 = 26</math>, <math>a_3 = 5</math>, <math>a_4 = 2</math>, <math>a_5 = 2</math>, and <math>a_6 = a_7 = a_8 = a_9 = a_{10} = 1</math>. Our answer is therefore <math>1 \cdot 983 + 2 \cdot 26 + 3 \cdot 5 + 4 \cdot 8 + 5 \cdot 2 + 6\cdot 1 + 7 \cdot 1 + 8 \cdot 1 + 9 \cdot 1 + 10 \cdot 1 = 1\boxed{108}</math>. | ||
− | + | ==Problem 7== | |
− | \setcounter{enumi}{6} | + | <math>\setcounter{enumi}{6}</math> |
Find the number of functions <math>f</math> from <math>\{1,2,3,4,5\}</math> to itself such that <math>f(f(f(x))) = f(f(x))</math> for all <math>x \in \{1,2,3,4,5\}</math>. (Alex Zhu) | Find the number of functions <math>f</math> from <math>\{1,2,3,4,5\}</math> to itself such that <math>f(f(f(x))) = f(f(x))</math> for all <math>x \in \{1,2,3,4,5\}</math>. (Alex Zhu) | ||
− | + | ==Solution 7== | |
− | |||
For a function <math>f</math>, let <math>A= \{i : f(i)=i\}</math> be the set of values that are fixed, let <math>B = \{i : f(i) \in A \text{ and } i \not\in A\}</math> be the set of values that evaluate to an element in <math>A</math> but are not elements of <math>A</math> themselves, and let <math>C=\{1,2,3,4,5\} - (A\cup B)</math> be the set of the remaining values. Notice that all possible values of <math>f(f(x))</math> are in <math>A</math>, so <math>A</math> must be nonempty. We will now use casework on the size of <math>A</math>. | For a function <math>f</math>, let <math>A= \{i : f(i)=i\}</math> be the set of values that are fixed, let <math>B = \{i : f(i) \in A \text{ and } i \not\in A\}</math> be the set of values that evaluate to an element in <math>A</math> but are not elements of <math>A</math> themselves, and let <math>C=\{1,2,3,4,5\} - (A\cup B)</math> be the set of the remaining values. Notice that all possible values of <math>f(f(x))</math> are in <math>A</math>, so <math>A</math> must be nonempty. We will now use casework on the size of <math>A</math>. | ||
Line 142: | Line 131: | ||
Adding everything up, we see that our final answer is <math>205+380+150+20+1=\boxed{756}</math>. | Adding everything up, we see that our final answer is <math>205+380+150+20+1=\boxed{756}</math>. | ||
+ | ==Problem 8== | ||
− | + | <math>\setcounter{enumi}{7}</math> | |
− | |||
− | \setcounter{enumi}{7} | ||
In triangle <math>ABC</math>, <math>BA = 15</math>, <math>AC = 20</math>, and <math>BC = 25</math>. In addition, there is a point <math>D</math> lying on segment <math>BC</math> such that <math>BD = 16</math>. Given that the length of the radius of the circle through <math>B</math> and <math>D</math> that is tangent to side <math>AC</math> can be expressed in the form <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime integers, find <math>p + q</math>. (Alex Zhu) | In triangle <math>ABC</math>, <math>BA = 15</math>, <math>AC = 20</math>, and <math>BC = 25</math>. In addition, there is a point <math>D</math> lying on segment <math>BC</math> such that <math>BD = 16</math>. Given that the length of the radius of the circle through <math>B</math> and <math>D</math> that is tangent to side <math>AC</math> can be expressed in the form <math>\frac{p}{q}</math>, where <math>p</math> and <math>q</math> are relatively prime integers, find <math>p + q</math>. (Alex Zhu) | ||
+ | ==Solutions 8== | ||
− | ===Solution | + | ===Solution 1=== |
− | |||
Let <math>E</math> be the point of tangency of the circle with <math>AC</math>. By power of a point, <math>CD \cdot CB = CE^2</math>, that is, <math>9 \cdot 25 = C^2</math>, giving <math>CE = 15</math> and <math>AE = 20 - 15 = 5</math>. Since <math>15^2 + 20^2 = 25^2</math>, <math>m \angle A = 90^{\circ}</math>, so <math>BE = 5 \sqrt{10}</math> and <math>\sin m \angle AEB = \frac{15}{5 \sqrt{10}}</math>. Since the circle is tangent to <math>AC</math>, we have that <math>\angle AEB \cong \angle EDB</math>. By the extended law of sines, the circumdiameter of <math>\triangle BED</math> (that is, the radius of our circle) is <math>\frac{BE}{\sin m \angle EDB} = \frac{BE}{\sin m \angle AEB} = \frac{50}{3}</math>. Therefore, the radius is <math>\frac{25}{3}</math>, giving an answer of <math>25 + 3 = \boxed{028}</math>. | Let <math>E</math> be the point of tangency of the circle with <math>AC</math>. By power of a point, <math>CD \cdot CB = CE^2</math>, that is, <math>9 \cdot 25 = C^2</math>, giving <math>CE = 15</math> and <math>AE = 20 - 15 = 5</math>. Since <math>15^2 + 20^2 = 25^2</math>, <math>m \angle A = 90^{\circ}</math>, so <math>BE = 5 \sqrt{10}</math> and <math>\sin m \angle AEB = \frac{15}{5 \sqrt{10}}</math>. Since the circle is tangent to <math>AC</math>, we have that <math>\angle AEB \cong \angle EDB</math>. By the extended law of sines, the circumdiameter of <math>\triangle BED</math> (that is, the radius of our circle) is <math>\frac{BE}{\sin m \angle EDB} = \frac{BE}{\sin m \angle AEB} = \frac{50}{3}</math>. Therefore, the radius is <math>\frac{25}{3}</math>, giving an answer of <math>25 + 3 = \boxed{028}</math>. | ||
− | |||
− | + | ===Solution 2=== | |
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 <math>CD \cdot CB=CE^2</math>, so <math>9\cdot 25=CE^2</math>, giving <math>CE=15</math> and <math>EA=20-15=5</math>. Now, let <math>r</math> be the radius of the circle. We have <math>AF=EO=r</math>, so <math>FB=AB-AF=15-r</math>. By the Pythagorean theorem on triangle FOB, we have <math>FB^2+FO^2=BO^2\iff 225-30r+r^2+FO^2=r^2 \iff FO=\sqrt{30r-225}</math>. Finally, we have <math>5=EA=FO=\sqrt{30r-225}</math>, so <math>25=30r-225</math>. Hence, <math>r=\frac{25}{3}</math>, giving us an answer of <math>25+3=\boxed{028}</math>. | 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 <math>CD \cdot CB=CE^2</math>, so <math>9\cdot 25=CE^2</math>, giving <math>CE=15</math> and <math>EA=20-15=5</math>. Now, let <math>r</math> be the radius of the circle. We have <math>AF=EO=r</math>, so <math>FB=AB-AF=15-r</math>. By the Pythagorean theorem on triangle FOB, we have <math>FB^2+FO^2=BO^2\iff 225-30r+r^2+FO^2=r^2 \iff FO=\sqrt{30r-225}</math>. Finally, we have <math>5=EA=FO=\sqrt{30r-225}</math>, so <math>25=30r-225</math>. Hence, <math>r=\frac{25}{3}</math>, giving us an answer of <math>25+3=\boxed{028}</math>. | ||
− | |||
− | |||
− | |||
− | + | ==Problem 9== | |
− | |||
+ | <math>\setcounter{enumi}{8}</math> | ||
+ | Given that <math>x,y,z</math> are reals such that <math>16 \sin^4(x+y) + 49 \cos^4(x+y) = \sin^2(2x + 2y)(8\sin^2(x+z) + 6 \cos^2(y+z))</math>, the largest possible value of <math>3\cos^2(x+y+z)</math> can be expressed in the form <math>\frac{a+b\sqrt{c}}{d}</math>, where <math>a</math> and <math>b</math> are integers, <math>c</math> is a positive integer not divisible by the square of any prime, and <math>d</math> is a positive integer such that <math>\gcd(a,b,d)=1</math>. Find <math>a+b+c+d</math>. | ||
− | + | ==Solution 9== | |
− | \begin{align*} | + | <cmath>\begin{align*} |
16\sin^4(x+y) + 49\cos^4(x+y) | 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) \\ | &= \sin^2(2x + 2y)\left(8\sin^2(x+z) + 6\cos^2(y+z)\right) \\ | ||
&\leq 14 \sin^2(2x + 2y) \\ | &\leq 14 \sin^2(2x + 2y) \\ | ||
&= 56(\sin(x+y) \cos(x+y)) | &= 56(\sin(x+y) \cos(x+y)) | ||
− | \end{align*} | + | \end{align*}</cmath> |
− | Hence, <math>(4 \sin^2(x+y) - 7 \cos^2(x+y)) \leq 0</math>, yielding <math>\tan^2(x+y) = \frac{7}{4}</math>, or <math>x + y = \pm \arctan{\frac{\sqrt{7}}{2}} + a\pi</math>, for some integer <math>a</math>. Furthermore, we must have <math>\sin^4(x+z) = \cos^4(y+z) = 1</math>, so <math>x + z = \frac{\pi}{2} + b\pi</math> and <math>y + z = c \pi</math> for some integers <math>b</math> and <math>c</math>. Hence, <math>2x + 2y + 2z = \pm \arctan\frac{\sqrt{7}}{2} + \frac{\pi}{2} + \pi(a+b+c)</math>, so <math>|\cos(2x + 2y + 2z)| = |\sin \arctan\frac{\sqrt{7}}{2}| = \frac{\sqrt{77}}{11}</math>. Hence, <math>2\cos(x+y+z)^2 - 1 \leq |2\cos(x+y+z)^2 - 1| = |\cos(2x + 2y + 2z)| = \frac{\sqrt{77}}{11}</math>, giving us <math>3 \cos(x+y+z)^2 \leq \frac{33 + 3 \sqrt{77}}{22}</math>. This is attained when <math>\cos(2x + 2y + 2z) > 0</math>, which indeed occurs if we pick <math>x + y = \arctan \frac{\sqrt{7}}{2}</math>, <math>x + z = \frac{\pi}{2} + \pi</math>, and <math>z + y = 0</math>, so our answer is <math>33 + 3 + 77 + 22 = \boxed{135}</math>. | + | Hence, <math>(4 \sin^2(x+y) - 7 \cos^2(x+y)) \leq 0</math>, yielding <math>\tan^2(x+y) = \frac{7}{4}</math>, or <math>x + y = \pm \arctan{\frac{\sqrt{7}}{2}} + a\pi</math>, for some integer <math>a</math>. Furthermore, we must have <math>\sin^4(x+z) = \cos^4(y+z) = 1</math>, so <math>x + z = \frac{\pi}{2} + b\pi</math> and <math>y + z = c \pi</math> for some integers <math>b</math> and <math>c</math>. Hence, <math>2x + 2y + 2z = \pm \arctan\frac{\sqrt{7}}{2} + \frac{\pi}{2} + \pi(a+b+c)</math>, so <math>|\cos(2x + 2y + 2z)| = |\sin \arctan\frac{\sqrt{7}}{2}| = \frac{\sqrt{77}}{11}</math>. Hence, <math>2\cos(x+y+z)^2 - 1 \leq |2\cos(x+y+z)^2 - 1| = |\cos(2x + 2y + 2z)| = \frac{\sqrt{77}}{11}</math>, giving us <math>3 \cos(x+y+z)^2 \leq \frac{33 + 3 \sqrt{77}}{22}</math>. This is attained when <math>\cos(2x + 2y + 2z) > 0</math>, which indeed occurs if we pick <math>x + y = \arctan \frac{\sqrt{7}}{2}</math>, <math>x + z = \frac{\pi}{2} + \pi</math>, and <math>z + y = 0</math>, so our answer is <math>33 + 3 + 77 + 22 = \boxed{135}</math>. |
− | |||
− | + | ==Problem 10== | |
− | \setcounter{enumi}{9} | + | <math>\setcounter{enumi}{9}</math> |
How many positive integers <math>n \le 2010 </math> satisfy <math>\phi(n) | n</math>, where <math>\phi(n)</math> is the number of positive integers less than or equal to <math>n</math> relatively prime to <math>n</math>? (Alex Zhu) | How many positive integers <math>n \le 2010 </math> satisfy <math>\phi(n) | n</math>, where <math>\phi(n)</math> is the number of positive integers less than or equal to <math>n</math> relatively prime to <math>n</math>? (Alex Zhu) | ||
− | + | ==Solution 10== | |
− | |||
If <math>n = 2^k</math>, then <math>\varphi(2^k) = 2^{k-1} | 2^k = n</math>. Now, suppose <math>n</math> is not a power of 2. Let <math>n = 2^a b</math>, where <math>b</math> is odd. <math>\phi(n) = 2^{a-1} \phi(b)</math>. If <math>b = pqm</math>, where <math>p</math> and <math>q</math> are distinct odd prime numbers and <math>m</math> is some integer, then <math>\phi(b) = \phi(p)\phi(q) \phi(m) = (p-1)(q-1) \phi(m)</math>. Since <math>p</math> and <math>q</math> are odd, <math>p-1</math> and <math>q-1</math> are even, so <math>4 | \phi(b)</math>. Hence, <math>2^{a+1} | \phi(n)</math>, so <math>\phi(n) \not | n</math>. | If <math>n = 2^k</math>, then <math>\varphi(2^k) = 2^{k-1} | 2^k = n</math>. Now, suppose <math>n</math> is not a power of 2. Let <math>n = 2^a b</math>, where <math>b</math> is odd. <math>\phi(n) = 2^{a-1} \phi(b)</math>. If <math>b = pqm</math>, where <math>p</math> and <math>q</math> are distinct odd prime numbers and <math>m</math> is some integer, then <math>\phi(b) = \phi(p)\phi(q) \phi(m) = (p-1)(q-1) \phi(m)</math>. Since <math>p</math> and <math>q</math> are odd, <math>p-1</math> and <math>q-1</math> are even, so <math>4 | \phi(b)</math>. Hence, <math>2^{a+1} | \phi(n)</math>, so <math>\phi(n) \not | n</math>. | ||
Line 192: | Line 175: | ||
− | + | ==Problem 11== | |
− | \setcounter{enumi}{10} | + | <math>\setcounter{enumi}{10}</math> |
Let <math>f:\mathbb{N}\to\mathbb{N}</math> be a function such that <cmath>f(n) =\sum_{abc = n | a,b,c \in \mathbb{N}} ab + bc + ca.</cmath> For example, <math>f(5) = (1 \cdot 1 + 1 \cdot 5 + 5 \cdot 1) + (1 \cdot 5 + 5 \cdot 1 + 1 \cdot 1) + (5 \cdot 1 + 1 \cdot 1 + 1 \cdot 5) = 33</math>, where we are summing over the triples <math>(a,b,c) = (1,1,5), (1,5,1)</math>, and <math>(5,1,1)</math>. Find the last three digits of <math>f(30^{3})</math>. (Mitchell Lee) | Let <math>f:\mathbb{N}\to\mathbb{N}</math> be a function such that <cmath>f(n) =\sum_{abc = n | a,b,c \in \mathbb{N}} ab + bc + ca.</cmath> For example, <math>f(5) = (1 \cdot 1 + 1 \cdot 5 + 5 \cdot 1) + (1 \cdot 5 + 5 \cdot 1 + 1 \cdot 1) + (5 \cdot 1 + 1 \cdot 1 + 1 \cdot 5) = 33</math>, where we are summing over the triples <math>(a,b,c) = (1,1,5), (1,5,1)</math>, and <math>(5,1,1)</math>. Find the last three digits of <math>f(30^{3})</math>. (Mitchell Lee) | ||
− | + | ==Solution 11== | |
− | |||
<math>\sum_{abc = n | a,b,c \in \mathbb{N}} ab + bc + ca = abc \sum_{abc = n | a,b,c \in \mathbb{N}} \frac{1}{a} + \frac{1}{b} + \frac{1}{c}</math>. For any <math>a</math> that divides <math>n</math>, the number of sums that <math>\frac{1}{a}</math> will be in is exactly three the number of ordered pairs <math>(b,c)</math> we can find such that <math>abc = n</math>, which in turn is just <math>\tau(\frac{n}{a})</math>, where <math>\tau(n)</math> is the number of divisors of <math>n</math> (<math>b</math> can be any divisor of <math>\frac{n}{a}</math>, and <math>c = \frac{n}{ab}</math>.) (The factor of three arises from the fact that <math>\frac{1}{b} + \frac{1}{a} + \frac{1}{c}</math> and <math>\frac{1}{b} + \frac{1}{c} + \frac{1}{a}</math> are to be taken account as well.) Hence, <math>abc \sum_{abc = n | a,b,c \in \mathbb{N}} \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = \frac{1}{n} \sum_{a | n} \frac{\tau(\frac{n}{a})}{a}</math>. Since the set <math>\{d : d > 0, d | n\}</math> is the same as the set <math>\{\frac{n}{d} : d > 0, d | n\}</math>, <math>n \sum_{a | n} \frac{\tau(\frac{n}{a})}{a} = n \sum_{a | n} \frac{\tau(a)}{\frac{n}{a}} = \sum_{a | n} a \tau(a)</math>, that is, <math>f(n) = 3 \sum_{a | n} a \tau(a)</math> for all <math>n</math>. | <math>\sum_{abc = n | a,b,c \in \mathbb{N}} ab + bc + ca = abc \sum_{abc = n | a,b,c \in \mathbb{N}} \frac{1}{a} + \frac{1}{b} + \frac{1}{c}</math>. For any <math>a</math> that divides <math>n</math>, the number of sums that <math>\frac{1}{a}</math> will be in is exactly three the number of ordered pairs <math>(b,c)</math> we can find such that <math>abc = n</math>, which in turn is just <math>\tau(\frac{n}{a})</math>, where <math>\tau(n)</math> is the number of divisors of <math>n</math> (<math>b</math> can be any divisor of <math>\frac{n}{a}</math>, and <math>c = \frac{n}{ab}</math>.) (The factor of three arises from the fact that <math>\frac{1}{b} + \frac{1}{a} + \frac{1}{c}</math> and <math>\frac{1}{b} + \frac{1}{c} + \frac{1}{a}</math> are to be taken account as well.) Hence, <math>abc \sum_{abc = n | a,b,c \in \mathbb{N}} \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = \frac{1}{n} \sum_{a | n} \frac{\tau(\frac{n}{a})}{a}</math>. Since the set <math>\{d : d > 0, d | n\}</math> is the same as the set <math>\{\frac{n}{d} : d > 0, d | n\}</math>, <math>n \sum_{a | n} \frac{\tau(\frac{n}{a})}{a} = n \sum_{a | n} \frac{\tau(a)}{\frac{n}{a}} = \sum_{a | n} a \tau(a)</math>, that is, <math>f(n) = 3 \sum_{a | n} a \tau(a)</math> for all <math>n</math>. | ||
Line 206: | Line 188: | ||
It follows that | It follows that | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
3 f(30^3) | 3 f(30^3) | ||
&= 3 \sum_{d | 30^3} d \tau(d) \\ | &= 3 \sum_{d | 30^3} d \tau(d) \\ | ||
Line 212: | Line 194: | ||
&= 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 \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 | &= 3 \cdot 49 \cdot 142 \cdot 586 | ||
− | \end{align*} | + | \end{align*}</cmath> |
The last three digits of this product can easily be computed to be <math>\boxed{164}</math>. | The last three digits of this product can easily be computed to be <math>\boxed{164}</math>. | ||
− | + | ==Problem 12== | |
− | \setcounter{enumi}{11} | + | <math>\setcounter{enumi}{11}</math> |
Let <cmath>K = \sum_{a_1=0}^8\sum_{a_2=0}^{a_1}...\sum_{a_{100}=0}^{a_{99}}\binom{8}{a_1}\binom{a_1}{a_2}...\binom{a_{99}}{a_{100}}.</cmath> Find the sum of digits of <math>K</math> in base-100. (Tim Wu) | Let <cmath>K = \sum_{a_1=0}^8\sum_{a_2=0}^{a_1}...\sum_{a_{100}=0}^{a_{99}}\binom{8}{a_1}\binom{a_1}{a_2}...\binom{a_{99}}{a_{100}}.</cmath> Find the sum of digits of <math>K</math> in base-100. (Tim Wu) | ||
+ | ==Solution 12== | ||
− | ===Solution | + | ===Solution 1=== |
− | |||
Let <cmath>f(n,k)=\sum_{a_1=0}^k \sum_{a_2=0}^{a_1}...\sum_{a_{n}=0}^{a_{n-1}}\binom{k}{a_1}\binom{a_1}{a_2}...\binom{a_{n-1}}{a_{n}}.</cmath> We seek to find <math>f(100,8)</math>. | Let <cmath>f(n,k)=\sum_{a_1=0}^k \sum_{a_2=0}^{a_1}...\sum_{a_{n}=0}^{a_{n-1}}\binom{k}{a_1}\binom{a_1}{a_2}...\binom{a_{n-1}}{a_{n}}.</cmath> We seek to find <math>f(100,8)</math>. | ||
We shall prove by induction that <math>f(n,k) = (n+1)^k</math>. Our base case, <math>n=1</math>, follows from the fact that <math>f(1,k)= \sum_{a_1=0}^k \binom{k}{a_1}=2^k</math> by the binomial theorem. Now, we note that <math>f(n,k)=\sum_{i=0}^{k} \binom{k}{i} f(n-1,i)</math>. Assuming that <math>f(m,k) = (m+1)^k</math> for all integers <math>m</math> with <math>1 \leq m \leq n-1</math>, we have that | We shall prove by induction that <math>f(n,k) = (n+1)^k</math>. Our base case, <math>n=1</math>, follows from the fact that <math>f(1,k)= \sum_{a_1=0}^k \binom{k}{a_1}=2^k</math> by the binomial theorem. Now, we note that <math>f(n,k)=\sum_{i=0}^{k} \binom{k}{i} f(n-1,i)</math>. Assuming that <math>f(m,k) = (m+1)^k</math> for all integers <math>m</math> with <math>1 \leq m \leq n-1</math>, we have that | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
f(n,k)&=\sum_{i=0}^{k} \binom{k}{i} f(n-1,i) \\ | f(n,k)&=\sum_{i=0}^{k} \binom{k}{i} f(n-1,i) \\ | ||
&= \sum_{i=0}^k \binom{k}{i} n^i \\ | &= \sum_{i=0}^k \binom{k}{i} n^i \\ | ||
&= (n+1)^k, | &= (n+1)^k, | ||
− | \end{align*} | + | \end{align*}</cmath> |
where the last step follows from the binomial theorem. | where the last step follows from the binomial theorem. | ||
Thus, we have <math>f(100,8)=101^8</math>. To express this in base-100, we notice that <math>101^8=(100+1)^8 = 100^8+\binom{8}{1}100^7+\binom{8}{2}100^6+\cdots+100^0</math>. Since <math>\binom{8}{4} = 70 < 100</math>, there are no ``carry-overs,'' so the sum of digits in base-100 will simply be <math>\binom 80+\binom{8}1+\binom 82 + \cdots +\binom{8}{8} = 2^8=\boxed{256}</math>. | Thus, we have <math>f(100,8)=101^8</math>. To express this in base-100, we notice that <math>101^8=(100+1)^8 = 100^8+\binom{8}{1}100^7+\binom{8}{2}100^6+\cdots+100^0</math>. Since <math>\binom{8}{4} = 70 < 100</math>, there are no ``carry-overs,'' so the sum of digits in base-100 will simply be <math>\binom 80+\binom{8}1+\binom 82 + \cdots +\binom{8}{8} = 2^8=\boxed{256}</math>. | ||
− | |||
− | + | ===Solution 2=== | |
+ | |||
Let <math>A_0 = \{1,2,3,4,5,6,7,8\}</math>. The number of 101-tuples of sets <math>(A_{100}, A_{99}, \ldots, A_1, A_0)</math>, such that <math>A_{100} \subseteq A_{99} \subseteq \ldots \subseteq A_1 \subseteq A_0</math> is equal to <math>K</math>; <math>\binom{8}{a_1}</math> tells the number of ways to pick <math>a_1</math> elements from <math>A_0</math>, <math>a_2</math> elements from <math>A_1</math>, etc. | Let <math>A_0 = \{1,2,3,4,5,6,7,8\}</math>. The number of 101-tuples of sets <math>(A_{100}, A_{99}, \ldots, A_1, A_0)</math>, such that <math>A_{100} \subseteq A_{99} \subseteq \ldots \subseteq A_1 \subseteq A_0</math> is equal to <math>K</math>; <math>\binom{8}{a_1}</math> tells the number of ways to pick <math>a_1</math> elements from <math>A_0</math>, <math>a_2</math> elements from <math>A_1</math>, etc. | ||
Line 243: | Line 225: | ||
Hence, <math>K = 101^8</math>. We proceed as we did before to find the sum of the digits of <math>K</math> when it is written in base 100 to arrive at our answer of <math>\boxed{256}</math>. | Hence, <math>K = 101^8</math>. We proceed as we did before to find the sum of the digits of <math>K</math> when it is written in base 100 to arrive at our answer of <math>\boxed{256}</math>. | ||
− | |||
− | + | ==Problem 13== | |
− | \setcounter{enumi}{12} | + | <math>\setcounter{enumi}{12}</math> |
<math>\triangle ABC</math> is inscribed in circle <math>\mathcal{C}</math>. The radius of <math>\mathcal{C}</math> is 285, and <math>BC = 567</math>. When the incircle of <math>\triangle ABC</math> is reflected across segment <math>BC</math>, it is tangent to <math>\mathcal{C}</math>. Given that the inradius of <math>\triangle ABC</math> can be expressed in the form <math>a\sqrt{b}</math>, where <math>a</math> and <math>b</math> are positive integers and <math>b</math> is not divisible by the square of any prime, find <math>a+b</math>. (Alex Zhu) | <math>\triangle ABC</math> is inscribed in circle <math>\mathcal{C}</math>. The radius of <math>\mathcal{C}</math> is 285, and <math>BC = 567</math>. When the incircle of <math>\triangle ABC</math> is reflected across segment <math>BC</math>, it is tangent to <math>\mathcal{C}</math>. Given that the inradius of <math>\triangle ABC</math> can be expressed in the form <math>a\sqrt{b}</math>, where <math>a</math> and <math>b</math> are positive integers and <math>b</math> is not divisible by the square of any prime, find <math>a+b</math>. (Alex Zhu) | ||
+ | ==Solution 13== | ||
+ | |||
+ | ===Solution 1=== | ||
− | |||
− | |||
We shall prove that in a circle <math>\mathcal{C}</math> with center <math>O</math>, radius <math>R</math>, a chord <math>BC</math> with midpoint <math>M</math> such that <math>OM = m</math>, and a point <math>A</math> on <math>\mathcal{C}</math> such that the incircle <math>\omega</math> of <math>\triangle ABC</math> with radius <math>r</math>, when reflected across <math>BC</math>, is tangent to <math>\mathcal{C}</math>, we have that <math>r = 4m</math>. | We shall prove that in a circle <math>\mathcal{C}</math> with center <math>O</math>, radius <math>R</math>, a chord <math>BC</math> with midpoint <math>M</math> such that <math>OM = m</math>, and a point <math>A</math> on <math>\mathcal{C}</math> such that the incircle <math>\omega</math> of <math>\triangle ABC</math> with radius <math>r</math>, when reflected across <math>BC</math>, is tangent to <math>\mathcal{C}</math>, we have that <math>r = 4m</math>. | ||
Line 258: | Line 240: | ||
It therefore suffices to find <math>m</math>. By the Pythagorean theorem, since <math>OMB</math> is right, we have that <math>m^2 + R^2 = \frac{BC^2}{4}</math>, so | It therefore suffices to find <math>m</math>. By the Pythagorean theorem, since <math>OMB</math> is right, we have that <math>m^2 + R^2 = \frac{BC^2}{4}</math>, so | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
m | m | ||
&= \sqrt{285^2 - \frac{567^2}{4}} \\ | &= \sqrt{285^2 - \frac{567^2}{4}} \\ | ||
Line 265: | Line 247: | ||
&= \frac{\sqrt{3 \cdot 1137}}{2} \\ | &= \frac{\sqrt{3 \cdot 1137}}{2} \\ | ||
&= \frac{3 \sqrt{379}}{2}. | &= \frac{3 \sqrt{379}}{2}. | ||
− | \end{align*} | + | \end{align*}</cmath> |
Hence, <math>r = 4m = 6 \sqrt{379}</math>, giving us an answer of <math>6 + 379 = \boxed{385}</math>. | Hence, <math>r = 4m = 6 \sqrt{379}</math>, giving us an answer of <math>6 + 379 = \boxed{385}</math>. | ||
− | |||
− | + | ===Solution 2=== pp | |
+ | |||
We shall prove that in another way that a circle <math>\mathcal{C}</math> with center <math>O</math>, radius <math>R</math>, a chord <math>BC</math> with midpoint <math>M</math> such that <math>OM = m</math>, and a point <math>A</math> on <math>\mathcal{C}</math> such that the incircle <math>\omega</math> of <math>\triangle ABC</math> with radius <math>r</math>, when reflected across <math>BC</math>, is tangent to <math>\mathcal{C}</math>, we have that <math>r = 4m</math>. | We shall prove that in another way that a circle <math>\mathcal{C}</math> with center <math>O</math>, radius <math>R</math>, a chord <math>BC</math> with midpoint <math>M</math> such that <math>OM = m</math>, and a point <math>A</math> on <math>\mathcal{C}</math> such that the incircle <math>\omega</math> of <math>\triangle ABC</math> with radius <math>r</math>, when reflected across <math>BC</math>, is tangent to <math>\mathcal{C}</math>, we have that <math>r = 4m</math>. | ||
Let <math>I</math> be the incenter of <math>\triangle ABC</math>, and let <math>I'</math> be the reflection of <math>I</math> across <math>BC</math> (hence, it is the center of the reflection of the incircle of <math>\triangle ABC</math> across <math>BC</math>.) Let <math>E</math> be the foot of the perpendicular from <math>O</math> to <math>II'</math>. We have that <math>IE = r - m</math> and <math>OI^2 = R^2 - 2Rr</math> by Euler's distance formula, so <math>OE^2 = R^2 - 2Rr - (r-m)^2 = R^2 - 2Rr + 2rm - r^2 - m^2</math>. In addition, <math>EI' = m + r</math> and <math>OI' = R - r</math>, since the reflection of <math>\omega</math> across <math>BC</math> is tangent to <math>\mathcal{C}</math>. Sine <math>\triangle OEI'</math> is right, we have that <math>OE^2 + EI'^2 = OI'^2</math>, that is, <math>R^2 - 2Rr + 2rm - r^2 - m^2 + m^2 + 2rm + r^2 = R^2 - 2Rr + r^2</math>, again yielding <math>r = 4m</math>. | Let <math>I</math> be the incenter of <math>\triangle ABC</math>, and let <math>I'</math> be the reflection of <math>I</math> across <math>BC</math> (hence, it is the center of the reflection of the incircle of <math>\triangle ABC</math> across <math>BC</math>.) Let <math>E</math> be the foot of the perpendicular from <math>O</math> to <math>II'</math>. We have that <math>IE = r - m</math> and <math>OI^2 = R^2 - 2Rr</math> by Euler's distance formula, so <math>OE^2 = R^2 - 2Rr - (r-m)^2 = R^2 - 2Rr + 2rm - r^2 - m^2</math>. In addition, <math>EI' = m + r</math> and <math>OI' = R - r</math>, since the reflection of <math>\omega</math> across <math>BC</math> is tangent to <math>\mathcal{C}</math>. Sine <math>\triangle OEI'</math> is right, we have that <math>OE^2 + EI'^2 = OI'^2</math>, that is, <math>R^2 - 2Rr + 2rm - r^2 - m^2 + m^2 + 2rm + r^2 = R^2 - 2Rr + r^2</math>, again yielding <math>r = 4m</math>. | ||
− | We simply compute the answer the way we did before to arrive at an answer of <math>\boxed{385}</math>. | + | We simply compute the answer the way we did before to arrive at an answer of <math>\boxed{385}</math>. |
− | |||
− | |||
− | |||
− | + | ==Problem 14== | |
− | |||
+ | <math>\setcounter{enumi}{13}</math> | ||
+ | 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 Xiniiiiiig) | ||
− | + | ==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. | 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 | + | 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 | + | 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 divisors. 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 | + | We shall now show that if Mitchell does not pick a multiple of 4, then he cannot guarantee 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 strategy, 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. | 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. | ||
Line 300: | Line 280: | ||
− | + | ==Problem 15== | |
− | \setcounter{enumi}{14} | + | <math>\setcounter{enumi}{14}</math> |
Given that <math>\sum_{a = 1}^{491}\sum_{b = 1}^{491} \frac{1}{(a+bi)^4 - 1}</math> can be expressed in the form <math>\frac{p + qi}{r}</math>, where <math>\gcd(p, q, r) = 1</math> and <math>r > 0</math>, find the unique integer <math>k</math> between 0 and 982 inclusive such that <math>983</math> divides <math>(p + q) - kr</math>. [Note: 983 is a prime.] (Alex Zhu) | Given that <math>\sum_{a = 1}^{491}\sum_{b = 1}^{491} \frac{1}{(a+bi)^4 - 1}</math> can be expressed in the form <math>\frac{p + qi}{r}</math>, where <math>\gcd(p, q, r) = 1</math> and <math>r > 0</math>, find the unique integer <math>k</math> between 0 and 982 inclusive such that <math>983</math> divides <math>(p + q) - kr</math>. [Note: 983 is a prime.] (Alex Zhu) | ||
− | + | ==Solution 15== | |
− | |||
Let <math>S_1 = S</math>, <math>S_2 = \{iz : z \in S\}</math>, <math>S_3 = \{i^2 z : z \in S\}</math>, <math>S_4 = \{i^3 z : z \in S\}</math>, and let <math>S' = S_1 \cup S_2 \cup S_3 \cup S_4</math>. Note that the following: | Let <math>S_1 = S</math>, <math>S_2 = \{iz : z \in S\}</math>, <math>S_3 = \{i^2 z : z \in S\}</math>, <math>S_4 = \{i^3 z : z \in S\}</math>, and let <math>S' = S_1 \cup S_2 \cup S_3 \cup S_4</math>. Note that the following: | ||
Line 317: | Line 296: | ||
It follows that | It follows that | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
\sum_{z \in S} \frac{1}{z^4 - 1} | \sum_{z \in S} \frac{1}{z^4 - 1} | ||
&= \frac{1}{4} \sum_{z \in S'} \frac{1}{z^4 - 1} \\ | &= \frac{1}{4} \sum_{z \in S'} \frac{1}{z^4 - 1} \\ | ||
Line 334: | Line 313: | ||
&= \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} \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) | &= \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*} | + | \end{align*}</cmath> |
+ | |||
We seek the integer <math>k</math> such that <math>983 | p - qk</math>, that is, we seek the value of <math>\frac{p}{q}</math> modulo 983, that is, the value of <math>pq^{-1}</math> 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 <math>b^2 + 1</math>, <math>b^2 + 492^2</math>, and <math>b^2 + 491^2</math> are never divisible by <math>983</math>, so the denominators of the above sum is never divisible by <math>983</math>. (Alternatively, upon noticing that <math>r \neq 0</math>, the problem statement implies that none of the denominators are divisible by <math>983</math>.) As the above sum that we have arrived at is real, and none of its denominators are divisible of <math>983</math>, we may manipulate the sum modulo 983. | We seek the integer <math>k</math> such that <math>983 | p - qk</math>, that is, we seek the value of <math>\frac{p}{q}</math> modulo 983, that is, the value of <math>pq^{-1}</math> 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 <math>b^2 + 1</math>, <math>b^2 + 492^2</math>, and <math>b^2 + 491^2</math> are never divisible by <math>983</math>, so the denominators of the above sum is never divisible by <math>983</math>. (Alternatively, upon noticing that <math>r \neq 0</math>, the problem statement implies that none of the denominators are divisible by <math>983</math>.) As the above sum that we have arrived at is real, and none of its denominators are divisible of <math>983</math>, we may manipulate the sum modulo 983. | ||
We note that <math>491 \equiv -492 \pmod{983}</math>, so <math>491^2 \equiv 492^2 \pmod{983}</math>, yielding <math>\frac{491}{491^2 + b^2} + \frac{492}{492^2 + b^2} \equiv \frac{491 + 492}{491^2 + b^2} = \frac{983}{491^2 + b^2} \equiv 0 \pmod{983}</math>. Hence, our sum taken modulo <math>p</math> is just <math>\frac{1}{2} \sum_{a=1}^{491} \frac{1}{1 + b^2}</math> mod <math>p</math>. Let this sum equal <math>T</math>. We have that | We note that <math>491 \equiv -492 \pmod{983}</math>, so <math>491^2 \equiv 492^2 \pmod{983}</math>, yielding <math>\frac{491}{491^2 + b^2} + \frac{492}{492^2 + b^2} \equiv \frac{491 + 492}{491^2 + b^2} = \frac{983}{491^2 + b^2} \equiv 0 \pmod{983}</math>. Hence, our sum taken modulo <math>p</math> is just <math>\frac{1}{2} \sum_{a=1}^{491} \frac{1}{1 + b^2}</math> mod <math>p</math>. Let this sum equal <math>T</math>. We have that | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
8T | 8T | ||
&\equiv 4\sum_{b=1}^{491} \frac{1}{1 + b^2} \\ | &\equiv 4\sum_{b=1}^{491} \frac{1}{1 + b^2} \\ | ||
Line 344: | Line 324: | ||
&\equiv 2\left(\sum_{b=1}^{491} \frac{1}{1 + b^2} + \sum_{b=492}^{982} \frac{1}{1+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}. | &\equiv 2 \sum_{b=1}^{982} \frac{1}{1+b^2} \pmod{983}. | ||
− | \end{align*} | + | \end{align*}</cmath> |
Since <math>\{\frac{1}{1}, \frac{1}{2}, \ldots, \frac{1}{p-1}\}</math> is a permutation of <math>\{1, 2, \ldots, p-1\}</math> modulo <math>p</math>, we have that | Since <math>\{\frac{1}{1}, \frac{1}{2}, \ldots, \frac{1}{p-1}\}</math> is a permutation of <math>\{1, 2, \ldots, p-1\}</math> modulo <math>p</math>, we have that | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
2 \sum_{b=1}^{982} \frac{1}{1+b^2} | 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} + \sum_{b=1}^{982} \frac{1}{1 + \left(\frac{1}{b}\right)^2} \\ | ||
Line 352: | Line 332: | ||
&\equiv \sum_{b=1}^{982} 1 \\ | &\equiv \sum_{b=1}^{982} 1 \\ | ||
&= 982 \pmod{983}. | &= 982 \pmod{983}. | ||
− | \end{align*}< | + | \end{align*}</cmath> |
Hence, | Hence, | ||
− | \begin{align*} | + | <cmath>\begin{align*} |
T | T | ||
&\equiv \frac{982}{8} \\ | &\equiv \frac{982}{8} \\ | ||
Line 362: | Line 342: | ||
&\equiv \frac{737 + 983}{2} \\ | &\equiv \frac{737 + 983}{2} \\ | ||
&\equiv 860 \pmod{983} | &\equiv 860 \pmod{983} | ||
− | \end{align*} | + | \end{align*}</cmath> |
− | giving us an answer of < | + | giving us an answer of <math>\boxed{860}</math>. |
Latest revision as of 20:22, 13 July 2023
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 Problem 1
- 2 Solution 1
- 3 Problem 2
- 4 Solution 2
- 5 Problem 3
- 6 Solution 3
- 7 Problem 4
- 8 Solution 4
- 9 Problem 5
- 10 Solution 5
- 11 Problem 6
- 12 Solution 6
- 13 Problem 7
- 14 Solution 7
- 15 Problem 8
- 16 Solutions 8
- 17 Problem 9
- 18 Solution 9
- 19 Problem 10
- 20 Solution 10
- 21 Problem 11
- 22 Solution 11
- 23 Problem 12
- 24 Solution 12
- 25 Problem 13
- 26 Solution 13
- 27 Problem 14
- 28 Solution 14
- 29 Problem 15
- 30 Solution 15
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.
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.
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)
Solution 3
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
,
, and
. He randomly writes
., and then writes down a long string consisting of those numbers juxtaposed against one another (e.g.,
...) 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
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 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 multiplies 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
If is twice
, then what is
in terms of
?
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
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)
Solutions 8
Solution 1
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
.
Solution 2
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
.
Problem 9
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
.
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
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
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
The last three digits of this product can easily be computed to be
.
Problem 12
Let
Find the sum of digits of
in base-100. (Tim Wu)
Solution 12
Solution 1
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
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
.
Solution 2
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
.
Problem 13
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
Solution 1
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
Hence,
, giving us an answer of
.
===Solution 2=== pp
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 .
Problem 14
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 Xiniiiiiig)
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 divisors. 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 guarantee 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 strategy, 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
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
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
Since
is a permutation of
modulo
, we have that
Hence,
giving us an answer of
.