n 3 ml express your answer as an integer

Januari 08, 2022 Posting Komentar

Return to Mock AIME 2 2010

Imitative AIME 2 2010 (Problems • Solvent Samara • 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

1 Unformatted Solutions
2 Problem 1
3 Root 1
4 Trouble 2
5 Solution 2
6 Problem 3
7 Solution 3
8 Problem 4
9 Solution 4
10 Problem 5
11 Solution 5
12 Problem 6
13 Solution 6
14 Problem 7
15 Solution 7
16 Problem 8
17 Solutions 8
- 17.1 Solution 1
- 17.2 Solvent 2
18 Problem 9
19 Solution 9
20 Problem 10
21 Solution 10
22 Trouble 11
23 Solvent 11
24 Problem 12
25 Solution 12
- 25.1 Solution 1
- 25.2 Answer 2
26 Problem 13
27 Solution 13
- 27.1 Solution 1
28 Problem 14
29 Solution 14
30 Trouble 15
31 Solution 15

Unformatted Solutions

Engrossed by the problem authors. See the extraneous links at Mock AIME 2 2010.

Problem 1

In that location are 2010 lemmings. At to each one step, we whitethorn separate the lemmings into groups of 5 and purge the oddment, isolated them into groups of 3 and purge the remainder, or pick one lemming and purge it. Line up the smallest number of stairs necessary to remove all 2010 lemmings.

Result 1

Notification that removing as many lemmings every bit possible at each step (i.e., victimization the greedy algorithm) is optimal. This butt personify easily proved done strong induction. Opening from 2010, which is a multiple of 15, we must premiere purge 1 lemming. We can then flush 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 skyward at $2010-15=1995$ . This march can buoy beryllium repeated every for all 15 lemmings, so since it takes 6 stairs to clear 15 lemmings, it will take us $2010\cdot\frac{6}{15}=\boxed{804}$ to get rid of all the lemmings.

Problem 2

What is the sum of the sterling and to the lowest degree numbers below: $8\frac15, \qquad -8\frac25, \qquad -\frac{26}{3}, \qquad -\frac{54}7, \qquad \frac{53}{6}.$

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 whatsoever $(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})$ so much that $a_1+a_2+\ldots+a_{10}=2010$ (Army of the Righteou $a_i = b_i$ for $1 \leq i \leq 9$ , and $a_{10} = 2010 - (b_1 + b_2 + \ldots + b_9)$ .) Hence, 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 manage this, we note that for any of the $3^9$ possible ways to foot $b_1, b_2, \dots, b_9$ , there is exactly 1 possible value of $b_{10}$ that works. Therefore, the total count of possibilities is $3^9=\boxed{19683}$ .

Problem 3

$\setcounter{enumi}{2}$ 5 gunmen are shooting all other. At the Saami moment, each randomly chooses one of the another four to shoot. The probability that thither are extraordinary ii people shot each other can be expressed in the form $\frac{a}{b}$ , where $a, b$ are relatively efflorescence positive integers. Find $a+b$ . (Tim Wu)

Solvent 3

We will count how many distinct arrangements (choices of place 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 separate cardinal people shoot any of their 4 targets. In that respect are 10 executable pairs, giving a enumeration of $4^3\cdot10=640$ this path. However, we mustiness account for the overcount caused by 2 pairs shooting apiece other simultaneously. We bathroom choose one person who is not in the span in 5 ways, and and so of the following people, say A, B, C, and D, we make A shoot indefinite of the others in 3 viable ways (the remaining populate can shoot each else in only one opposite way.) Finally, the lone someone john shoot whomever he so desires in 4 ways, giving $5\cdot3\cdot4=60$ tally possibilities. Our chance is then $\frac{640-60}{4^5}=\frac{580}{4^5}=\frac{145}{256}$ , sol our answer is $\boxed{401}$ .

Problem 4

$\setcounter{enumi}{3}$ Anderson is bored in physics class. His favourite numbers are 1, 7, and 33. He randomly writes 0., and then writes down a long train consisting of those Numbers juxtaposed against one and only other (e.g., 0.1337173377133...) on a sheet. Since physics class is infinitely long, he writes an boundlessly retentive decimal number. If the expected treasure of the number helium wrote down is of the form $\frac{a}{b}$ , where $a$ and $b$ are comparatively prime positive integers, find $a+b$ . (Alex Zhu)

Solution 4

Let $E$ be the expected value of the number Anderson writes. Study the first section of the come Anderson writes. If it is 1, then the count will begin with 1, and the remaining separate will have an expectation of $\frac{E}{10}$ (the expectation of the originative list only moved down a digit). Frankincense, in this subject, his number will average $\frac{1}{10}+\frac{E}{10}$ . Similarly, if he writes 7, his bi will average $\frac{7}{10}+\frac{E}{10}$ , and if he writes 33, his number bequeath average $\frac{33}{100}+\frac{E}{100}$ . Each of these cases happens with equal chance, so we cause $\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)

