Home » 国际竞赛 » 数学国际竞赛 » AMC美国数学竞赛 » Details

【全网首发】2021AIME II 真题及答案

Category: AMC美国数学竞赛, 国际竞赛, 翰林严选 Date: 2021年5月8日上午11:25

【全网首发】2021AIME II 真题及答案

文末答案

Problem 1

Find the arithmetic mean of all the three-digit palindromes. (Recall that a palindrome is a number that reads the same forward and backward, such as $777$ or $383$ .)

Problem 2

Equilateral triangle $ABC$ has side length $840$ . Point $D$ lies on the same side of line $BC$ as $A$ such that $\overline{BD} \perp \overline{BC}$ . The line $\ell$ through $D$ parallel to line $BC$ intersects sides $\overline{AB}$ and $\overline{AC}$ at points $E$ and $F$ , respectively. Point $G$ lies on $\ell$ such that $F$ is between $E$ and $G$ , $\triangle AFG$ is isosceles, and the ratio of the area of $\triangle AFG$ to the area of $\triangle BED$ is $8:9$ . Find $AF$ .

Diagram

$[asy] pair A,B,C,D,E,F,G; B=origin; A=5*dir(60); C=(5,0); E=0.6*A+0.4*B; F=0.6*A+0.4*C; G=rotate(240,F)*A; D=extension(E,F,B,dir(90)); draw(D--G--A,grey); draw(B--0.5*A+rotate(60,B)*A*0.5,grey); draw(A--B--C--cycle,linewidth(1.5)); dot(A^^B^^C^^D^^E^^F^^G); label("$A$",A,dir(90)); label("$B$",B,dir(225)); label("$C$",C,dir(-45)); label("$D$",D,dir(180)); label("$E$",E,dir(-45)); label("$F$",F,dir(225)); label("$G$",G,dir(0)); label("$\ell$",midpoint(E--F),dir(90)); [/asy]$

Problem 3

Find the number of permutations $x_1, x_2, x_3, x_4, x_5$ of numbers $1, 2, 3, 4, 5$ such that the sum of five products $x_1x_2x_3 + x_2x_3x_4 + x_3x_4x_5 + x_4x_5x_1 + x_5x_1x_2$

Problem 4

There are real numbers $a, b, c,$ and $d$ such that $-20$ is a root of $x^3 + ax + b$ and $-21$ is a root of $x^3 + cx^2 + d.$ These two polynomials share a complex root $m + \sqrt{n} \cdot i,$ where $m$ and $n$ are positive integers and $i = \sqrt{-1}.$ Find $m+n.$

Problem 5

For positive real numbers $s$ , let $\tau(s)$ denote the set of all obtuse triangles that have area $s$ and two sides with lengths $4$ and $10$ . The set of all $s$ for which $\tau(s)$ is nonempty, but all triangles in $\tau(s)$ are congruent, is an interval $[a,b)$ . Find $a^2+b^2$ .

Problem 6

For any finite set $S$ , let $|S|$ denote the number of elements in $S$ . Find the number of ordered pairs $(A,B)$ such that $A$ and $B$ are (not necessarily distinct) subsets of $\{1,2,3,4,5\}$ that satisfy $|A| \cdot |B| = |A \cap B| \cdot |A \cup B|$

Problem 7

Let $a, b, c,$ and $d$ be real numbers that satisfy the system of equations $\begin{align*} a + b &= -3, \\ ab + bc + ca &= -4, \\ abc + bcd + cda + dab &= 14, \\ abcd &= 30. \end{align*}$ There exist relatively prime positive integers $m$ and $n$ such that $a^2 + b^2 + c^2 + d^2 = \frac{m}{n}.$ Find $m + n$ .

Problem 8

An ant makes a sequence of moves on a cube where a move consists of walking from one vertex to an adjacent vertex along an edge of the cube. Initially the ant is at a vertex of the bottom face of the cube and chooses one of the three adjacent vertices to move to as its first move. For all moves after the first move, the ant does not return to its previous vertex, but chooses to move to one of the other two adjacent vertices. All choices are selected at random so that each of the possible moves is equally likely. The probability that after exactly 8 moves that ant is at a vertex of the top face on the cube is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Problem 9

Find the number of ordered pairs $(m, n)$ such that $m$ and $n$ are positive integers in the set $\{1, 2, ..., 30\}$ and the greatest common divisor of $2^m + 1$ and $2^n - 1$ is not $1$ .

Problem 10

Two spheres with radii $36$ and one sphere with radius $13$ are each externally tangent to the other two spheres and to two different planes $\mathcal{P}$ and $\mathcal{Q}$ . The intersection of planes $\mathcal{P}$ and $\mathcal{Q}$ is the line $\ell$ . The distance from line $\ell$ to the point where the sphere with radius $13$ is tangent to plane $\mathcal{P}$ is $\tfrac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

Diagram

Remarks

1. Let $\mathcal{R}$ be the plane that is determined by the centers of the spheres, as shown in the black points. Clearly, the side-lengths of the black dashed triangle are $49,49,$ and $72.$

1. Plane $\mathcal{P}$ is tangent to the spheres at the green points. Therefore, the blue dashed line segments are the radii of the spheres.

