Answer: 59

Small Hint:

Place $A = (0, 0)$ and $B = (9, 0)$ and find $C$ and $D;$ the two triangles are mirror images across the perpendicular bisector of $\overline{AB}$

Big Hint:

The overlap is the triangle with base $\overline{AB}$ whose apex is the point where segments $\overline{AC}$ and $\overline{BD}$ cross

Solution:

Place $A = (0, 0)$ and $B = (9, 0).$ From $CA = 17$ and $BC = 10,$ solving $x^2 + y^2 = 289$ and $(x - 9)^2 + y^2 = 100$ gives $C = (15, 8).$ The congruence $\triangle ABC \cong \triangle BAD$ swaps $A$ and $B,$ so $D$ is the reflection of $C$ across the line $x = \frac{9}{2},$ namely $D = (-6, 8).$

A point lies in triangle $ABC$ exactly when it is on or above $\overline{AB},$ on $B$’s side of line $AC,$ and on $A$’s side of line $BC;$ similarly for triangle $BAD.$ In the overlap the binding constraints are $y \ge 0,$ line $AC,$ and line $BD,$ so the intersection is the triangle with base $\overline{AB}$ and apex $E = AC \cap BD.$ Line $AC$ is $y = \frac{8x}{15}$ and line $BD$ is $y = -\frac{8(x - 9)}{15},$ which meet at $E = \left(\frac{9}{2}, \frac{12}{5}\right).$

The area is $$\frac{1}{2} \cdot 9 \cdot \frac{12}{5} = \frac{54}{5},$$ so $m + n = 54 + 5 = 59.$

Answer: 107

Small Hint:

Let $p_k$ be the probability that the frog ever lands on pad $k;$ the frog can only arrive there from pad $k - 1$ or pad $k - 2$

Big Hint:

$p_k = \frac{1}{2}p_{k-1} + \frac{1}{2}p_{k-2}$ with $p_1 = 1$ and $p_2 = \frac{1}{2};$ iterate up to $k = 7$

Solution:

Let $p_k$ be the probability that the frog visits pad $k.$ The frog lands on pad $k$ in exactly one of two disjoint ways: it visits pad $k - 1$ and jumps $+1$ from there (if it jumps $+2,$ pad $k$ is skipped forever), or it skips pad $k - 1$ entirely, which requires visiting pad $k - 2$ and jumping $+2$ from it, landing on pad $k.$ Hence $$\begin{aligned} &p_k = \tfrac{1}{2}p_{k-1} + \tfrac{1}{2}p_{k-2}, \\ &\qquad p_1 = 1, \quad p_2 = \tfrac{1}{2}. \end{aligned}$$

Iterating: $p_3 = \frac{3}{4},$ $p_4 = \frac{5}{8},$ $p_5 = \frac{11}{16},$ $p_6 = \frac{21}{32},$ and $p_7 = \frac{43}{64}.$ Since $\gcd(43, 64) = 1,$ the answer is $43 + 64 = 107.$

Answer: 96

Small Hint:

$71$ is prime, and $c$ must divide $70$ while $e$ must divide $72$

Big Hint:

With $d = 71$ and $c = e = 1,$ count the ordered pairs with $ab = 70$ and $fg = 72$ using divisor counts

Solution:

Since $71$ is prime, in $cde = 71$ one of the three factors is $71$ and the other two equal $1.$ But $c$ divides $abc = 70$ and $e$ divides $efg = 72,$ and $71$ divides neither $70$ nor $72.$ So $c = e = 1$ and $d = 71.$

The system reduces to $ab = 70$ and $fg = 72.$ Each divisor $a$ of $70$ determines $b,$ giving $\tau(70) = 8$ ordered pairs, and likewise $\tau(72) = 12$ ordered pairs $(f, g).$ The total is $8 \cdot 12 = 96.$

Answer: 187

Small Hint:

The product is a square exactly when each of the primes $2,$ $3,$ $5$ appears to an even power; only rolls of $5$ contribute the prime $5$

Big Hint:

Case on the number of $5$s (it must be even), then track the parities of the counts of $2$s, $3$s, and $6$s among the other rolls

Solution:

The product is a perfect square exactly when each of the primes $2,$ $3,$ and $5$ appears with even exponent. Only a roll of $5$ contributes the prime $5,$ so the number of $5$s is even: $0,$ $2,$ or $4.$ Classify the other values by the parities of their exponents of $2$ and $3:$ rolls of $1$ and $4$ contribute $(0, 0),$ a $2$ contributes $(1, 0),$ a $3$ contributes $(0, 1),$ and a $6$ contributes $(1, 1).$ The exponent of $2$ is even iff the count of $2$s plus the count of $6$s is even, and similarly for $3$s and $6$s, so a collection of non-$5$ rolls works exactly when the counts of $2$s, $3$s, and $6$s are all even or all odd.

