Mock AIME 2 2010 Answer Key

Return to Mock AIME 2 2010

804
683
401
392
416
108
756
028
135
041
164
256
385
167
860

Mock AIME 2 2010 (Problems • Answer Key • Resources)
Preceded by Mock AIME 1 2010	Followed by Mock AIME 1 2011
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Unformatted Solutions

Written by the problem authors. See the external links at Mock AIME 2 2010.

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 $2010-15=1995$ . This process can be repeated every for every 15 lemmings, so since it takes 6 steps to clear 15 lemmings, it will take us $2010\cdot\frac{6}{15}=\boxed{804}$ to remove all the lemmings.

Problem 2

$\setcounter{enumi}{1}$ Let $a_1, a_2, \ldots, a_{10}$ be nonnegative integers such that $a_1 + a_2 + \ldots + a_{10} = 2010$ , and define $f$ so that $f((a_1, a_2, \ldots, a_{10})) = (b_1, b_2, \ldots, b_{10})$ , with $0 \le b_i \le 2, 3|a_i-b_i$ for $1 \le i \le 10$ . Given that $f$ can take on $K$ distinct values, find the remainder when $K$ is divided by 1000. (Alex Zhu)

Solution 2

For any $a_1, a_2, \ldots, a_{10}$ , since $b_i\equiv a_i \pmod{3}$ for $1\le i\le 10$ , therefore, $b_1+b_2+\ldots+b_{10}\equiv a_1+a_2+\ldots+a_{10} = 2010 \equiv 0 \pmod{3}$ . Also, note that for any $(b_1, b_2, \ldots, b_{10})$ that satisfies $b_1+b_2+\ldots+b_{10}\equiv 0 \pmod{3}$ , there exists a corresponding $(a_1, a_2, \ldots, a_{10})$ such that $a_1+a_2+\ldots+a_{10}=2010$ (let $a_i = b_i$ for $1 \leq i \leq 9$ , and $a_{10} = 2010 - (b_1 + b_2 + \ldots + b_9)$ .) Therefore, we are just trying to count the number of $(b_1, b_2, \ldots, b_{10})$ that satisfy $b_1+b_2+\ldots+b_{10}\equiv 0 \pmod{3}$ . To do this, we note that for any of the $3^9$ possible ways to pick $b_1, b_2, \dots, b_9$ , there is exactly 1 possible value of $b_{10}$ that works. Therefore, the total number of possibilities is $3^9=19\boxed{683}$ .

Problem 3

$\setcounter{enumi}{2}$ 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 $\frac{a}{b}$ , where $a, b$ are relatively prime positive integers. Find $a+b$ . (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, $4^5$ . 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 $4^3\cdot10=640$ 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 $5\cdot3\cdot4=60$ total possibilities. Our probability is then $\frac{640-60}{4^5}=\frac{580}{4^5}=\frac{145}{256}$ , so our answer is $\boxed{401}$ .

Problem 4

$\setcounter{enumi}{3}$ 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 $\frac{a}{b}$ , where $a$ and $b$ are relatively prime positive integers, find $a+b$ . (Alex Zhu)

Solution 4

Let $E$ 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 $\frac{E}{10}$ (the expected value of the original number only moved down a digit). Thus, in this case, his number will average $\frac{1}{10}+\frac{E}{10}$ . Similarly, if he writes 7, his number will average $\frac{7}{10}+\frac{E}{10}$ , and if he writes 33, his number will average $\frac{33}{100}+\frac{E}{100}$ . Each of these cases happens with equal probability, so we have \begin{align*} 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 \\ 279E &= 113 \\ E &= $\frac{113}{279}$ . \end{align*} Our answer is therefore $113+279=\boxed{392}$ .

Problem 5

$\setcounter{enumi}{4}$ Let $P(x)=(1+x)(1+2x^2)(1+3x^4)(1+4x^8)(1+5x^{16})$ . Find the three rightmost nonzero digits of the product of the coefficients of $P(x)$ . (Alex Zhu)

Solution 5

First, note that each of the $2^{5}$ possible coefficients is multiplied by a different power of $x$ , because there are also $2^5$ different powers of $x$ 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 $x^n = x^{\sum 2^i b_i}$ , where $b_i \in \{0,1\}$ , is obtained from multiplying together all $i x^i$ with $b_i = 1$ .) Therefore, we are trying to find the product of the product of all of the elements of subsets of the set $S=\{ 1,2,3,4,5\}$ (where the product of the elements of the empty set is taken to be 1). If we pair each subset $P$ with its complement, we will have 16 pairs of subsets, each of which multiply together to $5!$ , so the product of all of the subsets is $(5!)^{16}=120^{16}$ . Since we want the last three nonzero digits, we simply wish to find $12^{16} \pmod{1000}$ . To make this easier, we will find it modulo 8 and modulo 125 and use the Chinese remainder theorem to find the answer.