By symmetry, since planes and are reflections of each other about plane it follows that the three planes are concurrent to line From here, we can conclude all of the following:
- - The four black dashed line segments all lie in plane $\mathcal{R}.$
- - The four green solid line segments all lie in plane $\mathcal{P}.$
- The red point (the foot of the perpendicular from the smallest sphere's center to line $\ell$ ), as well as the other points on line $\ell,$ all lie in planes $\mathcal{P,Q},$ and $\mathcal{R}.$

Problem 11

A teacher was leading a class of four perfectly logical students. The teacher chose a set $S$ of four integers and gave a different number in $S$ to each student. Then the teacher announced to the class that the numbers in $S$ were four consecutive two-digit positive integers, that some number in $S$ was divisible by $6$ , and a different number in $S$ was divisible by $7$ . The teacher then asked if any of the students could deduce what $S$ is, but in unison, all of the students replied no.

However, upon hearing that all four students replied no, each student was able to determine the elements of $S$ . Find the sum of all possible values of the greatest element of $S$ .

Problem 12

A convex quadrilateral has area $30$ and side lengths $5, 6, 9,$ and $7,$ in that order. Denote by $\theta$ the measure of the acute angle formed by the diagonals of the quadrilateral. Then $\tan \theta$ can be written in the form $\tfrac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

Problem 13

Find the least positive integer $n$ for which $2^n + 5^n - n$ is a multiple of $1000$ .

Problem 14

Let $\Delta ABC$ be an acute triangle with circumcenter $O$ and centroid $G$ . Let $X$ be the intersection of the line tangent to the circumcircle of $\Delta ABC$ at $A$ and the line perpendicular to $GO$ at $G$ . Let $Y$ be the intersection of lines $XG$ and $BC$ . Given that the measures of $\angle ABC, \angle BCA,$ and $\angle XOY$ are in the ratio $13 : 2 : 17,$ the degree measure of $\angle BAC$ can be written as $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Problem 15

Let $f(n)$ and $g(n)$ be functions satisfying $f(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ 1 + f(n+1) & \text{ otherwise} \end{cases}$ and $g(n) = \begin{cases}\sqrt{n} & \text{ if } \sqrt{n} \text{ is an integer}\\ 2 + g(n+2) & \text{ otherwise} \end{cases}$ for positive integers $n$ . Find the least positive integer $n$ such that $\tfrac{f(n)}{g(n)} = \tfrac{4}{7}$ .

参考答案及详解注册后登录可见：

Problem 1

Solution 1

Recall that the arithmetic mean of all the $n$ digit palindromes is just the average of the largest and smallest $n$ digit palindromes, and in this case the $2$ palindromes are $101$ and $999$ and $\frac{101+999}{2}=550$ and $\boxed{550}$ is the final answer.

~ math31415926535

Solution 2

For any palindrome $\underline{ABA}$ , note that $\underline{ABA}$ is 100A + 10B + A, which is also 101A + 10B. The average for A is 5 since A can be any of 1, 2, 3, 4, 5, 6, 7, 8, or 9. The average for B is 4.5 since B is either 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. Therefore, the answer is 505 + 45 = $\boxed{550}$ .

- ARCTICTURN

Solution 3 (Symmetry and Generalization)

For every three-digit palindrome $\underline{ABA}$ with $A\in\{1,2,3,4,5,6,7,8,9\}$ and $B\in\{0,1,2,3,4,5,6,7,8,9\},$ note that $\underline{(10-A)(9-B)(10-A)}$ must be another palindrome by symmetry. Therefore, we can pair each three-digit palindrome uniquely with another three-digit palindrome so that they sum to $\begin{align*} \underline{ABA}+\underline{(10-A)(9-B)(10-A)}&=\left[100A+10B+A\right]+\left[100(10-A)+10(9-B)+(10-A)\right] \\ &=\left[100A+10B+A\right]+\left[1000-100A+90-10B+10-A\right] \\ &=1000+90+10 \\ &=1100. \end{align*}$ For instances: $\begin{align*} 171+929&=1100, \\ 262+838&=1100, \\ 303+797&=1100, \\ 414+686&=1100, \\ 545+555&=1100, \end{align*}$ and so on.

From this symmetry, the arithmetic mean of all the three-digit palindromes is $\frac{1110}{2}=\boxed{550}.$

Remark

By the Multiplication Principle, there are $9\cdot10=90$ three-digit palindromes in total. Their sum is $1100\cdot45=49500,$ as we can match them into $45$ pairs such that the sum of each pair is $1100.$

~MRENTHUSIASM

Solution 4 (Very, Very Easy and Quick)

We notice that a three-digit palindrome looks like this $\overline{aba}$

And we know a can be any number from 1-9, and b can be any number from 0-9, so there are $9\times{10}=90$ three-digit palindromes

We want to find the sum of these 90 palindromes and divide it by 90 to find the arithmetic mean

How can we do that? Instead of adding the numbers up, we can break each palindrome into two parts: 101a+10b

Thus, all of these 90 palindromes can be broken into this form

Thus, the sum of these 90 palindromes will be $101\times{(1+2+...+9)}\times{10}+10\times{(0+1+2+...+9)}\times{9}$ , because each a will be in 10 different palindromes (since for each a, there are 10 choices for b). The same logic explains why there is a times 9 when computing the total sum of b.

We get a sum of $45\times{1100}$

But don't compute this! There's no need. Divide this by 90 and you will get $\boxed{550}$

~ $\alpha b \alpha$

Solution 5 (Extremely Fast Solution)

The average values of the first and last digits are each $5,$ and the average value of the middle digit is $4.5,$ so the average of all three-digit palindromes is $5\cdot 10^2+4.5\cdot 10+5=\boxed{550}.$

Problem 2

Solution 1 (Area Formulas for Triangles)

By angle-chasing, $\triangle AGF$ is a $30^\circ\text{-}30^\circ\text{-}120^\circ$ triangle, and $\triangle BED$ is a $30^\circ\text{-}60^\circ\text{-}90^\circ$ triangle.

Let $AF=x.$ It follows that $FG=x$ and $EB=FC=840-x.$ By the side-length ratios in $\triangle BED,$ we have $DE=\frac{840-x}{2}$ and $DB=\frac{840-x}{2}\cdot\sqrt3.$

Let the brackets denote areas. We have $[AFG]=\frac12\cdot AF\cdot FG\cdot\sin{\angle AFG}=\frac12\cdot x\cdot x\cdot\sin{120^\circ}=\frac12\cdot x^2\cdot\frac{\sqrt3}{2}$ and $[BED]=\frac12\cdot DE\cdot DB=\frac12\cdot\frac{840-x}{2}\cdot\left(\frac{840-x}{2}\cdot\sqrt3\right).$

We set up and solve an equation for $x:$ $\begin{align*} \frac{[AFG]}{[BED]}&=\frac89 \\ \frac{\frac12\cdot x^2\cdot\frac{\sqrt3}{2}}{\frac12\cdot\frac{840-x}{2}\cdot\left(\frac{840-x}{2}\cdot\sqrt3\right)}&=\frac89 \\ \frac{2x^2}{(840-x)^2}&=\frac89 \\ \frac{x^2}{(840-x)^2}&=\frac49. \end{align*}$ Since $0<x<840,$ it is clear that $\frac{x}{840-x}>0.$ Therefore, we take the positive square root for both sides: $\begin{align*} \frac{x}{840-x}&=\frac23 \\ 3x&=1680-2x \\ 5x&=1680 \\ x&=\boxed{336}. \end{align*}$

~MRENTHUSIASM

Solution 2

We express the areas of $\triangle BED$ and $\triangle AFG$ in terms of $AF$ in order to solve for $AF.$

We let $x = AF.$ Because $\triangle AFG$ is isosceles and $\triangle AEF$ is equilateral, $AF = FG = EF = AE = x.$

Let the height of $\triangle ABC$ be $h$ and the height of $\triangle AEF$ be $h'.$ Then we have that $h = \frac{\sqrt{3}}{2}(840) = 420\sqrt{3}$ and $h' = \frac{\sqrt{3}}{2}(EF) = \frac{\sqrt{3}}{2}x.$

Now we can find $DB$ and $BE$ in terms of $x.$ $DB = h - h' = 420\sqrt{3} - \frac{\sqrt{3}}{2}x,$ $BE = AB - AE = 840 - x.$ Because we are given that $\angle DBC = 90,$ $\angle DBE = 30.$ This allows us to use the sin formula for triangle area: the area of $\triangle BED$ is $\frac{1}{2}(\sin 30)(420\sqrt{3} - \frac{\sqrt{3}}{2}x)(840-x).$ Similarly, because $\angle AFG = 120,$ the area of $\triangle AFG = \frac{1}{2}(\sin 120)(x^2).$

Now we can make an equation:

$\frac{\triangle AFG}{\triangle BED} = \frac{8}{9}$ $\frac{\frac{1}{2}(\sin 120)(x^2)}{\frac{1}{2}(\sin 30)(420\sqrt{3} - \frac{\sqrt{3}}{2}x)(840-x)} = \frac{8}{9}$ $\frac{x^2}{(420 - \frac{x}{2})(840-x)} = \frac{8}{9}$

To make further calculations easier, we scale everything down by $420$ (while keeping the same variable names, so keep that in mind).

$\frac{x^2}{(1-\frac{x}{2})(2-x)} = \frac{8}{9}$ $8(1-\frac{x}{2})(2-x) = 9x^2$ $16-16x + 4x^2 = 9x^2$ $5x^2 + 16x -16 = 0$ $(5x-4)(x+4) = 0$

Thus $x = \frac{4}{5}.$ Because we scaled down everything by $420,$ the actual value of $AF$ is $(420)\frac{4}{5} = \boxed{336}.$

~JimY

Solution 3 (Pretty Straightforward)

$\angle AFE = \angle AEF = \angle EAF = 60^{0} \Rightarrow \angle AFG = 120^{0}$ So, If $\Delta AFG$ is isosceles, it means that $AF = FG$ .

Let $AF = FG = AE = EF = x$

So, $[\Delta AFG] = \frac{1}{2} \cdot x^{2} \textup{sin} 120^{0} = \frac{\sqrt{3}}{4}x^{2}$

In $\Delta BED$ , $BE = 840 - x$ , Hence $DE = \frac{840 - x}{2}$ (because $\textup{sin} 30^{0} = \frac{1}{2}$ )

Therefore, $[\Delta BED] = \frac{1}{2} (840 - x) \left (\frac{840-x}{2} \right) \textup{sin} 60^{0}$

So, $[\Delta BED] = \frac{\sqrt{3}}{4} (840 - x) \left (\frac{840-x}{2} \right) = \frac{\sqrt{3}}{8} (840 - x)^{2}$

Now, as we know that the ratio of the areas of $\Delta AFG$ and $\Delta BED$ is $8:9$

Substituting the values, we get

$\frac{\frac{\sqrt{3}}{4}x^{2}}{\frac{\sqrt{3}}{8} (840 - x)^{2}} = \frac{8}{9} \Rightarrow \left (\frac{x}{840 - x} \right)^{2} = \frac{4}{9}$ Hence, $\frac{x}{840 - x} = \frac{2}{3}$ . Solving this, we easily get $x = 336$

We have taken $AF = x$ , Hence, $AF = \boxed{336}$

-Arnav Nigam

Solution 4 (Similar Triangles)

Since $\triangle AFG$ is isosceles, $AF = FG$ , and since $\triangle AEF$ is equilateral, $AF = EF$ . Thus, $EF = FG$ , and since these triangles share an altitude, they must have the same area.

Drop perpendiculars from $E$ and $F$ to line $BC$ ; call the meeting points $P$ and $Q$ , respectively. $\triangle BEP$ is clearly congruent to both $\triangle BED$ and $\triangle FQC$ , and thus each of these new triangles has the same area as $\triangle BED$ . But we can "slide" $\triangle BEP$ over to make it adjacent to $\triangle FQC$ , thus creating an equilateral triangle whose area has a ratio of 18:8 when compared to $\triangle AEF$ (based on our conclusion from the first paragraph). Since these triangles are both equilateral, they are similar, and since the area ratio 18:8 reduces to 9:4, the ratio of their sides must be 3:2. So, because $FC$ and $AF$ represent sides of these triangles, and they add to 840, $AF$ must equal two-fifths of 840, or $\boxed{336}$ .

Problem 3

Solution 1

Since $3$ is one of the numbers, a product with a $3$ in it is automatically divisible by $3$ , so WLOG $x_3=3$ , we will multiply by $5$ afterward since any of $x_1, x_2, ..., x_5$ would be $3$ , after some cancelation we see that now all we need to find is the number of ways that $x_5x_1(x_4+x_2)$ is divisible by $3$ , since $x_5x_1$ is never divisible by $3$ , now we just need to find the number of ways $x_4+x_2$ is divisible by $3$ , after some calculation you will see that there are $16$ ways to choose $x_1, x_2, x_4,$ and $x_5$ in this way. So the desired answer is $16 \times 5=\boxed{080}$ .

~ math31415926535

Solution 2 (Cyclic Symmetry and Casework)

The expression $x_1x_2x_3 + x_2x_3x_4 + x_3x_4x_5 + x_4x_5x_1 + x_5x_1x_2$ has cyclic symmetry. Without the loss of generality, let $x_1=3.$ It follows that $\{x_2,x_3,x_4,x_5\}=\{1,2,4,5\}.$ We have

$x_1x_2x_3 + x_2x_3x_4 + x_3x_4x_5 + x_4x_5x_1 + x_5x_1x_2\equiv x_2x_3x_4 + x_3x_4x_5\pmod{3}.$

$x_2,x_3,x_4,x_5$ are congruent to $1,2,1,2\pmod{3}$ in some order.

We construct the following table for the case $x_1=3,$ with all values in modulo $3:$ $\begin{array}{c||c|c|c|c|c||c} & & & & & & \\ [-2.5ex] \textbf{Row} & \boldsymbol{x_2} & \boldsymbol{x_3} & \boldsymbol{x_4} & \boldsymbol{x_5} & \boldsymbol{x_2x_3x_4 + x_3x_4x_5} & \textbf{Valid?} \\ [0.5ex] \hline & & & & & & \\ [-2ex] 1 & 1 & 1 & 2 & 2 & 0 & \checkmark \\ 2 & 1 & 2 & 1 & 2 & 0 & \checkmark \\ 3 & 1 & 2 & 2 & 1 & 2 & \\ 4 & 2 & 1 & 1 & 2 & 1 & \\ 5 & 2 & 1 & 2 & 1 & 0 & \checkmark \\ 6 & 2 & 2 & 1 & 1 & 0 & \checkmark \end{array}$ For Row 1, $(x_2,x_3)$ can be either $(1,4)$ or $(4,1),$ and $(x_4,x_5)$ can be either $(2,5)$ or $(5,2).$ By the Multiplication Principle, Row 1 produces $2\cdot2=4$ permutations. Similarly, Rows 2, 5, and 6 each produce $4$ permutations.

Together, we get $4\cdot4=16$ permutations for the case $x_1=3.$ By the cyclic symmetry, the cases $x_2=3, x_3=3, x_4=3,$ and $x_5=3$ all have the same count. Therefore, the total number of permutations $x_1, x_2, x_3, x_4, x_5$ is $16\cdot5=\boxed{080}.$

~MRENTHUSIASM

Solution 3

WLOG, let $x_{3} = 3$ So, the terms $x_{1}x_{2}x_{3}, x_{2}x_{3}x_{4},x_{3}x_{4}x_{5}$ are divisible by $3$ .

We are left with $x_{4}x_{5}x_{1}$ and $x_{5}x_{1}x_{2}$ . We need $x_{4}x_{5}x_{1} + x_{5}x_{1}x_{2} \equiv 0 (mod 3)$ The only way is when They are $(+1,-1)$ or $(-1, +1)$ (mod 3)

The numbers left with us are $1,2,4,5$ which are $+1,-1,+1,-1$ (mod $3$ ) respectively.

$+1$ (of $x_{4}x_{5}x_{1}$ or $x_{5}x_{1}x_{2}$ ) $= +1 \cdot +1 \cdot +1$ $\;\;\; OR \;\;\;+1$ (of $x_{4}x_{5}x_{1}$ or $x_{5}x_{1}x_{2}$ ) = $-1 \cdot -1 \cdot +1$ .

$-1$ (of $x_{4}x_{5}x_{1}$ or $x_{5}x_{1}x_{2}$ ) $= -1 \cdot -1 \cdot -1$ $\;\;\; OR \;\;\;-1$ (of $x_{4}x_{5}x_{1}$ or $x_{5}x_{1}x_{2}$ ) = $-1 \cdot +1 \cdot +1$

But, as we have just two $+1's$ and two $-1's$ , Hence, We will have to take $+1 = +1 \cdot -1 \cdot -1$ and $-1 = -1 \cdot +1 \cdot +1$ Among these two, we have a $+1$ and $-1$ in common, i.e. $(x_{5}, x_{1}) = (+1, -1) or (-1, +1)$ (because $x_{1}$ and $x_{5}$ are common in $x_{4}x_{5}x_{1}$ and $x_{5}x_{1}x_{2}$ )

So, $(x_{5}, x_{1}) \in {(1,2), (1,5), (4,2), (4,5), (2,1), (5,1), (2,4), (5,4)}$ i.e. $8$ values.

For each value of $(x_{5}, x_{1})$ we get $2$ values for $(x_{2}, x_{4})$ Hence, in total, we have $8 \times 2 = 16$ ways.

But any of the $x_{i} 's$ can be $3$ So, $16 \times 5 = \boxed{080}$

Problem 4

Solution 1 (Complex Conjugate Root Theorem)

By the Complex Conjugate Root Theorem, the imaginary roots for each of $x^3+ax+b$ and $x^3+cx^2+d$ are a pair of complex conjugates. Let $z=m+\sqrt{n}\cdot i$ and $\overline{z}=m-\sqrt{n}\cdot i.$ It follows that the roots of $x^3+ax+b$ are $-20,z,\overline{z},$ and the roots of $x^3+cx^2+d$ are $-21,z,\overline{z}.$

We know that $\begin{align*} z+\overline{z}&=2m, \hspace{10mm} & (1) \\ z\overline{z}&=m^2+n. & (2) \end{align*}$

Applying Vieta's Formulas to $x^3+ax+b,$ we have $-20+z+\overline{z}=0,$ from which $\begin{align*} z+\overline{z}&=20 \hspace{12.5mm} & (3) \\ \underbrace{2m}_{\text{by }(1)}&=20 & \\ m&=10. & (4) \end{align*}$

Applying Vieta's Formulas to $x^3+cx^2+d,$ we have $-21z-21\overline{z}+z\overline{z}=0,$ from which $\begin{align*} -21\left(z+\overline{z}\right)+z\overline{z}&=0 \\ -21\underbrace{\left(20\right)}_{\text{by }(3)}+\underbrace{\left(m^2+n\right)}_{\text{by }(2)}&=0 \\ m^2+n&=420 \\ {\underbrace{10}_{\text{by }(4)}}^2+n&=420 \\ n&=320. \hspace{5.75mm} (5) \end{align*}$ Finally, we get $m+n=\boxed{330}$ by $(4)$ and $(5).$

~MRENTHUSIASM

Solution 2 (Somewhat Bashy)

$(-20)^{3} + (-20)a + b = 0$ , hence $-20a + b = 8000$

Also, $(-21)^{3} + c(-21)^{2} + d = 0$ , hence $441c + d = 9261$

$m + i \sqrt{n}$ satisfies both $\Rightarrow$ we can put it in both equations and equate to 0.

In the first equation, we get $(m + i \sqrt{n})^{3} + a(m + i \sqrt{n}) + b = 0$ Simplifying this further, we get $(m^{3} - 3mn + am + b) + i(3m^{2} \sqrt{n} - n\sqrt{n} + a\sqrt{n}) = 0$

Hence, $m^{3} - 3mn + am + b = 0$ and $3m^{2} \sqrt{n} - n\sqrt{n} + a\sqrt{n} = 0 \Rightarrow 3m^{2} - n + a = 0 \rightarrow (1)$

In the second equation, we get $(m + i \sqrt{n})^{3} + c(m + i \sqrt{n})^{2} + d = 0$ Simplifying this further, we get $(m^{3} + m^{2}c - nc - 3mn + d) + i(3m^{2} \sqrt{n} - n\sqrt{n} + 2mc\sqrt{n}) = 0$

Hence, $m^{3} + m^{2}c - nc - 3mn + d = 0$ and $3m^{2} \sqrt{n} - n\sqrt{n} + 2mc\sqrt{n} = 0 \Rightarrow 3m^{2} - n + 2mc = 0 \rightarrow (2)$

Comparing (1) and (2),

$a = 2mc$ and $am + b = m^{2}c - nc + d \rightarrow (3)$

$b = 8000 + 20a \Rightarrow b = 40mc + 8000$ ; $d = 9261 - 441c$

Substituting these in $(3)$ gives, $2m^{2}c + 8000 + 40mc = m^{2}c - nc + 9261 - 441c$

This simplifies to $m^{2}c + nc + 40mc + 441c = 1261 \Rightarrow c(m^{2} + n + 40m + 441) = 1261$

Hence, $c|1261 \Rightarrow c \in {1,13,97,1261}$

Consider case of $c = 1$ :

$c = 1 \Rightarrow d = 8820$ Also, $a = 2m, b = 8000 + 40m$

$am + b = m^{2} - n + 8820$ (because c = 1) Also, $m^{2} + n + 40m = 820 \rightarrow (4)$ Also, Equation (2) gives $3m^{2} - n + 2m = 0 \rightarrow (5)$

Solving (4) and (5) simultaneously gives $m = 10, n = 320$

[AIME can not have more than one answer, so we can stop here also 😁... Not suitable for Subjective exam]

Hence, $m + n = 10 + 320 = \boxed{330}$

-Arnav Nigam

Solution 3 (Heavy Calculation Solution)

start off by applying vieta's and you will find that $a=m^2+n-40m$ $b=20m^2+20n$ $c=21-2m$ and $d=21m^2+21n$ . After that, we have to use the fact that $-20$ and $-21$ are roots of $x^3+ax+b$ and $x^3+cx^2+d$ , respectively. Since we know that if you substitute the root of a function back into the function, the output is zero, therefore $(-20)^3-20(a)+b=0$ and $(-21)^3+c*(-21)^2+d=0$ and you can set these two equations equal to each other while also substituting the values of $a$ , $b$ , $c$ , and $d$ above to give you $21m^2+21n-1682m+8000=0$ , then you can rearrange the equation into $21n = -21m^2+1682m-8000$ . With this property, we know that $-21m^2+1682m-8000$ is divisible by $21$ therefore that means $1682m-8000=0(mod 21)$ which results in $2m-20=0(mod 21)$ which finally gives us m=10 mod 21. We can test the first obvious value of $m$ which is $10$ and we see that this works as we get $m=10$ and $n=320$ . That means your answer will be $m + n = 10 + 320 = \boxed{330}$

-Jske25

Solution 4 (Synthetic Division)

We note that $x^3 + ax + b = (x+20)P(x)$ and $x^3 + cx^2 + d = (x+21)Q(x)$ for some polynomials $P(x)$ and $Q(x)$ . Through synthetic division (ignoring the remainder as we can set $b$ and $d$ to constant values such that the remainder is zero), $P(x) = x^2 - 20x + (400+a)$ , and $Q(x) = x^2 + (c-21)x + (441 - 21c)$ By the complex conjugate root theorem, we know that $P(x)$ and $Q(x)$ share the same roots, and they share the same leading coefficient, so $P(x) = Q(x)$ . Therefore, $c-21 = -20$ and $441-21c = 400 + a$ . Solving the system equations, we get $a = 20$ and $c = 1$ , so $P(x) = Q(x) = x^2 - 20x + 420$ . Finally, by the quadratic formula, we have roots of $\frac{20 \pm \sqrt{400 - 1680}}{2} = 10 \pm \sqrt{320}i$ , so our final answer is $10 + 320 = \boxed{330}$

-faefeyfa

Solution 5 (Fast and Easy)

We plug -20 into the equation obtaining $(-20)^3-20a+b$ , likewise, plugging -21 into the second equation gets $(-21)^3+441c+d$ .

Both equations must have 3 solutions exactly, so the other two solutions must be $m + \sqrt{n} \cdot i$ and $m - \sqrt{n} \cdot i$ .

By Vieta's, the sum of the roots in the first equation is $0$ , so $m$ must be $10$ .

Next, using Vieta's theorem on the second equation, you get: $x1x2+x2x3+x1x3 = 0$ However, since we know that the sum of the roots with complex numbers are 20, we can factor out the terms with -21, so $-21*(20)+(m^2+n)=0$

Given that $m$ is $10$ , then $n$ is equal to $320$ .

Therefore, the answer to the equation is $\boxed{330}$

Problem 5

Solution 1

We start by defining a triangle. The two small sides MUST add to a larger sum than the long side. We are given 4 and 10 as the sides, so we know that the 3rd side is between 6 and 14, exclusive. We also have to consider the word OBTUSE triangles. That means that the two small sides squared is less than the 3rd side. So the triangles sides are between 6 and $\sqrt{84}$ exclusive, and the larger bound is between $\sqrt{116}$ and 14, exclusive. The area of these triangles are from 0 (straight line) to $2\sqrt{84}$ on the first "small bound" and the larger bound is between 0 and 20. $0 < s < 2\sqrt{84}$ is our first equation, and $0 < s < 20$ is our 2nd equation. Therefore, the area is between $\sqrt{336}$ and $\sqrt{400}$ , so our final answer is $\boxed{736}$ .

~ARCTICTURN

Solution 2 (Casework: Detailed Explanation of Solution 1)

If $a,b,$ and $c$ are the side-lengths of an obtuse triangle with $a\leq b\leq c,$ then both of the following must be satisfied:

Triangle Inequality Theorem: $a+b>c$

Pythagorean Inequality Theorem: $a^2+b^2<c^2$

For one such obtuse triangle, let $4,10,$ and $x$ be its side-lengths and $K$ be its area. By the Pythagorean Inequality Theorem, it is clear that $x\neq10.$ We apply casework to its longest side:

Case (1): The longest side has length $\boldsymbol{10,}$ so $\boldsymbol{0<x<10.}$

By the Triangle Inequality Theorem, we have $4+x>10,$ from which $x>6.$

By the Pythagorean Inequality Theorem, we have $4^2+x^2<10^2,$ from which $x<\sqrt{84}.$

Taking the intersection of these three inequalities produces $6<x<\sqrt{84}$ for this case.

At $x=6,$ the obtuse triangle degenerates into a straight line with area $K=0;$ at $x=\sqrt{84},$ the obtuse triangle degenerates into a right triangle with area $K=\frac12\cdot4\cdot\sqrt{84}=2\sqrt{84}.$ Together, we obtain $0<K<2\sqrt{84},$ or $K\in\left(0,2\sqrt{84}\right).$

Case (2): The longest side has length $\boldsymbol{x,}$ so $\boldsymbol{x>10.}$

By the Triangle Inequality Theorem, we have $4+10>x,$ from which $x<14.$

By the Pythagorean Inequality Theorem, we have $4^2+10^2<x^2,$ from which $x>\sqrt{116}.$

Taking the intersection of these three inequalities produces $\sqrt{116}<x<14$ for this case.

At $x=14,$ the obtuse triangle degenerates into a straight line with area $K=0;$ at $x=\sqrt{116},$ the obtuse triangle degenerates into a right triangle with area $K=\frac12\cdot4\cdot10=20.$ Together, we obtain $0<K<20,$ or $K\in\left(0,20\right).$

Answer

It is possible for non-congruent obtuse triangles to have the same area. Therefore, all such positive real numbers $s$ are in exactly one of $\left(0,2\sqrt{84}\right)$ or $\left(0,20\right).$ Taking the exclusive disjunction, the set of all such $s$ is $[a,b)=\left(0,2\sqrt{84}\right)\oplus\left(0,20\right)=\left[2\sqrt{84},20\right),$ from which $a^2+b^2=\boxed{736}.$

~MRENTHUSIASM

Solution 3

We have the diagram below.

$[asy] draw((0,0)--(1,2*sqrt(3))); draw((1,2*sqrt(3))--(10,0)); draw((10,0)--(0,0)); label("A",(0,0),SW); label("B",(1,2*sqrt(3)),N); label("C",(10,0),SE); label("$\theta$",(0,0),NE); label("$\alpha$",(1,2*sqrt(3)),SSE); label("$4$",(0,0)--(1,2*sqrt(3)),WNW); label("$10$",(0,0)--(10,0),S); [/asy]$

We proceed by taking cases on the angles that can be obtuse, and finding the ranges for $s$ that they yield .

If angle $\theta$ is obtuse, then we have that $s \in (0,20)$ . This is because $s=20$ is attained at $\theta = 90^{\circ}$ , and the area of the triangle is strictly decreasing as $\theta$ increases beyond $90^{\circ}$ . This can be observed from $s=\frac{1}{2}(4)(10)\sin\theta$ by noting that $\sin\theta$ is decreasing in $\theta \in (90^{\circ},180^{\circ})$ .

Then, we note that if $\alpha$ is obtuse, we have $s \in (0,4\sqrt{21})$ . This is because we get $x=\sqrt{10^2-4^2}=\sqrt{84}=2\sqrt{21}$ when $\alpha=90^{\circ}$ , yileding $s=4\sqrt{21}$ . Then, $s$ is decreasing as $\alpha$ increases by the same argument as before.

$\angle{ACB}$ cannot be obtuse since $AC>AB$ .

Now we have the intervals $s \in (0,20)$ and $s \in (0,4\sqrt{21})$ for the cases where $\theta$ and $\alpha$ are obtuse, respectively. We are looking for the $s$ that are in exactly one of these intervals, and because $4\sqrt{21}<20$ , the desired range is $s\in [4\sqrt{21},20)$ giving $a^2+b^2=\boxed{736}\Box$

Solution 4

Note: Archimedes15 Solution which I added an answer here are two cases. Either the $4$ and $10$ are around an obtuse angle or the $4$ and $10$ are around an acute triangle. If they are around the obtuse angle, the area of that triangle is $<20$ as we have $\frac{1}{2} \cdot 40 \cdot \sin{\alpha}$ and $\sin$ is at most $1$ . Note that for the other case, the side lengths around the obtuse angle must be $4$ and $x$ where we have $16+x^2 < 100 \rightarrow x < 2\sqrt{21}$ . Using the same logic as the other case, the area is at most $4\sqrt{21}$ . Square and add $4\sqrt{21}$ and $20$ to get the right answer $a^2+b^2= \boxed{736}\Box$

Problem 6

Solution 1

By PIE, $|A|+|B|-|A \cap B| = |A \cup B|$ , and after some algebra you see that we need $A \subseteq B$ or $B \subseteq A$ . WLOG $A\subseteq B$ , then for each element there are $3$ possibilities, either it is in both $A$ and $B$ , it is in $B$ but not $A$ , or it is in neither $A$ nor $B$ . This gives us $3^{5}$ possibilities, and we multiply by $2$ since it could have also been the other way around. Now we need to subtract the overlaps where $A=B$ , and this case has $2^{5}=32$ ways that could happen. It is $32$ because each number could be in the subset or it could not be in the subset. So the final answer is $2\cdot 3^5 - 2^5 = \boxed{454}$ .

~ math31415926535

Solution 2

We denote $\Omega = \left\{ 1 , 2 , 3 , 4 , 5 \right\}$ . We denote $X = A \cap B$ , $Y = A \backslash \left( A \cap B \right)$ , $Z = B \backslash \left( A \cap B \right)$ , $W = \Omega \backslash \left( A \cup B \right)$ .

Therefore, $X \cup Y \cup Z \cup W = \Omega$ and the intersection of any two out of sets $X$ , $Y$ , $Z$ , $W$ is an empty set. Therefore, $\left( X , Y , Z , W \right)$ is a partition of $\Omega$ .

Following from our definition of $X$ , $Y$ , $Z$ , we have $A \cup B = X \cup Y \cup Z$ .

Therefore, the equation

$|A| \cdot |B| = |A \cap B| \cdot |A \cup B|$

can be equivalently written as

$\left( | X | + | Y | \right) \left( | X | + | Z | \right) = | X | \left( | X | + | Y | + | Z | \right) .$

This equality can be simplified as

$| Y | \cdot | Z | = 0 .$

Therefore, we have the following three cases: (1) $|Y| = 0$ and $|Z| \neq 0$ , (2) $|Z| = 0$ and $|Y| \neq 0$ , (3) $|Y| = |Z| = 0$ . Next, we analyze each of these cases, separately.

Case 1: $|Y| = 0$ and $|Z| \neq 0$ .

In this case, to count the number of solutions, we do the complementary counting.

First, we count the number of solutions that satisfy $|Y| = 0$ .

Hence, each number in $\Omega$ falls into exactly one out of these three sets: $X$ , $Z$ , $W$ . Following from the rule of product, the number of solutions is $3^5$ .

Second, we count the number of solutions that satisfy $|Y| = 0$ and $|Z| = 0$ .

Hence, each number in $\Omega$ falls into exactly one out of these two sets: $X$ , $W$ . Following from the rule of product, the number of solutions is $2^5$ .

Therefore, following from the complementary counting, the number of solutions in this case is equal to the number of solutions that satisfy $|Y| = 0$ minus the number of solutions that satisfy $|Y| = 0$ and $|Z| = 0$ , i.e., $3^5 - 2^5$ .

Case 2: $|Z| = 0$ and $|Y| \neq 0$ .

This case is symmetric to Case 1. Therefore, the number of solutions in this case is the same as the number of solutions in Case 1, i.e., $3^5 - 2^5$ .

Case 3: $|Y| = 0$ and $|Z| = 0$ .

Recall that this is one part of our analysis in Case 1. Hence, the number solutions in this case is $2^5$ .

By putting all cases together, following from the rule of sum, the total number of solutions is equal to

$\begin{align*} \left( 3^5 - 2^5 \right) + \left( 3^5 - 2^5 \right) + 2^5 & = 2 \cdot 3^5 - 2^5 \\ & = \boxed{454} . \end{align*}$

~ Steven Chen (www.professorchenedu.com)

Solution 3 (Casework)

By the Principle of Inclusion-Exclusion (abbreviated as PIE), we have $|A \cup B|=|A|+|B|-|A \cap B|,$ from which we rewrite the given equation as $|A| \cdot |B| = |A \cap B| \cdot \left(|A|+|B|-|A \cap B|\right).$ Rearranging and applying Simon's Favorite Factoring Trick give $\begin{align*} |A| \cdot |B| &= |A \cap B|\cdot|A| + |A \cap B|\cdot|B| - |A \cap B|^2 \\ |A| \cdot |B| - |A \cap B|\cdot|A| - |A \cap B|\cdot|B| &= - |A \cap B|^2 \\ \left(|A| - |A \cap B|\right)\cdot\left(|B| - |A \cap B|\right) &=0, \end{align*}$ from which at least one of the following is true:

$|A|=|A \cap B|$

$|B|=|A \cap B|$

Let $|A \cap B|=k.$ For each value of $k\in\{0,1,2,3,4,5\},$ we will use PIE to count the ordered pairs $(A,B):$

Suppose $|A|=k.$ There are $\binom{5}{k}$ ways to choose the elements for $A.$ These $k$ elements must also appear in $B.$ Next, there are $2^{5-k}$ ways to add any number of the remaining $5-k$ elements to $B$ (Each element has $2$ options: in $B$ or not in $B.$ ). There are $\binom{5}{k}2^{5-k}$ ordered pairs for $|A|=k.$ Similarly, there are $\binom{5}{k}2^{5-k}$ ordered pairs for $|B|=k.$

To fix the overcount, we subtract the number of ordered pairs that are counted twice, in which $|A|=|B|=k.$ There are $\binom{5}{k}$ such ordered pairs.

Therefore, there are $2\binom{5}{k}2^{5-k}-\binom{5}{k}$ ordered pairs for $|A \cap B|=k.$

Two solutions follow from here:

Solution 3.1 (Binomial Theorem)

The answer is $\begin{align*} \sum_{k=0}^{5}\left[2\binom{5}{k}2^{5-k}-\binom{5}{k}\right] &= 2\underbrace{\sum_{k=0}^{5}\binom{5}{k}2^{5-k}}_{(2+1)^5}-\underbrace{\sum_{k=0}^{5}\binom{5}{k}}_{(1+1)^5} \\ &=2(243)-32 \\ &=\boxed{454}. \end{align*}$

Problem 7

Solution 1

From the fourth equation we get $d=\frac{30}{abc}.$ substitute this into the third equation and you get $abc + \frac{30(ab + bc + ca)}{abc} = abc - \frac{120}{abc} = 14$ . Hence $(abc)^2 - 14(abc)-120 = 0$ . Solving we get $abc = -6$ or $abc = 20$ . From the first and second equation we get $ab + bc + ca = ab-3c = -4 \Longrightarrow ab = 3c-4$ , if $abc=-6$ , substituting we get $c(3c-4)=-6$ . If you try solving this you see that this does not have real solutions in $c$ , so $abc$ must be $20$ . So $d=\frac{3}{2}$ . Since $c(3c-4)=20$ , $c=-2$ or $c=\frac{10}{3}$ . If $c=\frac{10}{3}$ , then the system $a+b=-3$ and $ab = 6$ does not give you real solutions. So $c=-2$ . Since you already know $d=\frac{3}{2}$ and $c=-2$ , so you can solve for $a$ and $b$ pretty easily and see that $a^{2}+b^{2}+c^{2}+d^{2}=\frac{141}{4}$ . So the answer is $\boxed{145}$ .

~ math31415926535

Solution 2 (Easy Algebra)

We can factor $d$ out of the last two equations. Therefore, it becomes $abc + d(bc + ac + ab) = 14$ . Notice this is just $abc -4d$ , since $bc + ac + ab = -4$ . We now have $abc -4d = 14$ and $abcd = 30$ . We then find $d$ in terms of $abc$ , so $abc = \frac{30}{d}-4d=14$ . We solve for $d$ and find that it is either $\dfrac32$ or $-5$ . We can now try for these two values, and plug the rest into the equation. Thus, we have $33 + \dfrac94 = \dfrac{33 \cdot 4 + 9}{4} = \dfrac{132+9}{4} = \dfrac{141}{4}$ . We have $141 + 4 = \boxed{145}$ and we're done.

~Arcticturn

Solution 3 (Easy and Straightforward Algebra)

$ab + bc + ca = -4$ can be rewritten as $ab + c(a+b) = -4$ . Hence, $ab = 3c - 4$

Rewriting $abc+bcd+cda+dab = 14$ , we get $ab(c+d) + cd(a+b) = 14$ . Substitute $ab = 3c - 4$ and solving, we get, $3c^{2} - 4c - 4d - 14 = 0$ call this Equation 1

$abcd = 30$ gives $(3c-4)cd = 30$ . So, $3c^{2}d - 4cd = 30$ , which implies $d(3c^{2} - 4c) = 30$ or $3c^{2} - 4c = \frac{30}{d}$ call this equation 2.

Substituting Eq 2 in Eq 1 gives, $\frac{30}{d} - 4d - 14 = 0$

Solving this quadratic yields that $d \in {-5, \frac{3}{2}}$

Now we just try these 2 cases.

For $d = \frac{3}{2}$ substituting in Equation 1 gives a quadratic in $c$ which has roots $c \in \frac{10}{3}, -2$

Again trying cases, by letting $c = -2$ , we get $ab = 3c-4$ , Hence $ab = -10$ We know that $a + b = -3$ , Solving these we get $a = -5, b = 2$ or $a= 2, b = -5$ (doesn't matter due to symmetry in a,b)

So, this case yields solutions $(a,b,c,d) = (-5, 2 , -2, \frac{3}{2})$

Similarly trying other three cases, we get no more solutions, Hence this is the solution for $(a,b,c,d)$

Finally, $a^{2} + b^{2} + c^{2} + d^{2} = 25 + 4 + 4 + \frac{9}{4} = \frac{141}{4} = \frac{m}{n}$

So, $m + n = 141 + 4 = \boxed{145}$

- Arnav Nigam

Solution 4 (Bash: Two Variables, Two Equations)

Number the given equations $(1),(2),(3),$ and $(4),$ in this order. Rearranging $(2)$ and solving for $c,$ we have $\begin{align*} ab+(a+b)c&=-4 \\ ab-3c&=-4 \\ c&=\frac{ab+4}{3}. \hspace{14mm} (5) \end{align*}$ Substituting $(5)$ into $(4)$ and solving for $d,$ we get $\begin{align*} ab\left(\frac{ab+4}{3}\right)d&=30 \\ d&=\frac{90}{ab(ab+4)}. \hspace{5mm} (6) \end{align*}$ Substituting $(5)$ and $(6)$ into $(3)$ and simplifying, we rewrite the left side of $(3)$ in terms of $a$ and $b$ only: $\begin{align*} ab\left[\frac{ab+4}{3}\right] + b\left[\frac{ab+4}{3}\right]\left[\frac{90}{ab(ab+4)}\right] + \left[\frac{ab+4}{3}\right]\left[\frac{90}{ab(ab+4)}\right]a + \left[\frac{90}{ab(ab+4)}\right]ab &= 14 \\ ab\left[\frac{ab+4}{3}\right] + \underbrace{\frac{30}{a} + \frac{30}{b}}_{\text{Group them.}} + \frac{90}{ab+4} &= 14 \\ ab\left[\frac{ab+4}{3}\right] + \frac{30(\phantom{ }\overbrace{a+b}^{-3}\phantom{ })}{ab} + \frac{90}{ab+4} &= 14 \\ ab\left[\frac{ab+4}{3}\right] + \underbrace{\frac{-90}{ab} + \frac{90}{ab+4}}_{\text{Group them.}} &= 14 \\ ab\left[\frac{ab+4}{3}\right] - \frac{360}{ab(ab+4)}&=14. \end{align*}$ Let $t=ab(ab+4),$ from which $\frac{t}{3}-\frac{360}{t}=14.$ Multiplying both sides by $3t,$ rearranging, and factoring give $(t+18)(t-60)=0.$ Substituting back and completing the squares produce $\begin{align*} \left[ab(ab+4)+18\right]\left[ab(ab+4)-60\right]&=0 \\ \left[(ab)^2+4ab+18\right]\left[(ab)^2+4ab-60\right]&=0 \\ \underbrace{\left[(ab+2)^2+14\right]}_{ab+2=\pm\sqrt{14}i\implies ab\not\in\mathbb R}\underbrace{\left[(ab+2)^2-64\right]}_{ab+2=\pm8}&=0 \\ ab&=6,-10. \end{align*}$ If $ab=6,$ then combining this with $(1),$ we know that $a$ and $b$ are the solutions of the quadratic $x^2+3x+6=0.$ Since the discriminant is negative, neither $a$ nor $b$ is a real number.

If $ab=-10,$ then combining this with $(1),$ we know that $a$ and $b$ are the solutions of the quadratic $x^2+3x-10=0,$ or $(x+5)(x-2)=0,$ from which $\{a,b\}=\{-5,2\}.$ Substituting $ab=-10$ into $(5)$ and $(6),$ we obtain $c=-2$ and $d=\frac32,$ respectively. Together, we have $a^2+b^2+c^2+d^2=\frac{141}{4},$ so the answer is $141+4=\boxed{145}.$

Problem 8

Solution 1 (Recursion)

For all positive integers $k,$ let

$N(k,\mathrm{BB})$ be the number of ways to make a sequence of exactly $k$ moves, where the last move is from the bottom face to the bottom face.

$N(k,\mathrm{BT})$ be the number of ways to make a sequence of exactly $k$ moves, where the last move is from the bottom face to the top face.

$N(k,\mathrm{TB})$ be the number of ways to make a sequence of exactly $k$ moves, where the last move is from the top face to the bottom face.

$N(k,\mathrm{TT})$ be the number of ways to make a sequence of exactly $k$ moves, where the last move is from the top face to the top face.

The base case occurs at $k=1,$ from which $\left(N(1,\mathrm{BB}),N(1,\mathrm{BT}),N(1,\mathrm{TB}),N(1,\mathrm{TT})\right)=(2,1,0,0).$

Suppose the ant makes exactly $k$ moves. We will perform casework on its last move:

1. If its last move is from the bottom face to the bottom face, then its next move has

1. - $1$ way to move from the bottom face to the bottom face.

1. - $1$ way to move from the bottom face to the top face.

1. If its last move is from the bottom face to the top face, then its next move has $2$ ways to move from the top face to the top face.

1. If its last move is from the top face to the bottom face, then its next move has $2$ ways to move from the bottom face to the bottom face.

If its last move is from the top face to the top face, then its next move has
- - $1$ way to move from the top face to the bottom face.
- - $1$ way to move from the top face to the top face.

Alternatively, this recursion argument is illustrated below, where each dashed arrow indicates $1$ way, and each solid arrow indicates $2$ ways: $[asy] /* Made by MRENTHUSIASM */ size(9cm); pair A, B, C, D, E, F, G, H, X, Y; A=(0,6); B=(0,4); C=(0,2); D=(0,0); E=(10,6); F=(10,4); G=(10,2); H=(10,0); X=(-1,8); Y=(11,8); label("BB", A, (-2,0)); label("BT", B, (-2,0)); label("TB", C, (-2,0)); label("TT", D, (-2,0)); label("BB", E, (2,0)); label("BT", F, (2,0)); label("TB", G, (2,0)); label("TT", H, (2,0)); label("\textbf{The \boldmath{$k$}th Move}", shift(0.3,0)*X); label("\textbf{The \boldmath{$(k+1)$}th Move}", shift(-0.3,-0.085)*Y); draw(A--E,0.8+black+dashed,EndArrow); draw(A--F,0.8+black+dashed,EndArrow); draw(B--H,0.8+black,EndArrow); draw(C--E,0.8+black,EndArrow); draw(D--G,0.8+black+dashed,EndArrow); draw(D--H,0.8+black+dashed,EndArrow); dot(A^^B^^C^^D^^E^^F^^G^^H, 5+black); [/asy]$ Therefore, we have the following relationships: $\begin{align*} N(1,\mathrm{BB})&=2, \\ N(1,\mathrm{BT})&=1, \\ N(1,\mathrm{TB})&=0, \\ N(1,\mathrm{TT})&=0, \\ N(k+1,\mathrm{BB})&=N(k,\mathrm{BB})+2\cdot N(k,\mathrm{TB}), \\ N(k+1,\mathrm{BT})&=N(k,\mathrm{BB}), \\ N(k+1,\mathrm{TB})&=N(k,\mathrm{TT}), \\ N(k+1,\mathrm{TT})&=N(k,\mathrm{TT})+2\cdot N(k,\mathrm{BT}). \end{align*}$ Using these equations, we recursively fill out the table below: $\begin{array}{c||c|c|c|c|c|c|c|c} \hspace{7mm}&\hspace{6.5mm}&\hspace{6.5mm}&\hspace{6.75mm}&\hspace{6.75mm}&\hspace{6.75mm}&\hspace{6.75mm}&& \\ [-2.5ex] \boldsymbol{k} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ \hline \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{BB})} &2&2&2&6&18&38&66&118 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{BT})} &1&2&2&2&6&18&38&66 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{TB})} &0&0&2&6&10&14&26&62 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{TT})} &0&2&6&10&14&26&62&138 \\ \hline \hline &&&&&&&& \\ [-2.25ex] \textbf{Total}&\boldsymbol{3}&\boldsymbol{6}&\boldsymbol{12}&\boldsymbol{24}&\boldsymbol{48}&\boldsymbol{96}&\boldsymbol{192}&\boldsymbol{384} \end{array}$ Clearly, there are $3\cdot2^{k-1}$ ways to make exactly $k$ moves. To guarantee correctness, note that for each value of $k,$ the four counts in that column must total up to $3\cdot2^{k-1}.$