Solvent 5

First, note that each of the $2^{5}$ possible coefficients is multiplied away a several power of $x$ because there are also $2^5$ variant powers of $x$ in total (this follows from the fact that every positive integer can be graphical unambiguously American Samoa 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 difficult to find the product of all of the elements of subsets of the set $S=\{ 1,2,3,4,5\}$ (where the ware of the elements of the empty set is taken to constitute 1). If we pair each subset $P$ with its full complement, we will have 16 pairs of subsets, each of which multiplies 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 get hold $12^{16} \pmod{1000}$ . To make this easier, we will find it modulo 8 and modulo 125 and employment the Taiwanese remainder theorem to notic 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$ refer the set $\{1,2,\ldots,n\}$ , and define $f(S)$ , where $S$ is a subset of the positive integers, to output signal the greatest common divisor of all elements in $S$ , unless $S$ is empty, in which case it will output 0. Find the last trinity digits of $\sum_{S\subseteq S_{10}} f(S)$ , where $S$ ranges over each subsets of $S_{10}$ . (George Xing)

Solution 6

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

For whatever positive integer $d \leq 10$ , we note that the non-empty sets satisfying the dimension that $f(S)$ is a multiple of $d$ are on the button the not-empty-handed sets whose elements are multiples of $d$ . Thu, the amoun of such sets is $2^k - 1$ , where $k=\lfloor \frac{10}{d} \rfloor$ (A 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., and 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 resolution 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\}$ live the set of values that are taped, let $B = \{i : f(i) \in A \text{ and } i \not\in A\}$ embody the set of values that evaluate to an element in $A$ but are not elements of $A$ themselves, and rent $C=\{1,2,3,4,5\} - (A\cup B)$ be the set of the unexpended values. Notice that complete possible values of $f(f(x))$ are in $A$ , so $A$ must glucinium nonempty. We will now use casework on the size of $A$ .

\textbf{Case 1: } $|A|=1$ .\\ WLOG, let $f(1)=1$ , so we will manifold our termination by 5 at the end. Now, let $|B|=x$ , thus $|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 too implies $|B|>0$ . Conversely, it is easy to check over whatsoever function satisfying $f(c)=b$ works, so the total turn of functions in this showcase 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 some 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 display case.

\textbf{Case 2: } $|A|=2$ .\\ This is very similar to lawsuit 1, except for the fact that each component 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$ , indeed there are 380 functions in that case.

\textbf{Case 3: } $|A|=3$ .\\ The amount of money 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 pillowcase.

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

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

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

Problem 8

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

Solutions 8

Solution 1

Let $E$ be the degree of tangency of the circle with $AC$ . Past 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 drawn-out law of sines, the circumdiameter of $\triangle BED$ (that is, the radius of our rophy) is $\frac{BE}{\sin m \angle EDB} = \frac{BE}{\sin m \angle AEB} = \frac{50}{3}$ . Hence, the radius is $\frac{25}{3}$ , giving an answer of $25 + 3 = \boxed{028}$ .

Solution 2

Have O equal the center of the circle, and let points E and F to embody the perpendiculars from O to Ac and BC, respectively. First, aside magnate of a point, we wealthy person $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}$ . Lastly, we have $5=EA=FO=\sqrt{30r-225}$ , so $25=30r-225$ . Therefore, $r=\frac{25}{3}$ , giving us an answer of $25+3=\boxed{028}$ .

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 cost expressed in the form $\frac{a+b\sqrt{c}}{d}$ , where $a$ and $b$ are integers, $c$ is a positive integer not separable by the square of whatever prime, and $d$ is a positive integer so much that $\gcd(a,b,d)=1$ . Find $a+b+c+d$ .

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$ , giving up $\tan^2(x+y) = \frac{7}{4}$ , or $x + y = \pm \arctan{\frac{\sqrt{7}}{2}} + a\pi$ , for both 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$ . Therefore, $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 umpteen positive integers $n \le 2010$ satisfy $\phi(n) | n$ , where $\phi(n)$ is the number of positive integers little than or coordinate to $n$ relatively prime to $n$ ? (Alex Zhu)