$12^{16}\equiv 0 \pmod{8}$ , and $12^{16}\equiv 144^8\equiv 19^8\equiv 361^4\equiv (-14)^4\equiv 196^2\equiv 71^2\equiv 41 \pmod{125}$ .

We can now see that because $41\equiv 1\pmod{8}$ and $125\equiv 5\pmod{8}$ , the only number that is $0\pmod{8}$ and $41\pmod{125}$ is $41+125 \cdot 3=\boxed{416}$ .

Problem 6

$\setcounter{enumi}{5}$ \item Let $S_n$ denote the set $\{1,2,\ldots,n\}$ , and define $f(S)$ , where $S$ is a subset of the positive integers, to output the greatest common divisor of all elements in $S$ , unless $S$ is empty, in which case it will output 0. Find the last three digits of $\sum_{S\subseteq S_{10}} f(S)$ , where $S$ ranges over all subsets of $S_{10}$ . (George Xing)

Solution 6

Let $a_i$ denote the number of subsets $S \subseteq S_{10}$ such that $f(S)=i$ . Our answer will be the sum $\sum_{i=0}^{10} ia_i$ .

For any positive integer $d \leq 10$ , we note that the non-empty sets satisfying the property that $f(S)$ is a multiple of $d$ are exactly the non-empty sets whose elements are multiples of $d$ . Hence, the number of such sets is $2^k - 1$ , where $k=\lfloor \frac{10}{d} \rfloor$ (as there are $k$ multiples of $d$ between 1 and 10 inclusive.) On the other hand, the number of such sets is $a_d + a_{2d} + \ldots + a_{kd}$ , that is, the sum of the number of sets $S$ such that $f(S)$ is $d$ , $f(S)$ is $2d$ , $f(S)$ is $3d$ , etc., so we have that $a_d + a_{2d} + \ldots + a_{kd} = 2^k - 1$ . By setting $d = 1, 2, 3, \ldots, 10$ , 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 $a_1 = 983$ , $a_2 = 26$ , $a_3 = 5$ , $a_4 = 2$ , $a_5 = 2$ , and $a_6 = a_7 = a_8 = a_9 = a_{10} = 1$ . Our answer is therefore $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}$ .

Problem 7

\setcounter{enumi}{6} Find the number of functions $f$ from $\{1,2,3,4,5\}$ to itself such that $f(f(f(x))) = f(f(x))$ for all $x \in \{1,2,3,4,5\}$ . (Alex Zhu)

Solution 7

For a function $f$ , let $A= \{i : f(i)=i\}$ be the set of values that are fixed, let $B = \{i : f(i) \in A \text{ and } i \not\in A\}$ be the set of values that evaluate to an element in $A$ but are not elements of $A$ themselves, and let $C=\{1,2,3,4,5\} - (A\cup B)$ be the set of the remaining values. Notice that all possible values of $f(f(x))$ are in $A$ , so $A$ must be nonempty. We will now use casework on the size of $A$ .

