Small Hint:

Pair each positive square with the negative square two below it, and factor $a^2 - b^2 = (a+b)(a-b)$ with $a - b = 2$

Big Hint:

Group four consecutive terms at a time; the block ending in $(4k)^2$ simplifies to $32k - 12$

Solution:

Group the terms four at a time. For $k = 1, 2, \ldots, 25,$ the block ending at $(4k)^2$ is $$\begin{aligned} &(4k)^2 + (4k-1)^2 \\ &\quad {}- (4k-2)^2 - (4k-3)^2 \\ &= 2(8k - 2) + 2(8k - 4) \\ &= 32k - 12, \end{aligned}$$ using the difference of squares $a^2 - b^2 = (a + b)(a - b)$ with $a - b = 2$ twice.

Summing over $k = 1$ to $25,$ $$\begin{aligned} N &= 32 \cdot \frac{25 \cdot 26}{2} - 12 \cdot 25 \\ &= 10400 - 300 = 10100, \end{aligned}$$ so the remainder when $N$ is divided by $1000$ is $100.$

Small Hint:

Neither rider takes a break upon arriving, so Rudolph takes $49$ breaks and Jennifer takes $24$

Big Hint:

With Rudolph’s rate $r$ miles per minute, equate $\frac{50}{r} + 245$ and $\frac{200}{3r} + 120$

Solution:

Let Rudolph bike at $r$ miles per minute. He rests after each of miles $1$ through $49,$ so his total time is $\frac{50}{r} + 49 \cdot 5 = \frac{50}{r} + 245$ minutes. Jennifer bikes at $\frac{3r}{4}$ miles per minute and rests after each of miles $2, 4, \ldots, 48,$ so her total time is $\frac{50}{\frac{3r}{4}} + 24 \cdot 5 = \frac{200}{3r} + 120$ minutes.

Setting the times equal gives $$\frac{50}{r} + 245 = \frac{200}{3r} + 120,$$ so $$\begin{aligned} 125 &= \frac{200 - 150}{3r} \\ &= \frac{50}{3r}, \end{aligned}$$ and $r = \frac{2}{15}.$ The common time is $\frac{50}{\frac{2}{15}} + 245 = 375 + 245 = 620$ minutes.

Small Hint:

Each slice shortens one of the three dimensions by $1$ cm, so the remaining block has dimensions summing to $10 + 13 + 14 - 10 = 27$

Big Hint:

A product of positive numbers with a fixed sum is largest when the numbers are all equal

Solution:

Every slice is $1$ cm wide and parallel to a face, so after each cut the remaining cheese is still a rectangular block, with one dimension shortened by $1.$ If the ten slices shorten the three dimensions by $p,$ $q,$ and $r$ with $p + q + r = 10,$ the remaining block measures $(10 - p) \times (13 - q) \times (14 - r),$ and these dimensions sum to $37 - 10 = 27.$

By the AM-GM inequality, a product of positive numbers with fixed sum $27$ is greatest when all three are equal to $9,$ which is achieved by taking $1$ slice from the $10$ cm dimension, $4$ from the $13$ cm dimension, and $5$ from the $14$ cm dimension. The maximum volume is $9^3 = 729$ cubic cm.

Small Hint:

Start by writing $2008$ in base $3$

Big Hint:

Replace each digit $2$ using $2 \cdot 3^k = 3^{k+1} - 3^k$ so that every coefficient becomes $1$ or $-1$

Solution:

In base $3,$ $2008 = 2202101_3,$ that is, $$\begin{aligned} 2008 &= 2 \cdot 3^6 + 2 \cdot 3^5 + 2 \cdot 3^3 \\ &\quad {}+ 3^2 + 3^0. \end{aligned}$$ To convert the digits $2$ into coefficients $\pm 1,$ use $2 \cdot 3^k = 3^{k+1} - 3^k.$ The two adjacent digits $2$ collapse neatly: $$\begin{aligned} 2 \cdot 3^6 + 2 \cdot 3^5 &= (3^7 - 3^6) \\ &\quad {}+ (3^6 - 3^5) \\ &= 3^7 - 3^5, \end{aligned}$$ and $2 \cdot 3^3 = 3^4 - 3^3.$

Therefore $$\begin{aligned} 2008 &= 3^7 - 3^5 + 3^4 - 3^3 \\ &\quad {}+ 3^2 + 3^0, \end{aligned}$$ which has distinct exponents and coefficients $\pm 1,$ as required. The sum of the exponents is $7 + 5 + 4 + 3 + 2 + 0 = 21.$

Small Hint:

Extend the legs $AB$ and $DC$ to meet at $E;$ since $37^\circ + 53^\circ = 90^\circ,$ the angle at $E$ is right

Big Hint:

The median to the hypotenuse of a right triangle is half the hypotenuse, and $E,$ $M,$ $N$ are collinear

Solution:

Extend legs $\overline{AB}$ and $\overline{DC}$ until they meet at a point $E.$ Since $\angle A + \angle D = 37^\circ + 53^\circ = 90^\circ,$ triangle $EAD$ has a right angle at $E.$ Because $\overline{BC} \parallel \overline{AD},$ triangle $EBC$ is the image of triangle $EAD$ under a homothety centered at $E,$ so the midpoint $M$ of $\overline{BC}$ maps to the midpoint $N$ of $\overline{AD};$ in particular $E,$ $M,$ and $N$ are collinear.

The median to the hypotenuse of a right triangle is half the hypotenuse, so $EN = \frac{2008}{2} = 1004$ and $EM = \frac{1000}{2} = 500.$ Therefore $$\begin{aligned} MN &= EN - EM \\ &= 1004 - 500 = 504. \end{aligned}$$

Small Hint:

Divide the recurrence by $a_{n-1}$ to see that the ratio $\frac{a_n}{a_{n-1}}$ increases by exactly $1$ at each step

Big Hint:

The ratios give $a_n = n!$ and $b_n = \frac{(n+2)!}{2};$ form the quotient

Solution:

Dividing the recurrence by $a_{n-1}$ gives $$\frac{a_n}{a_{n-1}} = 1 + \frac{a_{n-1}}{a_{n-2}},$$ so the consecutive-term ratio increases by exactly $1$ each step. For $\{a_n\}$ the first ratio is $\frac{a_1}{a_0} = 1,$ so $\frac{a_n}{a_{n-1}} = n$ and $a_n = n!.$ The same computation applies to $\{b_n\},$ whose first ratio is $\frac{b_1}{b_0} = 3,$ so $\frac{b_n}{b_{n-1}} = n + 2$ and $b_n = \frac{(n+2)!}{2}.$

Therefore $$\frac{b_{32}}{a_{32}} = \frac{\frac{34!}{2}}{32!} = \frac{34 \cdot 33}{2} = 561.$$

Small Hint:

There is no $x^2$ term, so $r + s + t = 0$ and each of $r + s,$ $s + t,$ $t + r$ is the negative of a root

Big Hint:

When $x + y + z = 0,$ the identity $x^3 + y^3 + z^3 = 3xyz$ applies; Vieta gives the product of the roots from the constant term

Solution:

The cubic has no $x^2$ term, so $r + s + t = 0$ by Vieta’s formulas. Hence $r + s = -t,$ $s + t = -r,$ and $t + r = -s,$ and the desired sum is $$\begin{aligned} &(-t)^3 + (-r)^3 \\ &\quad {}+ (-s)^3 \\ &= -(r^3 + s^3 + t^3). \end{aligned}$$

Whenever $r + s + t = 0,$ the identity $r^3 + s^3 + t^3 - 3rst$ $= (r + s + t)$ $(r^2 + s^2 + t^2 - rs - st - tr)$ gives $r^3 + s^3 + t^3 = 3rst.$ By Vieta’s formulas, $rst = -\frac{2008}{8} = -251,$ so $r^3 + s^3 + t^3 = -753,$ and the answer is $-(-753) = 753.$

Small Hint:

Apply the product-to-sum identity to turn each term into a difference of two sine terms

Big Hint:

The sum telescopes to $\sin(n(n+1)a),$ which is an integer exactly when $n(n+1)$ is a multiple of $1004$

Solution:

By the product-to-sum identity, $$\begin{aligned} &2\cos(k^2 a)\sin(ka) \\ &= \sin(k^2 a + ka) \\ &\quad {}- \sin(k^2 a - ka) \\ &= \sin(k(k+1)a) \\ &\quad {}- \sin((k-1)k a). \end{aligned}$$ Summing over $k = 1$ to $n,$ the terms telescope, leaving $$\sin(n(n+1)a) = \sin\frac{n(n+1)\pi}{2008}.$$

A sine is an integer only when it is $-1,$ $0,$ or $1,$ that is, when its argument is a multiple of $\frac{\pi}{2}.$ So we need $\frac{n(n+1)}{2008}$ to be a multiple of $\frac{1}{2},$ i.e. $n(n+1)$ is divisible by $1004,$ where $1004 = 4 \cdot 251$ and $251$ is prime.