With no $5$s, all four rolls come from $\{1, 2, 3, 4, 6\}.$ All-even cases: no $2$s, $3$s, or $6$s gives $2^4 = 16$ sequences (each roll is $1$ or $4$); exactly two of a single kind gives $3 \cdot \frac{4!}{2!\,2!} \cdot 2^2 = 72;$ two of each of two kinds gives $3 \cdot \frac{4!}{2!\,2!} = 18;$ four of one kind gives $3.$ All-odd case: one $2,$ one $3,$ one $6,$ and one roll from $\{1, 4\}$ gives $4! \cdot 2 = 48.$ Subtotal $16 + 72 + 18 + 3 + 48 = 157.$ With two $5$s, choose their positions in $\binom{4}{2} = 6$ ways; the other two rolls must lie in the same parity class, giving $2^2 + 1 + 1 + 1 = 7$ ordered pairs, for $42$ sequences. With four $5$s there is $1$ sequence.

In total $157 + 42 + 1 = 200$ of the $6^4 = 1296$ sequences work, so the probability is $\frac{200}{1296} = \frac{25}{162},$ and $m + n = 25 + 162 = 187.$

Answer: 520

Small Hint:

The six even chairs form a cycle, and each odd chair sits between two consecutive even chairs; each occupied even chair must claim one of its two flanking odd chairs, all distinct

Big Hint:

A block of $k$ consecutive occupied even chairs has $k + 1$ valid claim patterns; case on how the two empty even chairs split the cycle of six

Solution:

The six even chairs form a cycle (chair $12$ is adjacent to chair $1$), and each odd chair lies between two consecutive even chairs. The ambassadors occupy $4$ of the $6$ even chairs, and each advisor must take one of the two odd chairs flanking their ambassador, with all choices distinct. For a maximal block of $k$ consecutive occupied even chairs, the $k$ occupants choose among the $k + 1$ odd chairs touching the block; recording each choice as left or right, a conflict occurs exactly when someone picks right and their neighbor picks left, so the valid patterns are the strings of $L$s followed by $R$s: $k + 1$ of them.

Now case on the two empty even chairs among the six positions. If they are adjacent ($6$ ways), the occupied chairs form one block of $4,$ giving $5$ patterns. If they are separated by one chair ($6$ ways), the blocks have sizes $1$ and $3,$ giving $2 \cdot 4 = 8$ patterns. If they are opposite ($3$ ways), the blocks have sizes $2$ and $2,$ giving $3 \cdot 3 = 9$ patterns. The number of seat configurations is $6 \cdot 5 + 6 \cdot 8 + 3 \cdot 9 = 105.$

Finally, the four ambassador-advisor pairs can be assigned to the four chosen even chairs in $4! = 24$ ways, so $N = 105 \cdot 24 = 2520,$ and the remainder modulo $1000$ is $520.$

Answer: 216

Small Hint:

Let $y = \log_b x;$ by the change-of-base formula the second equation says $\log_b y = \frac{y}{54}$

Big Hint:

The first equation becomes $\frac{y}{2} + \log_b y = \frac{56}{3};$ substitute $\log_b y = \frac{y}{54}$ and solve for $y$

Solution:

Let $y = \log_b x.$ By the change-of-base formula, $$\begin{aligned} \log_{\log x}(x) &= \frac{\log_b x}{\log_b(\log_b x)} \\ &= \frac{y}{\log_b y} = 54, \end{aligned}$$ so $\log_b y = \frac{y}{54}.$ The first equation says $3\left(\frac{1}{2}\log_b x + \log_b(\log_b x)\right) = 56,$ that is, $\frac{y}{2} + \log_b y = \frac{56}{3}.$

Substituting $\log_b y = \frac{y}{54}$ gives $\frac{y}{2} + \frac{y}{54} = \frac{56}{3},$ so $\frac{28y}{54} = \frac{56}{3}$ and $y = 36.$ Then $\log_b 36 = \frac{36}{54} = \frac{2}{3},$ so $b^{\frac{2}{3}} = 36$ and $b = 36^{\frac{3}{2}} = 216.$

Answer: 715

Small Hint:

Each chord cuts off a triangle similar to $ABC:$ the ratios are $\frac{55}{220},$ $\frac{45}{180},$ and $\frac{15}{120}$

Big Hint:

Measure distances to the sides as fractions of the altitudes, which sum to $1;$ the lines sit at levels $\frac34,$ $\frac34,$ $\frac78$

Solution:

For a point $P,$ let $\alpha$ be the distance from $P$ to line $BC$ divided by the length of the altitude from $A,$ and define $\beta$ (to $CA$) and $\gamma$ (to $AB$) similarly; then $\alpha + \beta + \gamma = 1$ for points inside, since $[PBC] + [PCA]$ $+ [PAB] = [ABC].$ A chord parallel to $\overline{BC}$ at level $\alpha$ cuts off a triangle at $A$ similar to $ABC$ with ratio $1 - \alpha,$ so its length is $220(1 - \alpha).$ The chord of length $55$ gives $1 - \alpha = \frac{1}{4},$ so $\ell_A$ is the line $\alpha = \frac{3}{4};$ similarly $45 = 180(1 - \beta)$ puts $\ell_B$ at $\beta = \frac{3}{4},$ and $15 = 120(1 - \gamma)$ puts $\ell_C$ at $\gamma = \frac{7}{8}.$

Along any line parallel to $\overline{BC},$ the coordinate $\beta$ varies linearly, and on the chord at level $\alpha$ inside the triangle, $\beta$ runs over an interval of length $1 - \alpha$ while the chord has length $220(1 - \alpha);$ hence a segment parallel to $\overline{BC}$ with endpoints differing by $\Delta\beta$ has length $220\,|\Delta\beta|.$ The side of the new triangle on $\ell_A$ runs from $\ell_A \cap \ell_B,$ where $\beta = \frac{3}{4},$ to $\ell_A \cap \ell_C,$ where $\beta = 1 - \frac{3}{4} - \frac{7}{8} = -\frac{5}{8}.$ Its length is $$220\left(\frac{3}{4} + \frac{5}{8}\right) = 220 \cdot \frac{11}{8}.$$

Since the three lines are parallel to the sides of $ABC,$ the triangle they bound is similar to $ABC,$ here with ratio $\frac{11}{8}.$ Its perimeter is $\frac{11}{8}(120 + 220 + 180)$ $= \frac{11}{8} \cdot 520 = 715.$

Answer: 53

Small Hint:

$\frac{1 + \sqrt{3}i}{2}$ is a primitive sixth root of unity, and $2016$ is a multiple of $6$

Big Hint:

Matching imaginary parts gives $a + b = 4038;$ the bound on the coefficients then forces both values

Solution:

Let $\omega = \frac{1 + \sqrt{3}i}{2} = \cos 60^\circ + i\sin 60^\circ,$ a primitive sixth root of unity. Since $2016 = 6 \cdot 336,$ we get $\omega^{2016} = 1,$ $\omega^{2017} = \omega,$ and $\omega^{2018} = \omega^2 = \frac{-1 + \sqrt{3}i}{2}.$ Therefore $$\begin{aligned} f(\omega) &= a\omega^2 + b\omega + c \\ &= \left(c + \frac{b - a}{2}\right) \\ &\quad {}+ \frac{(a + b)\sqrt{3}}{2}\,i. \end{aligned}$$

Matching imaginary parts, $\frac{a + b}{2} = 2019,$ so $a + b = 4038.$ Since $a \le 2019$ and $b \le 2019,$ this forces $a = b = 2019.$ Matching real parts then gives $c + 0 = 2015,$ so $c = 2015.$

Hence $f(1) = a + b + c$ $= 4038 + 2015 = 6053,$ whose remainder upon division by $1000$ is $53.$

Answer: 472

Small Hint:

Write $n = 2^a 5^b m$ with $\gcd(m, 10) = 1;$ divisibility by $20$ forces $a \ge 2$ and $b \ge 1$

Big Hint:

Then $(a+1)(b+1)\tau(m) = 20$ with $a + 1 \ge 3$ and $b + 1 \ge 2;$ check which factorizations keep $n \lt 2019$

Solution:

We need $n$ to be a multiple of $20$ and $\tau(n) = 20.$ Write $n = 2^a 5^b m$ with $\gcd(m, 10) = 1;$ then $a \ge 2,$ $b \ge 1,$ and $(a + 1)(b + 1)\tau(m) = 20$ with $a + 1 \ge 3$ and $b + 1 \ge 2.$ The factor $a + 1$ must be a divisor of $20$ that is at least $3:$ one of $4,$ $5,$ $10,$ $20.$

If $a + 1 = 4,$ then $(b + 1)\tau(m) = 5$ forces $b = 4,$ $m = 1,$ so $n = 2^3 5^4 = 5000,$ too large. If $a + 1 = 10,$ then $b = 1,$ $m = 1,$ and $n = 2^9 \cdot 5 = 2560,$ too large. The case $a + 1 = 20$ is impossible because $b + 1 \ge 2.$ If $a + 1 = 5,$ then $(b + 1)\tau(m) = 4,$ giving either $b = 3,$ $m = 1,$ so $n = 2^4 5^3 = 2000 \lt 2019,$ or $b = 1$ and $\tau(m) = 2,$ so $m = p$ is a prime other than $2$ and $5$ and $n = 80p \lt 2019,$ i.e. $p \le 25:$ $p \in \{3, 7, 11, 13, 17, 19, 23\}.$