\textbf{Case 1: } $|A|=1$ .\\ WLOG, let $f(1)=1$ , so we will multiply our result by 5 at the end. Now, let $|B|=x$ , so $|C|=4-x$ . We must have $f(f(x))=1$ for all $x$ , so each element $c$ in $C$ must satisfy $f(c)=b$ for some $b$ in $B$ , because $f(c)\neq 1$ and the only other numbers for which $f(x)=1$ are the elements of b. This also implies $|B|>0$ . Conversely, it is easy to check any function satisfying $f(c)=b$ works, so the total number of functions in this case is ${5\sum_{x=1}^4 \binom{4}{x} x^{4-x}}$ because there are $\binom{4}{x}$ ways to choose the elements in $B$ , and each of the $4-x$ elements in C can map to any of the $x$ elements in B. This sum evaluates to $5(4+6\cdot 4+4\cdot 3+1)=205$ , so there are 205 functions in this case.

\textbf{Case 2: } $|A|=2$ .\\ This is very similar to case 1, except for the fact that each element in $B$ can now correspond to one of two possible elements in $A$ , so this adds a factor of $2^x$ . The sum is ${\binom{5}{2}\sum_{x=1}^3\binom{3}{x} 2^x x^{3-x}}=10(3\cdot 2+3\cdot 4\cdot 2+8)=380$ , so there are 380 functions in this case.

\textbf{Case 3: } $|A|=3$ .\\ The sum is ${\binom{5}{3}\sum_{x=1}^2\binom{2}{x} 3^x x^{2-x}}=10(2\cdot 3+9)=150$ , so there are 150 functions in this case.

\textbf{Case 4: } $|A|=4$ .\\ There are clearly $5(4)=20$ functions in this case.

\textbf{Case 5: } $|A|=5$ .\\ There is a total of 1 function (the identity) in this case.

Adding everything up, we see that our final answer is $205+380+150+20+1=\boxed{756}$ .

Problem 8

\setcounter{enumi}{7} In triangle $ABC$ , $BA = 15$ , $AC = 20$ , and $BC = 25$ . In addition, there is a point $D$ lying on segment $BC$ such that $BD = 16$ . Given that the length of the radius of the circle through $B$ and $D$ that is tangent to side $AC$ can be expressed in the form $\frac{p}{q}$ , where $p$ and $q$ are relatively prime integers, find $p + q$ . (Alex Zhu)

Solution 8

\begin{sol1} Let $E$ be the point of tangency of the circle with $AC$ . By power of a point, $CD \cdot CB = CE^2$ , that is, $9 \cdot 25 = C^2$ , giving $CE = 15$ and $AE = 20 - 15 = 5$ . Since $15^2 + 20^2 = 25^2$ , $m \angle A = 90^{\circ}$ , so $BE = 5 \sqrt{10}$ and $\sin m \angle AEB = \frac{15}{5 \sqrt{10}}$ . Since the circle is tangent to $AC$ , we have that $\angle AEB \cong \angle EDB$ . By the extended law of sines, the circumdiameter of $\triangle BED$ (that is, the radius of our circle) is $\frac{BE}{\sin m \angle EDB} = \frac{BE}{\sin m \angle AEB} = \frac{50}{3}$ . Therefore, the radius is $\frac{25}{3}$ , giving an answer of $25 + 3 = \boxed{028}$ . \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 $CD \cdot CB=CE^2$ , so $9\cdot 25=CE^2$ , giving $CE=15$ and $EA=20-15=5$ . Now, let $r$ be the radius of the circle. We have $AF=EO=r$ , so $FB=AB-AF=15-r$ . By the Pythagorean theorem on triangle FOB, we have $FB^2+FO^2=BO^2\iff 225-30r+r^2+FO^2=r^2 \iff FO=\sqrt{30r-225}$ . Finally, we have $5=EA=FO=\sqrt{30r-225}$ , so $25=30r-225$ . Hence, $r=\frac{25}{3}$ , giving us an answer of $25+3=\boxed{028}$ . \end{sol2}

Problem 9

