1994 AIME — Problems & Online Timed Exam

Timed

3:00:00

1.

The increasing sequence $3,$ $15,$ $24,$ $48,$ $\ldots$ consists of those positive multiples of $3$ that are one less than a perfect square. What is the remainder when the $1994$ th term of the sequence is divided by $1000?$

Answer

Answer: 63

Concepts:modular arithmetic counting integers in a range perfect square

Difficulty rating: 1640

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}$

2.

A circle with diameter $\overline{PQ}$ of length $10$ is internally tangent at $P$ to a circle of radius $20.$ Square $ABCD$ is constructed with $A$ and $B$ on the larger circle, $\overline{CD}$ tangent at $Q$ to the smaller circle, and the smaller circle outside $ABCD.$ The length of $\overline{AB}$ can be written in the form $m+\sqrt n,$ where $m$ and $n$ are integers. Find $m+n.$

Answer

Answer: 312

Concepts:chord square (geometry)quadratic

Difficulty rating: 2170

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.$

3.

The function $f$ has the property that, for each real number $x,$ $f(x)+f(x-1)=x^2.$ If $f(19)=94,$ what is the remainder when $f(94)$ is divided by $1000?$

Answer

Answer: 561

Concepts:recursion summation modular arithmetic

Difficulty rating: 1900

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.$

4.

Find the positive integer $n$ for which $\begin{aligned}&\lfloor\log_2 1\rfloor+\lfloor\log_2 2\rfloor+\lfloor\log_2 3\rfloor\\&\quad+\cdots+\lfloor\log_2 n\rfloor=1994.\end{aligned}$ (For real $x,$ $\lfloor x\rfloor$ is the greatest integer not exceeding $x.$ )

Answer

Answer: 312

Concepts:floor and ceiling functions logarithm power of 2

Difficulty rating: 1980

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.$

5.

Given a positive integer $n,$ let $p(n)$ be the product of the nonzero digits of $n.$ (If $n$ has only one digit, then $p(n)$ is equal to that digit.) Let $\begin{aligned}S&=p(1)+p(2)+p(3)\\&\quad+\cdots+p(999).\end{aligned}$ What is the largest prime factor of $S?$

Answer

Answer: 103

Concepts:digits multiplication principle prime factorization

Difficulty rating: 2110

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.$

6.

The graphs of the equations $\begin{aligned}y&=k,\\y&=\sqrt3x+2k,\\y&=-\sqrt3x+2k,\end{aligned}$ are drawn in the coordinate plane for $k=-10,$ $-9,$ $-8,$ $\ldots,$ $9,$ $10.$ These $63$ lines cut part of the plane into equilateral triangles of side $\frac{2}{\sqrt3}.$ How many such triangles are formed?

Answer

Answer: 660

Concepts:equilateral triangle counting regions counting pairs

Difficulty rating: 2350

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.$

7.

For certain ordered pairs $(a,b)$ of real numbers, the system of equations $\begin{aligned}ax+by&=1,\\x^2+y^2&=50\end{aligned}$ has at least one solution, and each solution is an ordered pair $(x,y)$ of integers. How many such ordered pairs $(a,b)$ are there?

Answer

Answer: 72

Concepts:lattice point chord tangent line

Difficulty rating: 2350

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.$

8.

The points $(0,0),$ $(a,11),$ and $(b,37)$ are the vertices of an equilateral triangle. Find the value of $ab.$

Answer

Answer: 315

Concepts:coordinate geometry vector equilateral triangle

Difficulty rating: 1940

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.$

9.

A solitaire game is played as follows. Six distinct pairs of matched tiles are placed in a bag. The player randomly draws tiles one at a time from the bag and retains them, except that matching tiles are put aside as soon as they appear in the player’s hand. The game ends if the player ever holds three tiles, no two of which match; otherwise the drawing continues until the bag is empty. The probability that the bag will be emptied is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p+q.$

Answer

Answer: 394

Concepts:recursive probability sampling without replacement process simulation

Difficulty rating: 2460

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.$

10.

In triangle $ABC,$ angle $C$ is a right angle and the altitude from $C$ meets $\overline{AB}$ at $D.$ The lengths of the sides of $\triangle ABC$ are integers, $BD=29^3,$ and $\cos B=\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m+n.$

Answer

Answer: 450

Concepts:altitude Pythagorean Triple divisibility

Difficulty rating: 2270

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.$

11.

Ninety-four bricks, each measuring $4''\times10''\times19'',$ are to be stacked one on top of another to form a tower $94$ bricks tall. Each brick can be oriented so it contributes $4'',$ $10'',$ or $19''$ to the total height of the tower. How many different tower heights can be achieved using all $94$ of the bricks?

Answer

Answer: 465

Concepts:Diophantine Equation parity counting integers in a range

Difficulty rating: 2270

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.

12.

A fenced, rectangular field measures $24$ meters by $52$ meters. An agricultural researcher has $1994$ meters of fence that can be used for internal fencing to partition the field into congruent, square test plots. The entire field must be partitioned, and the sides of the squares must be parallel to the edges of the field. What is the largest number of square test plots into which the field can be partitioned using all or some of the $1994$ meters of fence?

Answer

Answer: 702

Concepts:tiling divisibility optimization

Difficulty rating: 1900

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.$

13.

The equation $x^{10}+(13x-1)^{10}=0$ has $10$ complex roots $r_1,$ $\overline{r_1},$ $r_2,$ $\overline{r_2},$ $r_3,$ $\overline{r_3},$ $r_4,$ $\overline{r_4},$ $r_5,$ $\overline{r_5},$ where the bar denotes complex conjugation. Find the value of $\begin{aligned}&\frac1{r_1\overline{r_1}}+\frac1{r_2\overline{r_2}}+\frac1{r_3\overline{r_3}}\\&\quad+\frac1{r_4\overline{r_4}}+\frac1{r_5\overline{r_5}}.\end{aligned}$

Answer

Answer: 850

Concepts:roots of unity complex number summation

Difficulty rating: 2650

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.$

14.

A beam of light strikes $\overline{BC}$ at point $C$ with angle of incidence $\alpha=19.94^\circ$ and reflects with an equal angle of reflection as shown. The light beam continues its path, reflecting off line segments $\overline{AB}$ and $\overline{BC}$ according to the rule: angle of incidence equals angle of reflection. Given that $\beta=\frac{\alpha}{10}=1.994^\circ$ and $AB=BC,$ determine the number of times the light beam will bounce off the two line segments. Include the first reflection at $C$ in your count.

Answer

Answer: 71

Concepts:reflection (geometry)angle chasing floor and ceiling functions

Difficulty rating: 2790

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.$

15.

Given a point $P$ on a triangular piece of paper $ABC,$ consider the creases that are formed in the paper when $A,$ $B,$ and $C$ are folded onto $P.$ Let us call $P$ a fold point of $\triangle ABC$ if these creases, which number three unless $P$ is one of the vertices, do not intersect. Suppose that $AB=36,$ $AC=72,$ and $\angle B=90^\circ.$ Then the area of the set of all fold points of $\triangle ABC$ can be written in the form $q\pi-r\sqrt s,$ where $q,$ $r,$ and $s$ are positive integers and $s$ is not divisible by the square of any prime. What is $q+r+s?$

Answer

Answer: 597

Concepts:paper folding perpendicular bisector area decomposition

Difficulty rating: 2840

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.$