Finally, the requested probability is $\frac{N(8,\mathrm{BT})+N(8,\mathrm{TT})}{N(8,\mathrm{BB})+N(8,\mathrm{BT})+N(8,\mathrm{TB})+N(8,\mathrm{TT})}=\frac{66+138}{118+66+62+138}=\frac{204}{384}=\frac{17}{32},$ from which the answer is $17+32=\boxed{049}.$

~Arcticturn (Fundamental Logic)

~MRENTHUSIASM (Reconstruction)

Solution 2 (Casework)

On each move, we can either stay on the level we previously were (stay on the bottom/top) or switch levels (go from top to bottom and vise versa). Since we start on the bottom, ending on the top means that we will have to switch an odd number of times; since we cannot switch twice in a row, over an eight-move period we can either make one or three switches. Furthermore, once we switch to a level we can choose one of two directions of traveling on that level: clockwise or counterclockwise (since we can't go back to our previous move, our first move on the level after switching determines our direction).

Case 1: one switch. Our one switch can either happen at the start/end of our moves, or in the middle. There are ways to do this, outlined below.
1. Subcase 1: switch happens at ends. If our first move is a switch, then there are two ways to determine the direction we travel along the top layer. Multiply by 2 to count for symmetry (last move is a switch) so this case yields $2^2 = 4$ possibilities.
2. Subcase 2: switch happens in the middle. There are six places for the switch to happen; the switch breaks the sequences of moves into two chains, with each having 2 ways to choose their direction of travel. This case yields $6 \cdot 2^2 = 24$ possibilities.
Case 2: three switches. Either two, one, or none of our switches occur at the start/end of our moves. There are ways to do this, outlined below. (Keep in mind we can't have two switches in a row.)
1. Subcase 1: start and end with a switch. Since our third switch can't be in moves 2 or 7, there are four ways to place our switch, breaking our sequence into two chains. This case yields $4 \cdot 2^2 = 16$ possibilities.
2. Subcase 2: one of our switches is at the start/end. WLOG our first move is a switch; moves 2 and 8 cannot be switches. We can choose 2 from any of the remaining 5 moves to be switches, but we have to subtract the 4 illegal cases where the two switches are in a row (3-4, 4-5, 5-6, 6-7). These three switches break our sequence into three chains; accounting for symmetry this case yields $2\left(\binom{5}{2} - 4\right) \cdot 2^3 = 96$ possibilities.
3. Subcase 3: all our switches are in the middle. We choose 3 from any of the 6 middle moves to be our switches, but have to subtract the cases where at least two of them are in a row. If at least two switches are in a row, there are five places for the group of 2 and four places for the third switch; however this overcounts the case where all three are in a row, which has 4 possibilities. These three switches break our sequence into four chains, so this case yields $\left(\binom{6}{3} - 5 \cdot 4 + 4\right) \cdot 2^4 = 64$ possibilities.

Our probability is then $\frac{176 + 28}{3 \cdot 2^7} = \frac{17}{32} \iff \boxed{049}$ .

Solution 3 (Faster Recursion)

Define $n_i$ to be the probability that after $i$ moves, the ant ends up on the level it started on (assuming the first move is a normal move where the ant can stay or move to the opposite level with half chance each). Note $n_0 = 1$ and $n_1 = \frac{1}{2}$ .

Consider when the ant has $i$ moves left. It can either stay on its current level with $\frac{1}{2}$ chance and $i - 1$ moves left, or travel to the opposite level with $\frac{1}{2}$ chance and $i - 2$ moves left (it must spend another move as it cannot travel back immediately). We then have the recurrence $n_i = \frac{1}{2}n_{i - 1} + \frac{1}{2}(1 - n_{i - 2})$

On the first move, the ant can stay on the bottom level with $\frac{2}{3}$ chance and $7$ moves left. Or, it can move to the top level with $\frac{1}{3}$ chance and $6$ moves left (it has to spend one on the top as it can not return immediately). So the requested probability is $P = \frac{2}{3}(1 - n_7) + \frac{1}{3}n_6$ .

Computing $n_i$ we get $n_6 = \frac{33}{64}$ and $n_7 = \frac{59}{128}$ , resulting in $P = \frac{17}{32} \iff \boxed{049}$ .

Problem 9

Solution 1

We make use of the (olympiad number theory) lemma that $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$ .

Noting $\gcd(2^m+1,2^m-1)=\gcd(2^m+1,2)=1$ , we have (by difference of squares) $\gcd(2^m+1,2^n-1) \neq 1 \iff \gcd(2^{2m}-1,2^n-1) \neq \gcd(2^m-1,2^n-1)$ $\iff 2^{\gcd(2m,n)}-1 \neq 2^{\gcd(m,n)}-1 \iff \gcd(2m,n) \neq \gcd(m,n) \iff \nu_2(m)<\nu_2(n).$ It is now easy to calculate the answer (with casework on $\nu_2(m)$ ) as $15 \cdot 15+8 \cdot 7+4 \cdot 3+2 \cdot 1=\boxed{295}$ .

~Lcz

Solution 2 (Comprehensive and Generalized)

Claim (Solution 1's Lemma)

If $u,a,$ and $b$ are positive integers with $u\geq2,$ then $\gcd\left(u^a-1,u^b-1\right)=u^{\gcd(a,b)}-1.$

There are two proofs to this claim, as shown below.

~MRENTHUSIASM

Proof 1 (Euclidean Algorithm)

If $a=b,$ then $\gcd(a,b)=a=b,$ from which the claim is clearly true.

Otherwise, let $a>b$ without the loss of generality. Note that for all integers $p>q>0,$ the Euclidean Algorithm states that $\gcd(p,q)=\gcd(p-q,q)=\cdots=\gcd(q,p \ \mathrm{ mod } \ q).$ We apply this result repeatedly to reduce the larger number: $\gcd\left(u^a-1,u^b-1\right)=\gcd\left(u^a-1-u^{a-b}\left(u^b-1\right),u^b-1\right)=\gcd\left(u^{a-b}-1,u^b-1\right).$ Continuing, we have $\begin{align*} \gcd\left(u^a-1,u^b-1\right)&=\cdots \\ &=\gcd\left(u^{a-b}-1,u^b-1\right) \\ &=\cdots \\ &=\gcd\left(u^{\gcd(a,b)}-1,u^{\gcd(a,b)}-1\right) \\ &=u^{\gcd(a,b)}-1, \end{align*}$ from which the proof is complete.

~MRENTHUSIASM

Proof 2 (Bézout's Identity)

Let $d=\gcd\left(u^a-1,u^b-1\right).$ It follows that $u^a\equiv1\pmod{d}$ and $u^b\equiv1\pmod{d}.$

By Bézout's Identity, there exist integers $x$ and $y$ for which $ax+by=\gcd(a,b),$ so $u^{\gcd(a,b)}=u^{ax+by}=\left(u^a\right)^x\left(u^b\right)^y\equiv1\pmod{d},$ from which $u^{\gcd(a,b)}-1\equiv0\pmod{d}.$ We know that $u^{\gcd(a,b)}-1\geq d.$

Next, we notice that $\begin{align*} u^a-1&=\left(u^{\gcd(a,b)}-1\right)\left(u^{a-\gcd{(a,b)}}+u^{a-2\gcd{(a,b)}}+u^{a-3\gcd{(a,b)}}+\cdots+1\right), \\ u^b-1&=\left(u^{\gcd(a,b)}-1\right)\left(u^{b-\gcd{(a,b)}}+u^{b-2\gcd{(a,b)}}+u^{b-3\gcd{(a,b)}}+\cdots+1\right). \end{align*}$ Since $u^{\gcd(a,b)}-1$ is a common divisor of $u^a-1$ and $u^b-1,$ we conclude that $u^{\gcd(a,b)}-1=d,$ from which the proof is complete.

~MRENTHUSIASM

Solution (Detailed Explanation of Solution 1)

By the Euclidean Algorithm, we have $\gcd\left(2^m+1,2^m-1\right)=\gcd\left(2^m-1,2\right)=1. \hspace{41.125mm} (*)$ We are given that $\gcd\left(2^m+1,2^n-1\right)>1.$ Multiplying both sides by $\gcd\left(2^m-1,2^n-1\right)$ gives $\begin{align*} \gcd\left(2^m+1,2^n-1\right)\cdot\gcd\left(2^m-1,2^n-1\right)&>\gcd\left(2^m-1,2^n-1\right) \hspace{5mm} (**) \\ \underbrace{\gcd\left(\left(2^m+1\right)\left(2^m-1\right),2^n-1\right)}_{\text{by }(*)\text{ and }\textbf{Remark (GCD Property)}}&>\gcd\left(2^m-1,2^n-1\right) \\ \gcd\left(2^{2m}-1,2^n-1\right)&>\gcd\left(2^m-1,2^n-1\right) \\ \underbrace{2^{\gcd(2m,n)}-1}_{\text{by }\textbf{Claim}}&>\underbrace{2^{\gcd(m,n)}-1}_{\text{by }\textbf{Claim}} \\ \gcd(2m,n)&>\gcd(m,n), \end{align*}$ which implies that $n$ must have more factors of $2$ than $m$ does.

We construct the following table for the first $30$ positive integers: $\begin{array}{c|c|c} && \\ [-2.5ex] \boldsymbol{\#}\textbf{ of Factors of }\boldsymbol{2} & \textbf{Numbers} & \textbf{Count} \\ \hline && \\ [-2.25ex] 0 & 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29 & 15 \\ && \\ [-2.25ex] 1 & 2,6,10,14,18,22,26,30 & 8 \\ && \\ [-2.25ex] 2 & 4,12,20,28 & 4 \\ && \\ [-2.25ex] 3 & 8,24 & 2 \\ && \\ [-2.25ex] 4 & 16 & 1 \\ \end{array}$ To count the ordered pairs $(m,n),$ we perform casework on the number of factors of $2$ that $m$ has:

1. If $m$ has $0$ factors of $2,$ then $m$ has $15$ options and $n$ has $8+4+2+1=15$ options. So, this case has $15\cdot15=225$ ordered pairs.

1. If $m$ has $1$ factor of $2,$ then $m$ has $8$ options and $n$ has $4+2+1=7$ options. So, this case has $8\cdot7=56$ ordered pairs.

1. If $m$ has $2$ factors of $2,$ then $m$ has $4$ options and $n$ has $2+1=3$ options. So, this case has $4\cdot3=12$ ordered pairs.

If $m$ has $3$ factors of $2,$ then $m$ has $2$ options and $n$ has $1$ option. So, this case has $2\cdot1=2$ ordered pairs.

Together, the answer is $225+56+12+2=\boxed{295}.$

~MRENTHUSIASM

Remark (GCD Property)

In $(**)$ of the solution, we use the following property of the greatest common divisor:

For positive integers $r,s,$ and $t,$ if $\gcd(r,s)=1,$ then $\gcd(r,t)\cdot\gcd(s,t)=\gcd(rs,t).$

As $r$ and $s$ are relatively prime (have no prime divisors in common), this property is intuitive.

Problem 10

Solution 1

The centers of the three spheres form a 49-49-72 triangle. Consider the points at which the plane is tangent to the two bigger spheres; the line segment connecting these two points should be parallel to the 72 side of this triangle. Take its midpoint $M$ , which is 36 away from the midpoint of the 72 side $A$ , and connect these two midpoints.

Now consider the point at which the plane is tangent to the small sphere, and connect $M$ with the small sphere's tangent point $B$ . Extend $MB$ through B until it hits the ray from $A$ through the center of the small sphere (convince yourself that these two intersect). Call this intersection $D$ , the center of the small sphere $C$ , we want to find $BD$ .

By Pythagorus AC= $\sqrt{49^2-36^2}=\sqrt{1105}$ , and we know $MB=36,BC=13$ . We know that $MB,BC$ must be parallel, using ratios we realize that $CD=\frac{13}{23}\sqrt{1105}$ . Apply Pythagorean theorem on triangle BCD; $BD=\frac{312}{23}$ , so 312 + 23 = $\boxed{335}$

-Ross Gao

Solution 2 (Coord Bash)

Let's try to see some symmetry. We can use a coordinate plane to plot where the circles are. The 2 large spheres are externally tangent, so we'll make them at 0, -36, 0 and 0, 36, 0. The center of the little sphere would be x, 0, and -23 since we don't know how much the little sphere will be "pushed" down. We use the 3D distance formula to find that x is -24 (since 24 wouldn't make sense). Now, we draw a line through the little sphere and the origin. It also intersects $\ell$ because of the symmetry we created.

$\ell$ lies on the plane too, so these 2 lines must intersect. The point at where it intersects is -24a, 0, and 23a. We can use the distance formula again to find that a = $\dfrac{36}{23}$ . Therefore, they intersect at $\left(-\dfrac{864}{23},0,-36\right)$ . Since the little circle's x coordinate is -24 and the intersection point's x coordinate is $\dfrac{864}{23}$ , we get $\dfrac{864}{23}$ - 24 = $\dfrac{312}{23}$ . Therefore, our answer to this problem is 312 + 23 = $\boxed{335}$ .

~Arcticturn

Solution 3 (Illustration of Solution 1)

This solution refers to the Diagram section.

As shown below, let $O_1,O_2,O_3$ be the centers of the spheres (where sphere $O_3$ is the smallest) and $T_1,T_2,T_3$ be their respective points of tangency to plane $\mathcal{P}.$ Suppose $A$ is the foot of the perpendicular from $O_3$ to line $\ell,$ so $\overleftrightarrow{O_3A}$ is the perpendicular bisector of $\overline{O_1O_2}.$ We wish to find $T_3A.$

As the intersection of planes $\mathcal{R}$ and $\mathcal{P}$ is line $\ell,$ we know that both $\overrightarrow{O_1O_3}$ and $\overrightarrow{T_1T_3}$ must intersect line $\ell.$ Furthermore, since $\overline{O_1T_1}\perp\mathcal{P}$ and $\overline{O_3T_3}\perp\mathcal{P},$ it follows that $\overline{O_1T_1}\parallel\overline{O_3T_3},$ from which $O_1,O_3,T_1,$ and $T_3$ are coplanar.

We will focus on cross-sections $O_1O_3T_3T_1$ and $\mathcal{R}:$

1. In the three-dimensional space, the intersection of a line and a plane must be exactly one of the empty set, a point, or a line.Clearly, cross-section $O_1O_3T_3T_1$ intersects line $\ell$ at exactly one point. Let the intersection of $\overrightarrow{O_1O_3}$ and line $\ell$ be $B,$ which must also be the intersection of $\overrightarrow{T_1T_3}$ and line $\ell.$
2. In cross-section $\mathcal{R},$ let $C$ be the foot of the perpendicular from $O_1$ to line $\ell,$ and $D$ be the foot of the perpendicular from $O_3$ to $\overline{O_1C}.$

We have the following diagram:

In cross-section $O_1O_3T_3T_1,$ since $\overline{O_1T_1}\parallel\overline{O_3T_3}$ as discussed, we obtain $\triangle O_1T_1B\sim\triangle O_3T_3B$ by AA, with the ratio of similitude $\frac{O_1T_1}{O_3T_3}=\frac{36}{13}.$ Therefore, we get $\frac{O_1B}{O_3B}=\frac{49+O_3B}{O_3B}=\frac{36}{13},$ or $O_3B=\frac{637}{23}.$

In cross-section $\mathcal{R},$ note that $O_1O_3=49$ and $DO_3=\frac{O_1O_2}{2}=36.$ Applying the Pythagorean Theorem to right $\triangle O_1DO_3,$ we have $O_1D=\sqrt{1105}.$ Moreover, since $\ell\perp\overline{O_1C}$ and $\overline{DO_3}\perp\overline{O_1C},$ we obtain $\ell\parallel\overline{DO_3}$ so that $\triangle O_1CB\sim\triangle O_1DO_3$ by AA, with the ratio of similitude $\frac{O_1B}{O_1O_3}=\frac{49+\frac{637}{23}}{49}.$ Therefore, we get $\frac{O_1C}{O_1D}=\frac{\sqrt{1105}+DC}{\sqrt{1105}}=\frac{49+\frac{637}{23}}{49},$ or $DC=\frac{13\sqrt{1105}}{23}.$

Finally, note that $\overline{O_3T_3}\perp\overline{T_3A}$ and $O_3T_3=13.$ Since $DCAO_3$ is a rectangle, we have $O_3A=DC=\frac{13\sqrt{1105}}{23}.$ Applying the Pythagorean Theorem to right $\triangle O_3T_3A$ gives $T_3A=\frac{312}{23},$ from which the answer is $312+23=\boxed{335}.$

Problem 11

Solution 1

Let's start by listing the multiples of 6 and 7: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96; 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, and 98. First of all, the multiples of 6 and 7 wouldn't work, so we can cross out 42 and 84. Since the students said they didn't know the answer, it must be that the set has no distinct integers from the sets. Let's list out the possible sets. Since they are in lists of 4, we need multiples of 6 or 7. Let's list them out. 11, 12, 13, 14 12, 13, 14, 15 But if a student has 11 or 15, they would know. So that wouldn't work. The second set would be this: $\{34,35,36,37\}$ $\{47,48,49,50\}$ $\{76,77,78,79\}$ $\{89,90,91,92\}$ They couldn't know since the multiples of 7 is 35, and if you list it out, they wouldn't know about it since there are other sets such as 35, 36, 37, 38, and 33, 34, 35, 36. The people with these sets would say no, so the second set would WORK. The other sets are only 2 numbers, and since 2 numbers are sufficiently smaller than our 2nd set, we have concluded the answer is 37+50+79+92 = $\boxed{258}$ . ~Arcticturn

Solution 2 (Illustrations)

Note that $\mathrm{lcm}(6,7)=42.$ It is clear that $42\not\in S$ and $84\not\in S,$ otherwise the three other elements in $S$ are divisible by neither $6$ nor $7.$

In the table below, the multiples of $6$ are colored in yellow, and the multiples of $7$ are colored in green. By the least common multiple, we obtain cycles: If $n$ is a possible maximum value of $S,$ then $n+42$ must be another possible maximum value of $S,$ and vice versa. By observations, we circle all possible maximum values of $S.$ $[asy] /* Made by MRENTHUSIASM */ size(20cm); fill((5,0)--(6,0)--(6,2)--(5,2)--cycle,yellow); fill((11,0)--(12,0)--(12,3)--(11,3)--cycle,yellow); fill((17,1)--(18,1)--(18,3)--(17,3)--cycle,yellow); fill((23,1)--(24,1)--(24,3)--(23,3)--cycle,yellow); fill((29,1)--(30,1)--(30,3)--(29,3)--cycle,yellow); fill((35,1)--(36,1)--(36,3)--(35,3)--cycle,yellow); fill((6,0)--(7,0)--(7,2)--(6,2)--cycle,green); fill((13,0)--(14,0)--(14,3)--(13,3)--cycle,green); fill((20,1)--(21,1)--(21,3)--(20,3)--cycle,green); fill((27,1)--(28,1)--(28,3)--(27,3)--cycle,green); fill((34,1)--(35,1)--(35,3)--(34,3)--cycle,green); fill((42,3)--(41,3)--(41,2)--cycle,yellow); fill((42,2)--(41,2)--(41,1)--cycle,yellow); fill((42,3)--(42,2)--(41,2)--cycle,green); fill((42,2)--(42,1)--(41,1)--cycle,green); for (real i=9.5; i<=41.5; ++i) { label("$"+string(i+0.5)+"$",(i,2.5),fontsize(9pt)); } for (real i=0.5; i<=41.5; ++i) { label("$"+string(i+42.5)+"$",(i,1.5),fontsize(9pt)); } for (real i=0.5; i<=14.5; ++i) { label("$"+string(i+84.5)+"$",(i,0.5),fontsize(9pt)); } draw(circle((6.5,1.5),0.45)); draw(circle((6.5,0.5),0.45)); draw(circle((7.5,1.5),0.45)); draw(circle((7.5,0.5),0.45)); draw(circle((8.5,1.5),0.45)); draw(circle((8.5,0.5),0.45)); draw(circle((13.5,2.5),0.45)); draw(circle((13.5,1.5),0.45)); draw(circle((13.5,0.5),0.45)); draw(circle((14.5,2.5),0.45)); draw(circle((14.5,1.5),0.45)); draw(circle((14.5,0.5),0.45)); draw(circle((20.5,2.5),0.45)); draw(circle((20.5,1.5),0.45)); draw(circle((23.5,2.5),0.45)); draw(circle((23.5,1.5),0.45)); draw(circle((29.5,2.5),0.45)); draw(circle((29.5,1.5),0.45)); draw(circle((30.5,2.5),0.45)); draw(circle((30.5,1.5),0.45)); draw(circle((35.5,2.5),0.45)); draw(circle((35.5,1.5),0.45)); draw(circle((36.5,2.5),0.45)); draw(circle((36.5,1.5),0.45)); draw(circle((37.5,2.5),0.45)); draw(circle((37.5,1.5),0.45)); draw((9,3)--(42,3)); draw((0,2)--(42,2)); draw((0,1)--(42,1)); draw((0,0)--(15,0)); for (real i=0; i<9; ++i) { draw((i,2)--(i,0)); } for (real i=9; i<16; ++i) { draw((i,3)--(i,0)); } for (real i=16; i<=42; ++i) { draw((i,3)--(i,1)); } [/asy]$ From the second row of the table above, we perform casework on the possible maximum value of $S:$ $\begin{array}{c||c|c|l} & & & \\ [-2.5ex] \textbf{Max Value} & \boldsymbol{S} & \textbf{Valid?} & \hspace{16.25mm}\textbf{Reasoning/Conclusion} \\ [0.5ex] \hline & & & \\ [-2ex] 49 & \{46,47,48,49\} & & \text{The student who gets } 46 \text{ will reply yes.} \\ 50 & \{47,48,49,50\} & \checkmark & \text{Another possibility is } S=\{89,90,91,92\}. \\ 51 & \{48,49,50,51\} & & \text{The student who gets } 51 \text{ will reply yes.} \\ 56 & \{53,54,55,56\} & & \text{The student who gets } 53 \text{ will reply yes.} \\ 57 & \{54,55,56,57\} & & \text{The student who gets } 57 \text{ will reply yes.} \\ 63 & \{60,61,62,63\} & & \text{The students who get } 60,61,62 \text{ will reply yes.} \\ 66 & \{63,64,65,66\} & & \text{The students who get } 64,65,66 \text{ will reply yes.} \\ 72 & \{69,70,71,72\} & & \text{The student who gets } 69 \text{ will reply yes.} \\ 73 & \{70,71,72,73\} & & \text{The student who gets } 73 \text{ will reply yes.} \\ 78 & \{75,76,77,78\} & & \text{The student who gets } 75 \text{ will reply yes.} \\ 79 & \{76,77,78,79\} & \checkmark & \text{Another possibility is } S=\{34,35,36,37\}. \\ 80 & \{77,78,79,80\} & & \text{The student who gets } 80 \text{ will reply yes.} \end{array}$ Finally, all possibilities for $S$ are $\{34,35,36,37\}, \{47,48,49,50\}, \{76,77,78,79\},$ and $\{89,90,91,92\},$ from which the answer is $37+50+79+92=\boxed{258}.$

Remarks

Alternatively, we can reconstruct the second table in this solution as follows, where Y and N denote the replies of "yes" and "no", respectively. Notice that this table has some kind of symmetry! $[asy] /* Made by MRENTHUSIASM */ size(20cm); for (real j=5.5; j<41.5; j+=6) { fill((j+0.5,4)--(j-0.5,4)--(j-0.5,3)--(j+0.5,3)--cycle,yellow); } for (real j=6.5; j<41.5; j+=7) { fill((j+0.5,4)--(j-0.5,4)--(j-0.5,3)--(j+0.5,3)--cycle,green); } fill((4,1)--(8,1)--(8,2)--(4,2)--cycle,mediumgray); fill((33,1)--(37,1)--(37,2)--(33,2)--cycle,mediumgray); fill((42,4)--(41,4)--(41,3)--cycle,yellow); fill((42,4)--(42,3)--(41,3)--cycle,green); for (real i=0.5; i<=41.5; ++i) { label("$"+string(i+42.5)+"$",(i,3.5),fontsize(9pt)); } draw(circle((6.5,3.5),0.45)); draw(circle((7.5,3.5),0.45)); draw(circle((8.5,3.5),0.45)); draw(circle((13.5,3.5),0.45)); draw(circle((14.5,3.5),0.45)); draw(circle((20.5,3.5),0.45)); draw(circle((23.5,3.5),0.45)); draw(circle((29.5,3.5),0.45)); draw(circle((30.5,3.5),0.45)); draw(circle((35.5,3.5),0.45)); draw(circle((36.5,3.5),0.45)); draw(circle((37.5,3.5),0.45)); label("Y",(3.5,2.5),blue); label("N",(4.5,2.5),blue); label("N",(5.5,2.5),blue); label("N",(6.5,2.5),blue); label("N",(4.5,1.5),blue); label("N",(5.5,1.5),blue); label("N",(6.5,1.5),blue); label("N",(7.5,1.5),blue); label("N",(5.5,0.5),blue); label("N",(6.5,0.5),blue); label("N",(7.5,0.5),blue); label("Y",(8.5,0.5),blue); label("Y",(10.5,2.5),blue); label("N",(11.5,2.5),blue); label("N",(12.5,2.5),blue); label("N",(13.5,2.5),blue); label("N",(11.5,1.5),blue); label("N",(12.5,1.5),blue); label("N",(13.5,1.5),blue); label("Y",(14.5,1.5),blue); label("Y",(17.5,2.5),blue); label("Y",(18.5,2.5),blue); label("Y",(19.5,2.5),blue); label("N",(20.5,2.5),blue); label("N",(20.5,1.5),blue); label("Y",(21.5,1.5),blue); label("Y",(22.5,1.5),blue); label("Y",(23.5,1.5),blue); label("Y",(26.5,2.5),blue); label("N",(27.5,2.5),blue); label("N",(28.5,2.5),blue); label("N",(29.5,2.5),blue); label("N",(27.5,1.5),blue); label("N",(28.5,1.5),blue); label("N",(29.5,1.5),blue); label("Y",(30.5,1.5),blue); label("Y",(32.5,2.5),blue); label("N",(33.5,2.5),blue); label("N",(34.5,2.5),blue); label("N",(35.5,2.5),blue); label("N",(33.5,1.5),blue); label("N",(34.5,1.5),blue); label("N",(35.5,1.5),blue); label("N",(36.5,1.5),blue); label("N",(34.5,0.5),blue); label("N",(35.5,0.5),blue); label("N",(36.5,0.5),blue); label("Y",(37.5,0.5),blue); for (real i=0; i<=42; ++i) { draw((i,4)--(i,3)); } draw((0,4)--(42,4)); draw((0,3)--(42,3)); [/asy]$
As a confirmation, we can verify that each student will be able to deduce what $S$ is upon hearing the four replies of "no" in unison. For example, if $S=\{47,48,49,50\},$ then all students will know that no one gets $46$ or $51,$ otherwise that student will reply yes (as discussed). Therefore, all students will conclude that $S$ has only one possibility.

Problem 12

Solution 1

We denote by $A$ , $B$ , $C$ and $D$ four vertices of this quadrilateral, such that $AB = 5$ , $BC = 6$ , $CD = 9$ , $DA = 7$ . We denote by $E$ the point that two diagonals $AC$ and $BD$ meet at. To simplify the notation, we denote $a = AE$ , $b = BE$ , $c = CE$ , $d = DE$ .

We denote $\theta = \angle AED$ . Hence, $\angle AEB = \angle CED = 180^\circ - \theta$ and $\angle BEC = \theta$ .

First, we use the triangle area formula with sines to write down an equation of the area of the quadrilateral $ABCD$ .

We have $\begin{align*} {\rm Area} \ ABCD & = {\rm Area} \ \triangle ABE + {\rm Area} \ \triangle BCE + {\rm Area} \ \triangle CDE + {\rm Area} \ \triangle DAE \\ & = \frac{1}{2} ab \sin \angle AEB + \frac{1}{2} bc \sin \angle BEC + \frac{1}{2} cd \sin \angle CED + \frac{1}{2} da \sin \angle DEA \\ & = \frac{1}{2} ab \sin \theta + \frac{1}{2} bc \sin \left( 180^\circ - \theta \right) + \frac{1}{2} cd \sin \theta + \frac{1}{2} da \sin \left( 180^\circ - \theta \right) \\ & = \frac{1}{2} ab \sin \theta + \frac{1}{2} bc \sin \theta + \frac{1}{2} cd \sin \theta + \frac{1}{2} da \sin \theta \\ & = \frac{1}{2} \left( ab + bc + cd + da \right) \sin \theta , \end{align*}$ where the second equality follows from the formula to use the sine function to compute a triangle area, the the fourth equality follows from the property that $\sin \left( 180^\circ - \theta \right) = \sin \theta$ .

Because ${\rm Area} \ ABCD = 30$ , we have $\left( ab + bc + cd + da \right) \sin \theta = 60 . \ \ \ (1)$ .

Second, we use the law of cosines to establish four equations for four sides of the quadrilateral $ABCD$ .

In $\triangle AEB$ , following from the law of cosines, we have $a^2 + b^2 - 2 a b \cos \angle AEB = AB^2 .$

Because $\cos \angle AEB = \cos \left( 180^\circ - \theta \right) = \cos \theta$ and $AB = 5$ , we have $a^2 + b^2 + 2 a b \cos \theta = 5^2 . \ \ \ (2)$

In $\triangle BEC$ , following from the law of cosines, we have $b^2 + c^2 - 2 b c \cos \angle BEC = BC^2 .$

Because $\cos \angle AEB = \cos \theta$ and $BC = 6$ , we have $b^2 + c^2 - 2 b c \cos \theta = 6^2 . \ \ \ (3)$

In $\triangle CED$ , following from the law of cosines, we have $c^2 + d^2 - 2 c d \cos \angle CED = CD^2 .$

Because $\cos \angle CED = \cos \left( 180^\circ - \theta \right) = \cos \theta$ and $CD = 9$ , we have $c^2 + d^2 + 2 c d \cos \theta = 9^2 . \ \ \ (4)$

In $\triangle DEA$ , following from the law of cosines, we have $d^2 + a^2 - 2 d a \cos \angle DEA = DA^2 .$

Because $\cos \angle DEC = \cos \theta$ and $DA = 7$ , we have $d^2 + a^2 - 2 d a \cos \theta = 7^2 . \ \ \ (5)$

By taking $\frac{1}{2} \left( {\rm Eq} \ (2) - {\rm Eq} \ (3) + {\rm Eq} \ (4) - {\rm Eq} \ (5) \right)$ , we get

$\left( ab + bc + cd + da \right) \cos \theta = \frac{21}{2} . \ \ \ (6)$

By taking $\frac{{\rm Eq} \ (1)}{{\rm Eq} \ (6)}$ , we get $\tan \theta = \frac{60}{21/2} = \frac{40}{7} .$

Therefore, by writing this answer in the form of $\frac{m}{n}$ , we have $m = 40$ and $n = 7$ . Therefore, the answer to this question is $m + n = 40 + 7 = \boxed{047}$ .

~ Steven Chen (www.professorchenedu.com)

Solution 2

Since we are asked to find $\tan \theta$ , we can find $\sin \theta$ and $\cos \theta$ separately and use their values to get $\tan \theta$ . We can start by drawing a diagram. Let the vertices of the quadrilateral be $A$ , $B$ , $C$ , and $D$ . Let $AB = 5$ , $BC = 6$ , $CD = 9$ , and $DA = 7$ . Let $AX = a$ , $BX = b$ , $CX = c$ , and $DX = d$ . We know that $\theta$ is the acute angle formed between the intersection of the diagonals $AC$ and $BD$ .

$[asy] unitsize(4cm); pair A,B,C,D,X; A = (0,0); B = (1,0); C = (1.25,-1); D = (-0.75,-0.75); draw(A--B--C--D--cycle,black+1bp); X = intersectionpoint(A--C,B--D); draw(A--C); draw(B--D); label("$A$",A,NW); label("$B$",B,NE); label("$C$",C,SE); label("$D$",D,SW); dot(X); label("$X$",X,S); label("$5$",(A+B)/2,N); label("$6$",(B+C)/2,E); label("$9$",(C+D)/2,S); label("$7$",(D+A)/2,W); label("$\theta$",X,2.5E); label("$a$",(A+X)/2,NE); label("$b$",(B+X)/2,NW); label("$c$",(C+X)/2,SW); label("$d$",(D+X)/2,SE); [/asy]$

We are given that the area of quadrilateral $ABCD$ is $30$ . We can express this area using the areas of triangles $AXB$ , $BXC$ , $CXD$ , and $DXA$ . Since we want to find $\sin \theta$ and $\cos \theta$ , we can represent these areas using $\sin \theta$ as follows:

$\begin{align*} 30 &=[ABCD] \\ &=[AXB] + [BXC] + [CXD] + [DXA] \\ &=\frac{1}{2} ab \sin (\angle AXB) + \frac{1}{2} bc \sin (\angle BXC) + \frac{1}{2} cd \sin (\angle CXD) + \frac{1}{2} da \sin (\angle AXD) \\ &=\frac{1}{2} ab \sin (180^\circ - \theta) + \frac{1}{2} bc \sin (\theta) + \frac{1}{2} cd \sin (180^\circ - \theta) + \frac{1}{2} da \sin (\theta) \end{align*}$

We know that $\sin (180^\circ - \theta) = \sin \theta$ . Therefore it follows that:

$\begin{align*} 30 &=\frac{1}{2} ab \sin (180^\circ - \theta) + \frac{1}{2} bc \sin (\theta) + \frac{1}{2} cd \sin (180^\circ - \theta) + \frac{1}{2} da \sin (\theta) \\ &=\frac{1}{2} ab \sin (\theta) + \frac{1}{2} bc \sin (\theta) + \frac{1}{2} cd \sin (\theta) + \frac{1}{2} da \sin (\theta) \\ &=\frac{1}{2}\sin\theta (ab + bc + cd + da) \end{align*}$

From here we see that $\sin \theta = \frac{60}{ab + bc + cd + da}$ . Now we need to find $\cos \theta$ . Using the Law of Cosines on each of the four smaller triangles, we get following equations:

$\begin{align*} 5^2 &= a^2 + b^2 - 2ab\cos(180^\circ-\theta) \\ 6^2 &= b^2 + c^2 - 2bc\cos \theta \\ 9^2 &= c^2 + d^2 - 2cd\cos(180^\circ-\theta) \\ 7^2 &= d^2 + a^2 - 2da\cos \theta \end{align*}$

We know that $\cos (180^\circ - \theta) = -\cos \theta$ . We can substitute this value into our equations to get:

$\begin{align*} 5^2 &= a^2 + b^2 + 2ab\cos \theta \\ 6^2 &= b^2 + c^2 - 2bc\cos \theta \\ 9^2 &= c^2 + d^2 + 2cd\cos \theta \\ 7^2 &= d^2 + a^2 - 2da\cos \theta \end{align*}$

If we subtract the sum of the first and third equation from the sum of the second and fourth equation, the squared terms cancel, leaving us with: $5^2 + 9^2 - 6^2 - 7^2 = 2ab \cos \theta + 2bc \cos \theta + 2cd \cos \theta + 2da \cos \theta$ $21 = 2\cos \theta (ab + bc + cd + da)$

From here we see that $\cos \theta = \frac{21/2}{ab + bc + cd + da}$ .

Since we have figured out $\sin \theta$ and $\cos \theta$ , we can calculate $\tan \theta$ :

$\tan \theta = \frac{\sin \theta}{\cos \theta} = \frac{\frac{60}{ab + bc + cd + da}}{\frac{21/2}{ab + bc + cd + da}} = \frac{60}{21/2} = \frac{120}{21} = \frac{40}{7}$

Therefore our answer is $40 + 7 = \boxed{047}$ .

Problem 13

Solution 1

1000 divides this expression iff 8, 125 both divide it. It should be fairly obvious that $n \geq 3$ ; so we may break up the initial condition into two sub-conditions.

(1) $5^n \equiv n \pmod{8}$ . Notice that the square of any odd integer is 1 modulo 8 (proof by plugging in $1^2$ , $3^2$ , $5^2$ , $7^2$ into modulo 8), so the LHS of this expression goes "5,1,5,1, ...", while the RHS goes "1,2,3,4,5,6,7,8,1, ...". The cycle length of the LHS is 2, RHS is 8, so the cycle length of the solution is $lcm(2,8)=8$ . Indeed, the n that solve this equation are exactly those such that $n \equiv 5 \pmod{8}$ .

(2) $2^n \equiv n \pmod{125}$ . This is extremely computationally intensive if you try to calculate all $2^1,2^2, ..., 2^{100} \pmod{125}$ , so instead, we take a divide-and-conquer approach. In order for this expression to be true $2^n \equiv n \pmod{5}$ is necessary; it shouldn't take too long for you to go through the 20 possible LHS-RHS combinations and convince yourself that $n \equiv 3 \pmod{20}$ or $n \equiv 17 \pmod{20}$ .

With this in mind we consider $2^n \equiv n$ modulo 25. By the generalized Fermat's little theorem, $2^{20} \equiv 1 \pmod{25}$ , but we already have n modulo 20! Our calculation is greatly simplified. The LHS cycle length is 20, RHS cycle length is 25, the lcm is 100, in this step we need to test all the numbers between 1 to 100 that $n \equiv 3 \pmod{20}$ or $n \equiv 17 \pmod{20}$ . In the case that $n \equiv 3 \pmod{20}$ , $2^n \equiv 2^3 \equiv 8$ , and RHS goes "3,23,43,63,83"; clearly $n \equiv 83 \pmod{100}$ . In the case that $n \equiv 17 \pmod{20}$ , by a similar argument, $n \equiv 97 \pmod{100}$ .

In the final step, we need to calculate $2^{97}, 2^{83}$ modulo 125. The former is simply $2^{-3}$ ; because $8*47=376=1$ modulo 125, $2^{97} \equiv 47$ . $2^{83}$ is $2^{-17}=2^{-16}*2^{-1}$ . $\begin{align*} 2^{-1}&=63, \\ 2^{-2}&=63^2=3969=-31, \\ 2^{-4}&=(-31)^2=961=-39, \\ 2^{-8}&=1521=21, \\ 2^{-16}&=441, \\ 2^{-17}&=63*441=7*{-31}=-217=33. \end{align*}$ This time, LHS cycle is 100, RHS cycle is 125, so we need to figure out what is n modulo 500. It should be $n \equiv 283,297 \pmod{500}$ .

Put everything together. By the second subcondition, the only candidates < 100 are $283,297,782,797$ . Apply the first subcondition, n=797 is the desired answer.

-Ross Gao

Solution 2

We have that $2^n + 5^n \equiv n\pmod{1000}$ , or $2^n + 5^n \equiv n \pmod{8}$ and $2^n + 5^n \equiv n \pmod{125}$ by CRT. It is easy to check $n < 3$ don't work, so we have that $n \geq 3$ . Then, $2^n \equiv 0 \pmod{8}$ and $5^n \equiv 0 \pmod{125}$ , so we just have $5^n \equiv n \pmod{8}$ and $2^n \equiv n \pmod{125}$ . Let us consider both of these congruences separately.

First, we look at $5^n \equiv n \pmod{8}$ . By Euler's Totient Theorem (ETT), we have $5^4 \equiv 1 \pmod{8}$ , so $5^5 \equiv 5 \pmod{8}$ . On the RHS of the congruence, the possible values of $n$ are all nonnegative integers less than $8$ and on the RHS the only possible values are $5$ and $1$ . However, for $5^n$ to be $1 \pmod{8}$ we must have $n \equiv 0 \pmod{4}$ , a contradiction. So, the only possible values of $n$ are when $n \equiv 5 \pmod{8} \implies n = 8k+5$ .

Now we look at $2^n \equiv n \pmod{125}$ . Plugging in $n = 8k+5$ , we get $2^{8k+5} \equiv 8k+5 \pmod{125} \implies 2^{8k} \cdot 32 \equiv 8k+5 \pmod{125}$ . Note, for $2^n \equiv n\pmod{125}$ to be satisfied, we must have $2^n \equiv n \pmod{5}$ and $2^n \equiv n\pmod{25}$ . Since $2^{8k} \equiv 1\pmod{5}$ as $8k \equiv 0\pmod{4}$ , we have $2 \equiv -2k \pmod{5} \implies k = 5m-1$ . Then, $n = 8(5m-1) + 5 = 40m-3$ . Now, we get $2^{40m-3} \equiv 40m-3 \pmod{125}$ . Using the fact that $2^n \equiv n\pmod{25}$ , we get $2^{-3} \equiv 15m-3 \pmod{25}$ . The inverse of $2$ modulo $25$ is obviously $13$ , so $2^{-3} \equiv 13^3 \equiv 22 \pmod{25}$ , so $15m \equiv 0 \pmod{25} \implies m = 5s$ . Plugging in $m = 5s$ , we get $n = 200s - 3$ .

Now, we are finally ready to plug $n$ into the congruence modulo $125$ . Plugging in, we get $2^{200s-3} \equiv 200s - 3 \pmod{125}$ . By ETT, we get $2^{100} \equiv 1 \pmod{125}$ , so $2^{200s- 3} \equiv 2^{-3} \equiv 47 \pmod{125}$ . Then, $200s \equiv 50 \pmod{125} \implies s \equiv 4 \pmod{5} \implies s = 5y+4$ . Plugging this in, we get $n = 200(5y+4) - 3 = 1000y+797$ , implying the smallest value of $n$ is simply $\boxed{797}$ . ~rocketsri

Solution 3 (Chinese Remainder Theorem and Binomial Theorem)

We wish to find the least positive integer $n$ for which $2^n+5^n-n\equiv0\pmod{1000}.$ Rearranging gives $2^n+5^n\equiv n\pmod{1000}.$ Applying the Chinese Remainder Theorem, we get the following systems of linear congruences: $\begin{align*} 2^n+5^n &\equiv n \pmod{8}, \\ 2^n+5^n &\equiv n \pmod{125}. \end{align*}$ It is clear that $n\geq3,$ from which we simplify to $\begin{align*} 5^n &\equiv n \pmod{8}, \hspace{15mm} &(1) \\ 2^n &\equiv n \pmod{125}. &(2) \end{align*}$

1. For $(1),$ quick inspections produce that $5^1,5^2,5^3,5^4,\cdots$ are congruent to $5,1,5,1,\cdots$ modulo $8,$ respectively. More generally, $5^n \equiv 5 \pmod{8}$ if $n$ is odd, and $5^n \equiv 1 \pmod{8}$ if $n$ is even. As $5^n$ is always odd (so is $n$ ), we must have $n\equiv5\pmod{8}.$ That is, $\boldsymbol{n=8r+5}$ for some nonnegative integer $\boldsymbol{r.}$

1. For $(2),$ we substitute the result from $(1)$ and simplify:

$\begin{align*} 2^{8r+5}&\equiv8r+5\pmod{125} \\ \left(2^8\right)^r\cdot2^5&\equiv8r+5\pmod{125} \\ 256^r\cdot32&\equiv8r+5\pmod{125} \\ 6^r\cdot32&\equiv8r+5\pmod{125}. \end{align*}$ Note that $5^3=125$ and $6=5+1,$ so we apply the Binomial Theorem to the left side: $\begin{align*} (5+1)^r\cdot32&\equiv8r+5&&\pmod{125} \\ \Biggl[\binom{r}{0}5^0+\binom{r}{1}5^1+\binom{r}{2}5^2+\phantom{ }\underbrace{\binom{r}{3}5^3+\cdots+\binom{r}{r}5^r}_{0\pmod{125}}\phantom{ }\Biggr]\cdot32&\equiv8r+5&&\pmod{125} \\ \left[1+5r+\frac{25r(r-1)}{2}\right]\cdot32&\equiv8r+5&&\pmod{125} \\ 32+160r+400r(r-1)&\equiv8r+5&&\pmod{125} \\ 32+35r+25r(r-1)&\equiv8r+5&&\pmod{125} \\ 25r^2+2r+27&\equiv0&&\pmod{125}. \hspace{15mm} (*) \end{align*}$ Since $125\equiv0\pmod{5},$ it follows that $\begin{align*} 25r^2+2r+27&\equiv0\pmod{5} \\ 2r+2&\equiv0\pmod{5} \\ r&\equiv4\pmod{5}. \end{align*}$

That is, $\boldsymbol{r=5s+4}$ for some nonnegative integer $\boldsymbol{s.}$

Substituting this back into $(*),$ we get $\begin{align*} 25(5s+4)^2+2(5s+4)+27&\equiv0\pmod{125} \\ 625s^2+1010s+435&\equiv0\pmod{125} \\ 10s+60&\equiv0\pmod{125} \\ 10(s+6)&\equiv0\pmod{125}. \end{align*}$ As $10(s+6)$ is a multiple of $125,$ it has at least three factors of $5.$ Since $10$ contributes one factor, it follows that $s+6$ contributes at least two factors, or $s+6$ must be a multiple of $25.$ Therefore, the least such nonnegative integer $s$ is $19.$

Finally, combining the two results from above (bolded) generates the least such positive integer $n$ at $s=19:$ $\begin{align*} n&=8r+5 \\ &=8(5s+4)+5 \\ &=40s+37 \\ &=\boxed{797}. \end{align*}$

Problem 14

Solution 1

Let $M$ be the midpoint of $BC$ . Because $\angle{OAX}=\angle{OGX}=\angle{OGY}=\angle{OMY}=90^o$ , $AXOG$ and $OMYG$ are cyclic, so $O$ is the center of the spiral similarity sending $AM$ to $XY$ , and $\angle{XOY}=\angle{AOM}$ . Because $\angle{AOM}=2\angle{BCA}+\angle{BAC}$ , it's easy to get $\frac{585}{7} \implies \boxed{592}$ from here.

~Lcz

Solution 2

Let $M$ be the midpoint of $BC$ . Because $\angle OAX = \angle OGX = 90$ we have $AXOG$ cyclic and so $\angle GXO = \angle OAG$ ; likewise since $\angle OMY = \angle OGY = 90$ we have $OMYG$ cyclic and so $\angle OYG = \angle OMG$ . Now note that $A, G, M$ are collinear since $\overline{AM}$ is a median, so $\triangle AOM \sim \triangle XOY$ . But $\angle AOM = \angle AOB + \angle BOM = 2 \angle C + \angle A$ . Now letting $\angle C = 2k, \angle B = 13k, \angle AOM = \angle XOY = 17k$ we have $\angle A = 13k$ and so $\angle A = \frac{585}{7} \implies \boxed{592}$ .

Guessing Solution for last 3 minutes (unreliable)

Notice that $\triangle ABC$ looks isosceles, so we assume it's isosceles. Then, let $\angle BAC = \angle ABC = 13x$ and $\angle BCA = 2x.$ Taking the sum of the angles in the triangle gives $28x=180,$ so $13x = \frac{13}{28} \cdot 180 = \frac{585}{7}$ so the answer is $\boxed{592}.$

Problem 15

Solution

Consider what happens when we try to calculate $f(n)$ where n is not a square. If $k^2<n<(k+1)^2$ for (positive) integer k, recursively calculating the value of the function gives us $f(n)=(k+1)^2-n+f((k+1)^2)=k^2+3k+2-n$ . Note that this formula also returns the correct value when $n=(k+1)^2$ , but not when $n=k^2$ . Thus $f(n)=k^2+3k+2-n$ for $k^2<n \leq (k+1)^2$ .

If $2 \mid (k+1)^2-n$ , $g(n)$ returns the same value as $f(n)$ . This is because the recursion once again stops at $(k+1)^2$ . We seek a case in which $f(n)<g(n)$ , so obviously this is not what we want. We want $(k+1)^2,n$ to have a different parity, or $n, k$ have the same parity. When this is the case, $g(n)$ instead returns $(k+2)^2-n+g((k+2)^2)=k^2+5k+6-n$ .

Write $7f(n)=4g(n)$ , which simplifies to $3k^2+k-10=3n$ . Notice that we want the $LHS$ expression to be divisible by 3; as a result, $k \equiv 1 \pmod{3}$ . We also want n to be strictly greater than $k^2$ , so $k-10>0, k>10$ . The LHS expression is always even (why?), so to ensure that k and n share the same parity, k should be even. Then the least k that satisfies these requirements is $k=16$ , giving $n=258$ .