\setcounter{enumi}{8} Given that $x,y,z$ are reals such that $16 \sin^4(x+y) + 49 \cos^4(x+y) = \sin^2(2x + 2y)(8\sin^2(x+z) + 6 \cos^2(y+z))$ , the largest possible value of $3\cos^2(x+y+z)$ can be expressed in the form $\frac{a+b\sqrt{c}}{d}$ , where $a$ and $b$ are integers, $c$ is a positive integer not divisible by the square of any prime, and $d$ is a positive integer such that $\gcd(a,b,d)=1$ . Find $a+b+c+d$ . (Alex Zhu)

Solution 9

\begin{align*} 16\sin^4(x+y) + 49\cos^4(x+y) &= \sin^2(2x + 2y)\left(8\sin^2(x+z) + 6\cos^2(y+z)\right) \\ &\leq 14 \sin^2(2x + 2y) \\ &= 56(\sin(x+y) \cos(x+y)) \end{align*} Hence, $(4 \sin^2(x+y) - 7 \cos^2(x+y)) \leq 0$ , yielding $\tan^2(x+y) = \frac{7}{4}$ , or $x + y = \pm \arctan{\frac{\sqrt{7}}{2}} + a\pi$ , for some integer $a$ . Furthermore, we must have $\sin^4(x+z) = \cos^4(y+z) = 1$ , so $x + z = \frac{\pi}{2} + b\pi$ and $y + z = c \pi$ for some integers $b$ and $c$ . Hence, $2x + 2y + 2z = \pm \arctan\frac{\sqrt{7}}{2} + \frac{\pi}{2} + \pi(a+b+c)$ , so $|\cos(2x + 2y + 2z)| = |\sin \arctan\frac{\sqrt{7}}{2}| = \frac{\sqrt{77}}{11}$ . Hence, $2\cos(x+y+z)^2 - 1 \leq |2\cos(x+y+z)^2 - 1| = |\cos(2x + 2y + 2z)| = \frac{\sqrt{77}}{11}$ , giving us $3 \cos(x+y+z)^2 \leq \frac{33 + 3 \sqrt{77}}{22}$ . This is attained when $\cos(2x + 2y + 2z) > 0$ , which indeed occurs if we pick $x + y = \arctan \frac{\sqrt{7}}{2}$ , $x + z = \frac{\pi}{2} + \pi$ , and $z + y = 0$ , so our answer is $33 + 3 + 77 + 22 = \boxed{135}$ .

Problem 10

\setcounter{enumi}{9} How many positive integers $n \le 2010$ satisfy $\phi(n) | n$ , where $\phi(n)$ is the number of positive integers less than or equal to $n$ relatively prime to $n$ ? (Alex Zhu)

Solution 10

If $n = 2^k$ , then $\varphi(2^k) = 2^{k-1} | 2^k = n$ . Now, suppose $n$ is not a power of 2. Let $n = 2^a b$ , where $b$ is odd. $\phi(n) = 2^{a-1} \phi(b)$ . If $b = pqm$ , where $p$ and $q$ are distinct odd prime numbers and $m$ is some integer, then $\phi(b) = \phi(p)\phi(q) \phi(m) = (p-1)(q-1) \phi(m)$ . Since $p$ and $q$ are odd, $p-1$ and $q-1$ are even, so $4 | \phi(b)$ . Hence, $2^{a+1} | \phi(n)$ , so $\phi(n) \not | n$ .

It follows that $n$ has at most one other prime factor, so $n$ is of the form $2^k p^j$ . $\varphi(2^k p^j) = 2^{k-1} p^{j-1}(p-1) | 2^k p^j$ , so $p - 1 | 2p$ . Hence, $p - 1 | 2p - 2(p - 2) = 2$ , so $p = 2, 3$ . But $p \neq 2$ , so we must have that $p = 3$ .

We now note that $\varphi(3^b)$ , $b > 0$ , is even, and hence does not divide $3^k$ . But $\varphi(2^a 3^b) = 2^a 3^{b-1} | 2^a 3^b$ , so we wish to find the number of integers less than or equal to 2010 of the form $2^a 3^b$ such that $b \neq 0$ implies $a \neq 0$ .