Since $n$ and $n + 1$ are coprime, $251$ must divide one of them, so $n \ge 250.$ For $n = 250$ the product $250 \cdot 251$ is not divisible by $4.$ For $n = 251$ the product $251 \cdot 252$ is divisible by $4 \cdot 251 = 1004.$ The smallest such $n$ is $251.$

Small Hint:

In the complex plane a move sends $z$ to $\omega z + 10,$ where $\omega = e^{\frac{i\pi}{4}}$

Big Hint:

After iterating, group the resulting geometric sum into blocks of $8$ using $\omega^8 = 1$

Solution:

Identify the plane with the complex plane, so a move sends $z$ to $\omega z + 10$ with $\omega = e^{\frac{i\pi}{4}}.$ Starting from $z_0 = 5$ and iterating, $$\begin{aligned} z_{150} &= 5\omega^{150} \\ &\quad {}+ 10 \scriptsize\left(\omega^{149} + \omega^{148} + \cdots + \omega + 1\right). \end{aligned}$$

Since $\omega^8 = 1$ and $150 = 8 \cdot 18 + 6,$ we get $\omega^{150} = \omega^6 = -i.$ In the geometric sum, every block of $8$ consecutive powers adds to $0,$ so the $150$ terms reduce to $$\begin{aligned} &1 + \omega + \cdots + \omega^5 \\ &= -\omega^6 - \omega^7 \\ &= i - \frac{\sqrt{2}}{2} \\ &\quad {}+ \frac{\sqrt{2}}{2}i. \end{aligned}$$ Therefore $$\begin{aligned} z_{150} &= -5i \\ &\quad {}+ 10 \scriptsize\left(-\frac{\sqrt{2}}{2} + \left(1 + \frac{\sqrt{2}}{2}\right)i\right) \\ &= -5\sqrt{2} + \left(5 + 5\sqrt{2}\right)i. \end{aligned}$$

Thus $$\begin{aligned} |p| + |q| &= 5\sqrt{2} + 5 + 5\sqrt{2} \\ &= 5 + 10\sqrt{2} \\ &\approx 19.14, \end{aligned}$$ and the greatest integer less than or equal to this is $19.$

Small Hint:

The squared distance between two array points is $a^2 + b^2$ with $0 \le a, b \le 3$ not both zero, which takes only $9$ distinct values

Big Hint:

Build maximal paths backwards from the longest step: the last two points must be opposite corners, and nearly every earlier point is then forced

Solution:

The squared distance between two points of the array is $a^2 + b^2,$ where $a$ and $b$ are the coordinate differences, each in $\{0, 1, 2, 3\}$ and not both zero. The possible values are $1, 2, 4, 5, 8, 9, 10, 13, 18$ — only $9$ values — so a growing path has at most $10$ points, and a path with $10$ points must use all nine distances in increasing order. Label its points $P_1, \ldots, P_{10}$ so that $P_1 P_2 = 1$ and $P_9 P_{10} = \sqrt{18}.$

Since $\sqrt{18}$ is realized only by opposite corners, there are $4$ ordered choices of $(P_{10}, P_9).$ Next, $P_8 P_9 = \sqrt{13}$ leaves $2$ choices for $P_8,$ the two neighbors of $P_{10},$ symmetric across the main diagonal. From there the distances $\sqrt{10}, 3, \sqrt{8}, \sqrt{5}, 2, \sqrt{2}$ force $P_7, P_6, \ldots, P_2$ uniquely (for $P_7$ the alternative corner choice fails because the point needed next for $P_6$ would coincide with $P_9$ or $P_{10}$). Finally $P_1$ must be at distance $1$ from $P_2,$ and $3$ of its neighbors are unused. One of the resulting paths is shown below.

Hence $m = 10$ and $r = 4 \cdot 2 \cdot 3 = 24,$ so $mr = 240.$

Small Hint:

Place $B = (0,0),$ $C = (56,0),$ $A = (28,96);$ both centers lie on angle bisectors, and $\tan\frac{B}{2} = \tan\frac{C}{2} = \frac{3}{4}$

Big Hint:

The centers are $\left(56 - \frac{64}{3},\, 16\right)$ and $\left(\frac{4q}{3},\, q\right);$ set the distance between them equal to $q + 16$

Solution:

Place $B = (0, 0)$ and $C = (56, 0);$ the altitude from $A$ has length $\sqrt{100^2 - 28^2} = 96,$ so $A = (28, 96).$ Then $\sin B = \frac{24}{25},$ $\cos B = \frac{7}{25},$ and $$\begin{aligned} \tan\frac{B}{2} &= \frac{\sin B}{1 + \cos B} \\ &= \frac{3}{4} = \tan\frac{C}{2}. \end{aligned}$$ A circle of radius $r$ tangent to $\overline{BC}$ and to a slanted side has its center on the bisector from that base vertex, at height $r$ and horizontal distance $\frac{r}{\tan(\frac{C}{2})} = \frac{4r}{3}$ from the vertex. Thus $P = \left(56 - \frac{64}{3},\, 16\right)$ and $Q = \left(\frac{4q}{3},\, q\right),$ where $q$ is the radius of circle $Q.$

External tangency means $PQ = q + 16:$ $$\begin{aligned} &\left(\frac{104 - 4q}{3}\right)^2 + (16 - q)^2 \\ &= (16 + q)^2. \end{aligned}$$ Since $(16 + q)^2 - (16 - q)^2 = 64q,$ this becomes $(104 - 4q)^2 = 576q,$ i.e. $(26 - q)^2 = 36q,$ which simplifies to $q^2 - 88q + 676 = 0,$ so $q = 44 \pm 6\sqrt{35}.$

The root $44 + 6\sqrt{35} \approx 79.5$ would make circle $Q$ extend outside the triangle, so $q = 44 - 6\sqrt{35}.$ Here $m = 44,$ $n = 6,$ and $k = 35 = 5 \cdot 7,$ giving $m + nk = 44 + 210 = 254.$

Small Hint:

On a pole with $b$ blue and $g$ green flags, the greens must occupy distinct gaps among the $b + 1$ gaps determined by the blues: $\binom{b+1}{g}$ ways

Big Hint:

Sum $\binom{b+1}{g}\binom{11-b}{9-g}$ over $g$ using Vandermonde’s identity, then subtract the arrangements that leave a pole empty

Solution:

Suppose the first pole gets $b$ blue and $g$ green flags, the second the remaining $10 - b$ blue and $9 - g$ green. On a pole with $b$ blue flags, the green flags must occupy distinct gaps among the $b + 1$ gaps around the blues, in $\binom{b+1}{g}$ ways. Temporarily ignoring the requirement that each pole be nonempty, the total is $$\begin{aligned} &\sum_{b=0}^{10} \sum_{g=0}^{9} \binom{b+1}{g} \\ &\quad {}\cdot \binom{11-b}{9-g} \\ &= \sum_{b=0}^{10} \binom{12}{9} \\ &= 11 \cdot 220 = 2420, \end{aligned}$$ where the inner sum collapses by Vandermonde’s identity, since $(b + 1) + (11 - b) = 12.$

The arrangements that leave a pole empty put all $19$ flags on one pole, in $\binom{11}{9} = 55$ ways for each choice of pole. Hence $$N = 2420 - 2 \cdot 55 = 2310,$$ and the remainder when $N$ is divided by $1000$ is $310.$

Small Hint:

Writing $w = \frac{1}{z},$ the half-plane $\mathrm{Re}\,z \gt \frac{1}{2}$ maps exactly onto the disk of radius $1$ centered at $1$

Big Hint:

$S$ is the union of six unit disks centered at the sixth roots of unity; by symmetry find the area inside one $60^\circ$ wedge as a $120^\circ$ sector plus two triangles

Solution:

The hexagon’s sides lie at distance $\frac{1}{2}$ from the origin, with one side on the line $\mathrm{Re}\,z = \frac{1}{2},$ so $R$ is the union of the six half-planes obtained by rotating $\mathrm{Re}\,z \gt \frac{1}{2}$ by multiples of $60^\circ.$ If $w = u + vi = \frac{1}{z},$ then $\mathrm{Re}\,z = \mathrm{Re}\,\frac{1}{w} = \frac{u}{u^2 + v^2} \gt \frac{1}{2}$ is equivalent to $u^2 + v^2 \lt 2u,$ i.e. $(u - 1)^2 + v^2 \lt 1.$ So each half-plane maps onto an open unit disk, and $S$ is the union of six unit disks centered at the sixth roots of unity.

Cut the plane into six $60^\circ$ wedges by the rays at angles $30^\circ + 60^\circ k;$ by symmetry, within each wedge $S$ coincides with the disk whose center lies in that wedge. The rays at $\pm 30^\circ$ meet the circle $|w - 1| = 1$ at $\left(\frac{3}{2}, \pm\frac{\sqrt{3}}{2}\right),$ so the piece of $S$ in that wedge consists of two triangles with vertices at $0,$ the center $1,$ and one of these points — each isosceles with two sides $1$ and apex angle $120^\circ,$ area $\frac{\sqrt{3}}{4}$ — together with the $120^\circ$ sector of the disk between them, area $\frac{\pi}{3}.$