Therefore $$\begin{aligned} S &= 2000 + 80(3 + 7 + 11 + 13 \\ &\qquad {}+ 17 + 19 + 23) \\ &= 2000 + 80 \cdot 93 \\ &= 9440, \end{aligned}$$ and $\frac{S}{20} = 472.$

Answer: 547

Small Hint:

Work modulo $180^\circ:$ the tangent is positive for angles in $(0^\circ, 90^\circ)$ and negative for angles in $(90^\circ, 180^\circ)$

Big Hint:

If $\theta$ works, the reduction of $8\theta$ works too (same sign pattern shifted by three), so uniqueness forces $8\theta \equiv \theta \pmod{180^\circ}$

Solution:

Since $\tan$ has period $180^\circ,$ only $2^n\theta \bmod 180^\circ$ matters: the tangent is positive on $(0^\circ, 90^\circ)$ and negative on $(90^\circ, 180^\circ).$ Suppose $\theta$ satisfies the condition, and let $\theta'$ be the reduction of $8\theta$ modulo $180^\circ;$ since $\tan(8\theta) \gt 0,$ we have $\theta' \in (0^\circ, 90^\circ).$ For every $n,$ $2^n\theta' \equiv 2^{n+3}\theta \pmod{180^\circ},$ and the sign pattern for the exponents $n + 3$ is the same as for $n,$ so $\theta'$ also satisfies the condition. By uniqueness, $\theta' = \theta,$ so $7\theta \equiv 0 \pmod{180^\circ}$ and $\theta = \frac{180k}{7}$ degrees for some $k \in \{1, 2, 3\}.$

Test each: for $k = 1,$ $2\theta = \frac{360^\circ}{7} \approx 51.4^\circ$ has positive tangent — fails. For $k = 2,$ $4\theta = \frac{1440^\circ}{7} \equiv \frac{180^\circ}{7} \approx 25.7^\circ$ has positive tangent — fails. For $k = 3,$ $\theta = \frac{540^\circ}{7} \approx 77.1^\circ:$ then $2\theta \approx 154.3^\circ$ and $4\theta \equiv 128.6^\circ$ are both in $(90^\circ, 180^\circ),$ and $8\theta \equiv \theta,$ so the pattern positive, negative, negative repeats forever.

Thus $\theta = \frac{540}{7}$ degrees, and $p + q = 540 + 7 = 547.$

Answer: 11

Small Hint:

Use the tangent-chord angle in each circle: $\angle KAC = \angle KBA$ and $\angle KAB = \angle KCA$

Big Hint:

Those equal angles make triangles $KAB$ and $KCA$ similar and give $\angle BKC = 2\angle A;$ apply the law of cosines in triangle $BKC$

Solution:

By the tangent-chord angle in $\omega_1$ (tangent $AC,$ chord $AK$), $\angle KAC = \angle KBA,$ and in $\omega_2$ (tangent $AB,$ chord $AK$), $\angle KAB = \angle KCA.$ Write $u = \angle KAC$ and $v = \angle KAB,$ so $u + v = \angle A.$ Triangles $KAB$ and $KCA$ then have $\angle KAB = v = \angle KCA$ and $\angle KBA = u = \angle KAC,$ so $\triangle KAB \sim \triangle KCA.$ With $t = AK$ this gives $$\frac{KB}{t} = \frac{t}{KC} = \frac{AB}{CA} = \frac{7}{9},$$ so $KB = \frac{7t}{9}$ and $KC = \frac{9t}{7}.$ Also $\angle AKB = \angle AKC$ $= 180^\circ - u - v$ $= 180^\circ - \angle A,$ so $\angle BKC = 360^\circ - 2(180^\circ - \angle A)$ $= 2\angle A.$

From the law of cosines in $ABC,$ $\cos A = \frac{49 + 81 - 64}{2 \cdot 7 \cdot 9} = \frac{11}{21},$ so $\cos 2A = 2\left(\frac{11}{21}\right)^2 - 1 = -\frac{199}{441}.$ The law of cosines in triangle $BKC$ gives $$\begin{aligned} 64 &= \frac{49t^2}{81} + \frac{81t^2}{49} - 2t^2\cos 2A \\ &= t^2 \cdot \frac{2401 + 6561 + 3582}{3969} \\ &= \frac{12544\,t^2}{3969}, \end{aligned}$$ so $t^2 = \frac{64 \cdot 3969}{12544} = \frac{3969}{196}$ and $t = \frac{63}{14} = \frac{9}{2}.$