When $a=0$ , $b=0$ giving one possible value of $b$ . For any larger $a < 10$ (as $2^{11} > 2010$ ), we have $0 \leq b \leq \lfloor \log_2 \frac{2010}{2^a} \rfloor$ , yieding $\lfloor \log_2 \frac{2010}{2^a} \rfloor + 1$ possible values of $b$ . Summing these values for $1 \leq a \leq 9$ gives us the answer of $1 + 7 + 6 + 6 + 5 + 4 + 4 + 3 + 2 + 2 = \boxed{041}$ .

Problem 11

\setcounter{enumi}{10} Let $f:\mathbb{N}\to\mathbb{N}$ be a function such that $f(n) =\sum_{abc = n | a,b,c \in \mathbb{N}} ab + bc + ca.$ For example, $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$ , where we are summing over the triples $(a,b,c) = (1,1,5), (1,5,1)$ , and $(5,1,1)$ . Find the last three digits of $f(30^{3})$ . (Mitchell Lee)

Solution 11

$\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}$ . For any $a$ that divides $n$ , the number of sums that $\frac{1}{a}$ will be in is exactly three the number of ordered pairs $(b,c)$ we can find such that $abc = n$ , which in turn is just $\tau(\frac{n}{a})$ , where $\tau(n)$ is the number of divisors of $n$ ( $b$ can be any divisor of $\frac{n}{a}$ , and $c = \frac{n}{ab}$ .) (The factor of three arises from the fact that $\frac{1}{b} + \frac{1}{a} + \frac{1}{c}$ and $\frac{1}{b} + \frac{1}{c} + \frac{1}{a}$ are to be taken account as well.) Hence, $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}$ . Since the set $\{d : d > 0, d | n\}$ is the same as the set $\{\frac{n}{d} : d > 0, d | n\}$ , $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)$ , that is, $f(n) = 3 \sum_{a | n} a \tau(a)$ for all $n$ .

Note that if $r$ and $s$ are relatively prime integers, then $\tau(rs) = \tau(r)\tau(s)$ and $rs = (r)(s)$ . Hence, $\sum_{a | rs} a \tau(a) = \left(\sum_{a | r} a \tau(a)\right) \left(\sum_{a | s} a \tau(a) \right),$ since every divisor of $rs$ can be expressed uniquely as a product of a divisor of $r$ and as a divisor of $s$ (upon expanding the product using the distributive property, it follows that we are summing over the set of all numbers of the form $r_1 s_1$ , where $r_1 | r$ and $s_1 | s$ , which is exactly the set divisors of $rs$ .)

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 $\boxed{164}$ .

Problem 12

\setcounter{enumi}{11} Let $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}}.$ Find the sum of digits of $K$ in base-100. (Tim Wu)

Solution 12

\begin{sol1} Let $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}}.$ We seek to find $f(100,8)$ .

We shall prove by induction that $f(n,k) = (n+1)^k$ . Our base case, $n=1$ , follows from the fact that $f(1,k)= \sum_{a_1=0}^k \binom{k}{a_1}=2^k$ by the binomial theorem. Now, we note that $f(n,k)=\sum_{i=0}^{k} \binom{k}{i} f(n-1,i)$ . Assuming that $f(m,k) = (m+1)^k$ for all integers $m$ with $1 \leq m \leq n-1$ , 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 $f(100,8)=101^8$ . To express this in base-100, we notice that $101^8=(100+1)^8 = 100^8+\binom{8}{1}100^7+\binom{8}{2}100^6+\cdots+100^0$ . Since $\binom{8}{4} = 70 < 100$ , there are no ``carry-overs, so the sum of digits in base-100 will simply be $\binom 80+\binom{8}1+\binom 82 + \cdots +\binom{8}{8} = 2^8=\boxed{256}$ . \end{sol1}

\begin{sol2} Let $A_0 = \{1,2,3,4,5,6,7,8\}$ . The number of 101-tuples of sets $(A_{100}, A_{99}, \ldots, A_1, A_0)$ , such that $A_{100} \subseteq A_{99} \subseteq \ldots \subseteq A_1 \subseteq A_0$ is equal to $K$ ; $\binom{8}{a_1}$ tells the number of ways to pick $a_1$ elements from $A_0$ , $a_2$ elements from $A_1$ , etc.