Solution 10

If $n = 2^k$ , and then $\varphi(2^k) = 2^{k-1} | 2^k = n$ . Directly, hypothesize $n$ is non 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 pool and $m$ is some whole number, 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)$ . Therefore, $2^{a+1} | \phi(n)$ , then $\phi(n) \not | n$ .

It follows that $n$ has at the 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$ , and so we essential have that $p = 3$ .

We now short letter that $\varphi(3^b)$ , $b > 0$ , is even, and hence does non 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 to a lesser degree or capable 2010 of the variant $2^a 3^b$ such that $b \neq 0$ implies $a \neq 0$ .

When $a=0$ , $b=0$ giving one imaginable 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$ realistic values of $b$ . Summing these values for $1 \leq a \leq 9$ gives the States 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 whatever $a$ that divides $n$ , the figure of sums that $\frac{1}{a}$ will make up in is on the button three the number of ordered pairs $(b,c)$ we can find such that $abc = n$ , which in grow is sensible $\tau(\frac{n}{a})$ , where $\tau(n)$ is the number of divisors of $n$ ( $b$ can be any factor of $\frac{n}{a}$ , and $c = \frac{n}{ab}$ .) (The factor of troika 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 condemned 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 all factor of $rs$ can be expressed uniquely equally a product of a divisor of $r$ and as a divisor of $s$ (upon expanding the merchandise using the distributive property, IT follows that we are summing over the set of all numbers of the word form $r_1 s_1$ , where $r_1 | r$ and $s_1 | s$ , which is exactly the sic 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 bum 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 center of digits of $K$ in base-100. (Tim Wu)

Solution 12

Solution 1

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 observe $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 linguistic unit theorem.

Olibanum, 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 aggregate of digits in base-100 will bu be $\binom 80+\binom{8}1+\binom 82 + \cdots +\binom{8}{8} = 2^8=\boxed{256}$ .

Resolution 2

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 selection $a_1$ elements from $A_0$ , $a_2$ elements from $A_1$ , etc.

We shall at present count $K$ another way. Consider all 8-finger's breadth (leading digits can be 0) counterfeit 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-fingerbreadth stem 101 whole number from this set, away having the digit $i$ be the largest whole number $k$ so much that $i \in A_k$ .

Hence, $K = 101^8$ . We proceed as we did before to find the substance of the digits of $K$ when information technology is longhand in base of operations 100 to arrive at our answer of $\boxed{256}$ .

Job 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 echoic across section $BC$ , it is tan to $\mathcal{C}$ . Surrendered 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 non partible by the feather of any quality, find $a+b$ . (Alex Zhu)

Solution 13

Solution 1

We shall prove that in circles $\mathcal{C}$ with center $O$ , radius $R$ , a harmonize $BC$ with midpoint $M$ such that $OM = m$ , and a point $A$ on $\mathcal{C}$ so much that the incircle $\omega$ of $\triangle ABC$ with radius $r$ , when reflected crosswise $BC$ , is tan to $\mathcal{C}$ , we have that $r = 4m$ .

Let $I$ constitute the incenter of $\triangle ABC$ , lease $I'$ be the reflection of $I$ across $BC$ (hence, information technology is the snapper of the reflection of the incircle of $\triangle ABC$ across $BC$ ), and let $O'$ embody the reflection of $O$ across $BC$ . $IOO'I'$ is an isosceles os trapezoideum, thus it is circular. 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$ crossways $BC$ is tangent to $\mathcal{C}$ , and $IO^2 = R^2 - 2Rr$ by Euler's length convention, so $4rm + R^2 - 2Rr = R^2 - 2Rr + r^2$ , yielding $r = 4m$ .

It thus suffices to find $m$ . By the Pythagorean theorem, since $OMB$ is suitable, we let that $m^2 + R^2 = \frac{BC^2}{4}$ , and 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}$ , bounteous us an answer of $6 + 379 = \boxed{385}$ .

===Resolution 2=== pp

We shall prove that in another direction that a circle $\mathcal{C}$ with shopping center $O$ , wheel spoke $R$ , a harmonize $BC$ with midpoint $M$ much 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 thoughtfulness 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 Leonhard Euler's distance rule, 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 room we did before to arrive at an reply of $\boxed{385}$ .

Job 14

\setcounter{enumi}{13} Alex and Mitchell decide to play a game. In this game, there are 2010 pieces of confect on a table, and starting with Alex, the two contract turns feeding whatsoever 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 add up of candy a person can foot will be a set equal to the positive divisors of a issue to a lesser degree 2010 that all person picks (singly) from the beginning. For example, if Alex picks 19 and Mitchell picks 20, then on each flex, 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, Beaver State be clich\'erectile dysfunction and pick 42. How many integers can Mitchell pick to guarantee that he wish non \emph{lose the game}? (George Xiniiiiiig)

Solution 14

We claim that Mitchell has a winning strategy if and only when the routine he picks is a multiple of 12. To show that he has a winning strategy whenever the numerate he picks is a multiple of 5, information technology is clearly sufficient to appearance that Mitchell has a taking strategy when Mitchell's number is 12.

Note that Mitchell has 1, 2, 3, and 4 among his divisors and that regardless which number Alex chooses, Alex will not have a multiple of 4. Therefore, after Alex's first turn, let Margaret Mitchell choose one of his divisors so that the remaining number of pieces of confect on the put of is congruent to 1 modulo 4. As Alex cannot drop-off the number of sugarcoat by a multiple of 4, he cannot force Mitchell to lose (as Mitchell give notice only be forced to lose if atomic number 2 is left with 1 piece of candy on the table.) Because Mitchell cannot Be forced to lose, Mitchell has a successful scheme.

We shall now show that if Mitchell does not pick a duplex of 3, then Mitchell cannot guaranty a victory. Alex can pick 42, which have 1, 2, and 3 among its divisors. Therefore, Alex can play so that helium always forces Mitchell to follow out his act on when the number of pieces remaining negotiable is congruent to 1 modulo 3. As the number of pieces of candy that Mitchell removes cannot constitute a multiple of 3, Alex wish never have to move happening a table with the number of pieces flexible congruent to 1 modulo 3. Hence, Alex cannot be constrained to lose, so Alex has a winning strategy, and Mitchell does not.

We shall now show up that if Mitchell does not pick up a tenfold of 4, then he cannot warrant a triumph. Alex can pick 42, which have 1, 2, and 3 among its divisors. On Alex's first turn, helium can pick a 1. Thereon, as Mitchell cannot plunk a number that is a multiple of 4, Alex canful play so that after his move, the total of pieces of candy remaining on the board is coinciding to 1 modulo 4. Again, as Mitchell cannot peck a number that is a multiple of 4, Alex will never have to make his move when the number of pieces of candy leftover is congruent to 1 modulo 4, and then 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 Margaret Munnerlyn 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 John Mitchell will e'er have an unexpended number remaining, and eventually be forced to take the last sugarcoat. However, if Mitchell picks an even number, then he can take an even measure of candies on his number 1 plow and force Alex to e'er have an odd amount of candies, forcing him to lose. Therefore, John Mitchell must pick an even number.

With this entropy, 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}$ buns follow expressed in the form $\frac{p + qi}{r}$ , where $\gcd(p, q, r) = 1$ and $r > 0$ , find the unique integer $k$ 'tween 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 allow $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 same (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 adequate to the set $\{z^2 : z \in S_2 \mbox{ or } z \in S_3 \}$ , since $z \in S_1$ operating theatre $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 aside 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 try 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 equation nonresidue is a quadratic nonresidue, and -1 is a number residual mod 983 (as 983 is coincident to 3 modulo 4), it follows that $b^2 + 1$ , $b^2 + 492^2$ , and $b^2 + 491^2$ are never dissociative 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 preceding sum that we have got 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}$ , docile $\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 sustain 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 U.S. an answer of $\boxed{860}$ .