Small Hint:

A number $k^2-1$ is divisible by $3$ exactly when $k$ is not divisible by $3$

Big Hint:

Index the eligible values of $k$ in pairs, then reduce the required square modulo $1000$

Solution:

The terms are $k^2-1$ for integers $k\geq2$ not divisible by $3.$ In each block of three consecutive $k$’s there are two eligible values. The $1994=2\cdot997$th corresponds to $k=3(997)+1=2992.$ Since $2992\equiv992\equiv-8\pmod {1000},$ $$\begin{aligned}k^2-1&\equiv(-8)^2-1\\&\equiv63\pmod {1000}.\end{aligned}$$

Small Hint:

Place the large circle at the origin and put $P$ and $Q$ on a diameter

Big Hint:

If the square’s side is $s$, its chord side $AB$ lies at distance $|10-s|$ from the large circle’s center

Solution:

Put the large circle at the origin with $P=(20,0)$ and $Q=(10,0).$ Let the square’s side be $s.$ Because the smaller circle is outside the square, $\overline{CD}$ lies on $x=10$ and the parallel chord $\overline{AB}$ lies on $x=10-s.$ A chord of the radius-$20$ circle then gives $$s=2\sqrt{400-(10-s)^2}.$$ Squaring yields $s^2-16s-240=0,$ so $s=8+4\sqrt{19}=8+\sqrt{304}.$ Thus $m+n=8+304=312.$

Small Hint:

First use $x=20$ to find $f(20)$

Big Hint:

Eliminate alternating terms by deriving a recurrence from $f(x)$ to $f(x-2)$

Solution:

First $f(20)=20^2-f(19)=306.$ Subtracting through two steps gives $$\begin{aligned}f(x)&=x^2-(x-1)^2+f(x-2)\\&=2x-1+f(x-2).\end{aligned}$$ Therefore $$\begin{aligned}f(94)&=306+\sum_{j=11}^{47}(4j-1)\\&=306+4(1073)-37\\&=4561.\end{aligned}$$ The requested remainder is $561.$

Small Hint:

Group integers having the same value of $\lfloor\log_2 k\rfloor$

Big Hint:

Compute the sum through $255$, after which every new term initially contributes $8$

Solution:

For $2^j\leq k<2^{j+1},$ the summand is $j.$ Thus the sum through $255=2^8-1$ is $$\sum_{j=0}^7j2^j=(8-2)2^8+2=1538.$$ The remaining $1994-1538=456$ is $57\cdot8,$ so we include $57$ more integers beginning with $256.$ Hence $n=255+57=312.$

Small Hint:

Write every number from $000$ through $999$ using three digits and let a zero digit contribute a factor of $1$

Big Hint:

The sum factors by digit position; remember to remove the contribution of $000$

Solution:

For one digit position, the sum of its effective factors is $1+1+2+\cdots+9=46,$ where the first $1$ represents digit $0.$ Thus the sum over $000$ through $999$ is $46^3.$ Removing the artificial contribution $1$ from $000$ gives $$\begin{aligned}S&=46^3-1\\&=45(46^2+46+1)\\&=45\cdot2163.\end{aligned}$$ Since $2163=3\cdot721=3\cdot7\cdot103,$ the largest prime factor is $103.$

Small Hint:

Index one line from each family by $i,j,k$ in $[-10,10]$

Big Hint:

A smallest triangular cell occurs precisely when $i=j+k+1$ or $i=j+k-1$

Solution:

A unit triangular cell is determined by indices $i,j,k\in[-10,10]$ satisfying $i=j+k\pm1.$ For the plus sign, $-11\leq j+k\leq9.$ There are $21-|s|$ ordered pairs $(j,k)$ with sum $s,$ so this orientation contributes $$\sum_{s=-11}^{9}(21-|s|)=330.$$ By symmetry the other orientation also contributes $330,$ for a total of $660.$

Small Hint:

List all integer points on $x^2+y^2=50$

Big Hint:

Count both chords through two non-antipodal lattice points and tangents at one lattice point

Solution:

The circle has the $12$ lattice points obtained from $(\pm1,\pm7),$ $(\pm5,\pm5),$ and $(\pm7,\pm1).$ A secant satisfying the condition is determined by any two non-antipodal lattice points. This gives $\binom{12}{2}-6=60$ lines; antipodal pairs are excluded because their line passes through the origin and cannot have equation $ax+by=1.$ There are also $12$ tangents, one at each lattice point. Each line has a unique normalization $ax+by=1,$ so the total is $60+12=72.$

Small Hint:

The vector $(b,37)$ is a rotation of $(a,11)$ through $60^\circ$ or $-60^\circ$

Big Hint:

Use the second coordinate of the rotation first, then compute the first coordinate

Solution:

For a $60^\circ$ rotation, $$37=\frac{\sqrt3}{2}a+\frac{11}{2},$$ so $a=21\sqrt3.$ The first coordinate is then $$b=\frac a2-\frac{11\sqrt3}{2}=5\sqrt3.$$ The opposite orientation changes both signs and leaves the product unchanged. Hence $ab=(21\sqrt3)(5\sqrt3)=315.$

Small Hint:

Track the number $r$ of unseen pairs and the number $h$ of unmatched tiles currently held

Big Hint:

From state $(r,h)$, the next tile either matches one of the $h$ held tiles or opens one of the $r$ unseen pairs

Solution:

Let $F(r,h)$ be the chance of success with $r$ unseen pairs and $h\leq2$ unmatched tiles held. Among $2r+h$ remaining tiles, $h$ close an open pair and $2r$ open a new pair; the latter move fails when $h=2.$ Thus $$\begin{aligned}F(r,h)&=\frac{hF(r,h-1)}{2r+h}\\&\quad+\frac{2rF(r-1,h+1)}{2r+h},\end{aligned}$$ omitting the second term when $h=2,$ with $F(0,h)=1.$ Evaluating this three-state recursion gives $$\begin{aligned}F(r,0):\quad&1,\ 1,\ \frac35,\ \frac9{35},\\&\frac3{35},\ \frac9{385}\end{aligned}$$ for $r=1,2,\ldots,6.$ Hence $\frac{p}{q}=\frac{9}{385}$ and $p+q=394.$

Small Hint:

Use similarity to write $BD=\frac{BC^2}{AB}$

Big Hint:

Express $\frac{BC}{AB}=\frac{m}{n}$ in lowest terms and use the prime factorization of $29^3$

Solution:

Write $\frac{BC}{AB}=\frac{m}{n}$ in lowest terms, with $BC=km$ and $AB=kn.$ Similarity gives $$29^3=BD=\frac{BC^2}{AB}=\frac{km^2}{n}.$$ Hence $k$ is divisible by $n;$ writing $k=nt$ gives $tm^2=29^3.$ The possibility $m=1$ cannot be a leg of a nondegenerate integer right triangle, so $m=29.$ Writing the other leg of the primitive triple as $u,$ we have $(n-u)(n+u)=29^2,$ giving $n=421$ and $u=420.$ Therefore $m+n=29+421=450.$

Small Hint:

Start with all bricks contributing $4$ inches and count possible increments

Big Hint:

If $c$ bricks contribute $19$ inches, the remaining increments form a parity interval as the number of $10$-inch bricks varies

Solution:

If $b$ bricks use height $10$ and $c$ use height $19,$ the total is $376+3(2b+5c),$ where $b,c\geq0$ and $b+c\leq94.$ For fixed $c,$ the value $v=2b+5c$ runs by twos from $5c$ to $188+3c.$ The even-$c$ intervals cover every even $v$ from $0$ through $464,$ as well as $470,$ missing only $466$ and $468.$ The odd-$c$ intervals cover every odd $v$ from $5$ through $461,$ as well as $465$ and $467,$ missing only $1,$ $3,$ $463,$ and $469.$ Thus there are $471-6=465$ distinct heights.

Small Hint:

If there are $m$ rows and $n$ columns, equality of square side lengths forces $m:n=6:13$

Big Hint:

Write $m=6k$ and $n=13k$, then calculate only the internal fence length

Solution:

Let the grid have $6k$ rows and $13k$ columns, so each square has side $\frac{4}{k}.$ The internal vertical and horizontal fences have total length $$\begin{aligned}&52(6k-1)+24(13k-1)\\&\quad=624k-76.\end{aligned}$$ Requiring this to be at most $1994$ gives $k\leq3.$ With $k=3,$ the number of plots is $(6k)(13k)=78k^2=702.$

Small Hint:

Set $\frac{x}{13x-1}=\zeta,$ where $\zeta^{10}=-1$

Big Hint:

Express $\frac{1}{|x|^2}$ in terms of $\zeta+\overline\zeta$ and sum over the five conjugate pairs

Solution:

Let $\zeta=\frac{x}{13x-1},$ so $\zeta^{10}=-1$ and $$\begin{aligned}x&=\frac{\zeta}{13\zeta-1},\\\frac1x&=13-\zeta^{-1}.\end{aligned}$$ Since $|\zeta|=1,$ $$\begin{aligned}\frac1{|x|^2}&=|13-\zeta^{-1}|^2\\&=170-13(\zeta+\overline\zeta).\end{aligned}$$ Summing one value for each of the five conjugate pairs gives $5\cdot170$ minus $13$ times the sum of all ten roots of $z^{10}+1,$ which is $0.$ The requested value is $850.$

Small Hint:

Unfold each reflection by reflecting the next copy of the two-segment angle instead of reflecting the beam

Big Hint:

After $k$ reflections beyond the first one, the relevant boundary ray has turned through $k\beta$

Solution:

Unfold the path at each bounce, so the beam becomes one straight line crossing successive reflected copies of the angle at $B.$ After $k$ reflections beyond the initial reflection at $C,$ the next boundary ray makes angle $k\beta$ with the original one. Using $AB=BC,$ the crossing remains on the finite segments exactly while $$k\beta\leq180^\circ-2\alpha.$$ Therefore $$k\leq\frac{180-2(19.94)}{1.994}\approx70.27,$$ so there are $70$ further reflections. Including the first reflection at $C$ gives $71.$

Small Hint:

Two fold creases meet at the circumcenter of the triangle formed by $P$ and the corresponding two vertices

Big Hint:

The fold-point locus is the intersection of the disks with diameters $AB$ and $BC$

Solution:

The creases for two vertices meet at the circumcenter of the triangle formed with $P.$ This intersection lies off the paper exactly when the angle at $P$ is obtuse, so the fold-point locus is the intersection of the three diameter disks for $AB,$ $BC,$ and $CA.$ The $CA$ disk contains the entire right triangle, leaving the intersection of the $AB$ and $BC$ disks.

Here $BC=\sqrt{72^2-36^2}=36\sqrt3.$ The two relevant radii are $18$ and $18\sqrt3,$ and their lens consists of circular segments with central angles $120^\circ$ and $60^\circ.$ Its area is $$\begin{aligned}&\left(\frac\pi3\cdot18^2\right.\\&\qquad\left.-\frac12\cdot18^2\sin120^\circ\right)\\&+\left(\frac\pi6(18\sqrt3)^2\right.\\&\qquad\left.-\frac12(18\sqrt3)^2\sin60^\circ\right)\\&=270\pi-324\sqrt3.\end{aligned}$$ Thus $q+r+s$ equals $270+324+3=597.$