We shall now count $K$ another way. Consider all 8-digit (leading digits can be 0) base 101 integers; there are clearly $101^8$ such integers. Let $A_i$ be the set of all $i$ such that the $i$ -th digit is greater than or equal to $i$ ; then we have that $A_{100} \subseteq A_{99} \subseteq \ldots \subseteq A_1$ . Conversely, for any 101-tuple of sets $(A_{100}, A_{99}, \ldots, A_1, A_0)$ such that $A_{100} \subseteq A_{99} \subseteq \ldots \subseteq A_1 \subseteq A_0$ , we can construct an 8-digit base 101 integer from this set, by having the digit $i$ be the largest integer $k$ such that $i \in A_k$ .

Hence, $K = 101^8$ . We proceed as we did before to find the sum of the digits of $K$ when it is written in base 100 to arrive at our answer of $\boxed{256}$ . \end{sol2}

Problem 13

\setcounter{enumi}{12} $\triangle ABC$ is inscribed in circle $\mathcal{C}$ . The radius of $\mathcal{C}$ is 285, and $BC = 567$ . When the incircle of $\triangle ABC$ is reflected across segment $BC$ , it is tangent to $\mathcal{C}$ . Given that the inradius of $\triangle ABC$ can be expressed in the form $a\sqrt{b}$ , where $a$ and $b$ are positive integers and $b$ is not divisible by the square of any prime, find $a+b$ . (Alex Zhu)

Solution 13

\begin{sol1} We shall prove that in a circle $\mathcal{C}$ with center $O$ , radius $R$ , a chord $BC$ with midpoint $M$ such that $OM = m$ , and a point $A$ on $\mathcal{C}$ such that the incircle $\omega$ of $\triangle ABC$ with radius $r$ , when reflected across $BC$ , is tangent to $\mathcal{C}$ , we have that $r = 4m$ .

Let $I$ be the incenter of $\triangle ABC$ , let $I'$ be the reflection of $I$ across $BC$ (hence, it is the center of the reflection of the incircle of $\triangle ABC$ across $BC$ ), and let $O'$ be the reflection of $O$ across $BC$ . $IOO'I'$ is an isosceles trapezoid, so it is cyclic. Hence, by Ptolemy's theorem, $II' \cdot OO' + IO \cdot I'O' = O'I \cdot OI'$ . In other words, $(2r)(2m) + IO^2 = OI'^2$ , since $I'O' = IO$ and $O'I = OI'$ . But $OI' = R - r$ , since the reflection of $\omega$ across $BC$ is tangent to $\mathcal{C}$ , and $IO^2 = R^2 - 2Rr$ by Euler's distance formula, so $4rm + R^2 - 2Rr = R^2 - 2Rr + r^2$ , yielding $r = 4m$ .

It therefore suffices to find $m$ . By the Pythagorean theorem, since $OMB$ is right, we have that $m^2 + R^2 = \frac{BC^2}{4}$ , 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, $r = 4m = 6 \sqrt{379}$ , giving us an answer of $6 + 379 = \boxed{385}$ . \end{sol1}

\begin{sol2} We shall prove that in another way that a circle $\mathcal{C}$ with center $O$ , radius $R$ , a chord $BC$ with midpoint $M$ such that $OM = m$ , and a point $A$ on $\mathcal{C}$ such that the incircle $\omega$ of $\triangle ABC$ with radius $r$ , when reflected across $BC$ , is tangent to $\mathcal{C}$ , we have that $r = 4m$ .

Let $I$ be the incenter of $\triangle ABC$ , and let $I'$ be the reflection of $I$ across $BC$ (hence, it is the center of the reflection of the incircle of $\triangle ABC$ across $BC$ .) Let $E$ be the foot of the perpendicular from $O$ to $II'$ . We have that $IE = r - m$ and $OI^2 = R^2 - 2Rr$ by Euler's distance formula, so $OE^2 = R^2 - 2Rr - (r-m)^2 = R^2 - 2Rr + 2rm - r^2 - m^2$ . In addition, $EI' = m + r$ and $OI' = R - r$ , since the reflection of $\omega$ across $BC$ is tangent to $\mathcal{C}$ . Sine $\triangle OEI'$ is right, we have that $OE^2 + EI'^2 = OI'^2$ , that is, $R^2 - 2Rr + 2rm - r^2 - m^2 + m^2 + 2rm + r^2 = R^2 - 2Rr + r^2$ , again yielding $r = 4m$ .

