Answer: 59

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

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 $$p_k = \tfrac{1}{2}p_{k-1} + \tfrac{1}{2}p_{k-2}, \qquad p_1 = 1, \quad p_2 = \tfrac{1}{2}.$$

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

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

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

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

Solution:

Let $y = \log_b x.$ By the change-of-base formula, $$\log_{\log x}(x) = \frac{\log_b x}{\log_b(\log_b x)} = \frac{y}{\log_b y} = 54,$$ 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^{2/3} = 36$ and $b = 36^{3/2} = 216.$

Answer: 715

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

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 $$f(\omega) = a\omega^2 + b\omega + c = \left(c + \frac{b - a}{2}\right) + \frac{(a + b)\sqrt{3}}{2}\,i.$$

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

Solution:

We need $20 \mid n$ 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; $a + 1 = 20$ is larger still. 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 $S = 2000 + 80(3 + 7 + 11 + 13 + 17 + 19 + 23) = 2000 + 80 \cdot 93 = 9440,$ and $\frac{S}{20} = 472.$

Answer: 547

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

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 $$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},$$ so $t^2 = \frac{64 \cdot 3969}{12544} = \frac{3969}{196}$ and $t = \frac{63}{14} = \frac{9}{2}.$

Hence $AK = \frac{9}{2}$ and $m + n = 9 + 2 = 11.$

Answer: 47

Solution:

Divisibility is transitive, so every term of a progressive sequence is a multiple of the first term. If a sequence with sum $360$ has length at least $2$ and first term $d,$ then $d \mid 360,$ and dividing the remaining terms by $d$ yields a progressive sequence with first term at least $2$ and sum $\frac{360 - d}{d} = \frac{360}{d} - 1;$ this correspondence is reversible. So if $g(s)$ denotes the number of progressive sequences with sum $s$ and first term at least $2,$ the answer is $1 + \sum_{d \mid 360,\, d \lt 360} g\!\left(\frac{360}{d} - 1\right),$ the leading $1$ counting the sequence $(360).$

The same reduction gives the recursion $$g(s) = 1 + \sum_{\substack{e \mid s \\ 2 \le e \lt s}} g\!\left(\frac{s}{e} - 1\right) \qquad (s \ge 2),$$ with $g(1) = 0;$ in particular $g(s) = 1$ when $s$ is prime. Working upward: $g(2) = g(3) = g(4) = g(5) = g(7) = 1;$ $g(6) = 1 + g(2) = 2;$ $g(8) = 1 + g(3) = 2;$ $g(9) = 1 + g(2) = 2;$ $g(10) = 1 + g(4) = 2;$ $g(12) = 1 + g(5) + g(3) + g(2) = 4;$ $g(14) = 1 + g(6) = 3;$ $g(16) = 1 + g(7) + g(3) = 3;$ $g(21) = 1 + g(6) + g(2) = 4;$ $g(35) = 1 + g(6) + g(4) = 4;$ $g(39) = 1 + g(12) + g(2) = 6;$ $g(44) = 1 + g(21) + g(10) + g(3) = 8;$ $g(119) = 1 + g(16) + g(6) = 6.$

The $23$ divisors $d \lt 360$ give arguments $\frac{360}{d} - 1 = 359,$ $179,$ $119,$ $89,$ $71,$ $59,$ $44,$ $39,$ $35,$ $29,$ $23,$ $19,$ $17,$ $14,$ $11,$ $9,$ $8,$ $7,$ $5,$ $4,$ $3,$ $2,$ $1,$ whose $g$-values are $1, 1, 6, 1, 1, 1, 8, 6, 4, 1, 1, 1, 1, 3, 1, 2, 2, 1, 1, 1, 1, 1, 0,$ summing to $46.$ Adding the single-term sequence gives $46 + 1 = 47.$

Answer: 504

Solution:

Let $O$ be the center, $s$ the side length, $a$ the apothem, and $u_i$ the unit vector from $O$ toward the midpoint of chord $A_iA_{i+1}.$ The region bounded by $\overline{PA_i},$ $\overline{PA_{i+1}},$ and the arc is the circular segment together with triangle $PA_iA_{i+1}.$ The segment has area $\frac{1}{8} - \frac{sa}{2}$ (sector minus triangle $OA_iA_{i+1}$), and the triangle at $P$ has area $\frac{s}{2}(a - P \cdot u_i),$ since $a - P \cdot u_i$ is the distance from $P$ to the chord. Adding, $$\text{area}_i = \frac{1}{8} - \frac{s}{2}\,(P \cdot u_i).$$

The given areas say $\frac{s}{2}(P \cdot u_1) = \frac{1}{8} - \frac{1}{7} = -\frac{1}{56}$ and $\frac{s}{2}(P \cdot u_3) = \frac{1}{8} - \frac{1}{9} = \frac{1}{72}.$ The normals rotate $45^\circ$ per side, so $u_3$ is $u_1$ rotated $90^\circ,$ and $u_6,$ five steps from $u_1,$ is $u_1$ rotated $225^\circ:$ $$u_6 = -\frac{\sqrt{2}}{2}\,(u_1 + u_3).$$ Therefore $$\frac{s}{2}(P \cdot u_6) = -\frac{1}{\sqrt{2}}\left(-\frac{1}{56} + \frac{1}{72}\right) = -\frac{1}{\sqrt{2}} \cdot \left(-\frac{1}{252}\right) = \frac{\sqrt{2}}{504}.$$

The region on side $A_6A_7$ thus has area $\frac{1}{8} - \frac{\sqrt{2}}{504},$ so $n = 504.$

Answer: 71

Solution:

Using $k$ stamps of the denominations $n$ and $n + 1$ produces exactly the amounts $kn + c$ for $0 \le c \le k,$ and adding $5$-cent stamps then covers everything above in the same residue class mod $5.$ So in each class $r$ every amount at least $m(r)$ is formable and nothing smaller is, where $m(r)$ is the least value of $kn + c$ $(0 \le c \le k)$ congruent to $r$ mod $5.$ The greatest non-formable amount is $\max_r m(r) - 5,$ so we need $\max_r m(r) = 96:$ the class of $96$ (which is $1$ mod $5$) must be covered first exactly at $96,$ and every other class no later.

Case on $n \bmod 5,$ noting $kn + c \equiv kn + c.$ If $n \equiv 4:$ class $1$ needs $4k + c \equiv 1$ with $c \le k,$ first possible at $k = 4,$ $c = 0,$ so $4n = 96$ and $n = 24;$ the other classes are covered at $24,$ $48,$ $72,$ all less than $96,$ so $n = 24$ works. If $n \equiv 2:$ class $1$ is first covered at $k = 2,$ $c = 2,$ so $2n + 2 = 96$ and $n = 47;$ the other classes are covered at $47,$ $48,$ $94 \le 96,$ so $n = 47$ works.

If $n \equiv 3:$ class $1$ first at $2n = 96,$ so $n = 48,$ but then class $2$ is first covered at $2n + 1 = 97 \gt 96$ — fails. If $n \equiv 1:$ class $1$ first at $n = 96,$ but then class $3$ is first covered at $2n + 1 = 193$ — fails. If $n \equiv 0:$ class $1$ first at $n + 1 = 96,$ so $n = 95,$ but class $4$ needs $c = 4,$ $k \ge 4,$ giving $4n + 4 \gt 96$ — fails. The answer is $24 + 47 = 71.$