We simply compute the answer the way we did before to arrive at an answer of $\boxed{385}$ . \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 $\left\lfloor \frac{2010}{12} \right\rfloor = \boxed{167}$ .

\emph{Remark: }I lost.

Problem 15

\setcounter{enumi}{14} Given that $\sum_{a = 1}^{491}\sum_{b = 1}^{491} \frac{1}{(a+bi)^4 - 1}$ can be expressed in the form $\frac{p + qi}{r}$ , where $\gcd(p, q, r) = 1$ and $r > 0$ , find the unique integer $k$ between 0 and 982 inclusive such that $983$ divides $(p + q) - kr$ . [Note: 983 is a prime.] (Alex Zhu)

Solution 15

Let $S_1 = S$ , $S_2 = \{iz : z \in S\}$ , $S_3 = \{i^2 z : z \in S\}$ , $S_4 = \{i^3 z : z \in S\}$ , and let $S' = S_1 \cup S_2 \cup S_3 \cup S_4$ . Note that the following:

The sets $\{z^4 : z \in S_i\}$ , for $1 \leq i \leq 4$ , are equal (since $i^4 = 1$ .) $\{iz : z \in S'\} = \{z : z \in S'\}$ , since $z \in S'$ if and only if $iz \in S'$ . The sets $\{z^2 : z \in S_1 \mbox{ or } z \in S_4\}$ is equal to the set $\{z^2 : z \in S_2 \mbox{ or } z \in S_3 \}$ , since $z \in S_1$ or $z \in S_4$ if and only if $-z \in S_2$ or $-z \in S_3$ . $S_4 = \{\bar{z} : z \in S_1\}$ . This is because $S_4$ is the set of all complex numbers of the form $i(a + bi) = -b + ai$ , where $a$ and $b$ are integers between 1 and 491 inclusive, which is the same as the set of all complex numbers of the form $a - bi$ , where $a$ and $b$ are integers between 1 and 491 inclusive. The latter set is clearly comprised of exactly the conjugates of the elements of $S_1$ .

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 $k$ such that $983 | p - qk$ , that is, we seek the value of $\frac{p}{q}$ modulo 983, that is, the value of $pq^{-1}$ 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 $b^2 + 1$ , $b^2 + 492^2$ , and $b^2 + 491^2$ are never divisible by $983$ , so the denominators of the above sum is never divisible by $983$ . (Alternatively, upon noticing that $r \neq 0$ , the problem statement implies that none of the denominators are divisible by $983$ .) As the above sum that we have arrived at is real, and none of its denominators are divisible of $983$ , we may manipulate the sum modulo 983.

We note that $491 \equiv -492 \pmod{983}$ , so $491^2 \equiv 492^2 \pmod{983}$ , yielding $\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}$ . Hence, our sum taken modulo $p$ is just $\frac{1}{2} \sum_{a=1}^{491} \frac{1}{1 + b^2}$ mod $p$ . Let this sum equal $T$ . 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 $\{\frac{1}{1}, \frac{1}{2}, \ldots, \frac{1}{p-1}\}$ is a permutation of $\{1, 2, \ldots, p-1\}$ modulo $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*}$Hence, \begin{align*} T &\equiv \frac{982}{8} \\ &\equiv \frac{491}{4} \\ &\equiv \frac{491 + 983}{4} \\ &\equiv \frac{737}{2} \\ &\equiv \frac{737 + 983}{2} \\ &\equiv 860 \pmod{983} \end{align*} giving us an answer of$ (Error compiling LaTeX. Unknown error_msg)\boxed{860}$.

Page

Toolbox

Search