1993 AIME Solutions | LIVE by Po-Shen Loh

1.

How many even integers between $4000$ and $7000$ have four different digits?

Answer

Concepts:basic counting casework digits

Difficulty rating: 1920

Small Hint:

Separate the cases according to whether the thousands digit is even or odd

Big Hint:

After choosing the thousands and units digits, count the choices for the two middle digits in order

Solution:

The thousands digit is $4,$ $5,$ or $6.$ If it is $4$ or $6,$ the units digit has $4$ choices among $0,$ $2,$ $4,$ $6,$ and $8,$ after which the hundreds and tens digits have $8$ and $7$ choices. These two cases contribute $2\cdot4\cdot8\cdot7=448.$ If the thousands digit is $5,$ all $5$ even units digits are available, contributing $5\cdot8\cdot7=280.$ Thus the total is $448+280=728.$

2.

During a recent campaign for office, a candidate made a tour of a country which we assume lies in a plane. On the first day of the tour he went east, on the second day he went north, on the third day west, on the fourth day south, on the fifth day east, etc. If the candidate went $\frac{n^2}{2}$ miles on the $n$ th day of this tour, how many miles was he from his starting point at the end of the $40$ th day?

Answer

Concepts:arithmetic sequence distance formula vector

Difficulty rating: 2070

Small Hint:

Group the $40$ days into ten four-day cycles and sum horizontal and vertical displacements separately

Big Hint:

For cycle index $k,$ compare $(4k+1)^2$ with $(4k+3)^2$ , and similarly compare the other pair

Solution:

Index the ten cycles by $k=0,1,\ldots,9.$ The horizontal displacement is $\begin{aligned}&\frac12\sum_{k=0}^9\left((4k+1)^2-(4k+3)^2\right)\\&\quad=\sum_{k=0}^9(-8k-4)\\&\quad=-400.\end{aligned}$ Similarly, the vertical displacement is $\begin{aligned}&\frac12\sum_{k=0}^9\left((4k+2)^2-(4k+4)^2\right)\\&\quad=\sum_{k=0}^9(-8k-6)\\&\quad=-420.\end{aligned}$ Therefore the distance from the start is $\sqrt{400^2+420^2}=580.$

3.

The table below displays some of the results of last summer’s Frostbite Falls Fishing Festival, showing how many contestants caught $n$ fish for various values of $n.$

$n$	$0$	$1$	$2$	$3$	$\ldots$
number of contestants who caught $n$ fish	$9$	$5$	$7$	$23$	$\ldots$

$n$	$13$	$14$	$15$
number of contestants who caught $n$ fish	$5$	$2$	$1$

In the newspaper story covering the event, it was reported that

(a) the winner caught $15$ fish;
(b) those who caught $3$ or more fish averaged $6$ fish each;
(c) those who caught $12$ or fewer fish averaged $5$ fish each.

What was the total number of fish caught during the festival?

Answer

Concepts:data and graph interpretation system of equations weighted mean

Difficulty rating: 2070

Small Hint:

Let $N$ be the total number of contestants and $T$ the total number of fish

Big Hint:

Use the two averages by first subtracting the known groups with fewer than $3$ fish and with more than $12$ fish

Solution:

The $9+5+7=21$ contestants below $3$ fish caught $5+14=19$ fish. Thus condition (b) gives $T-19=6(N-21),$ or $T=6N-107.$ The $5+2+1=8$ contestants above $12$ fish caught $65+28+15=108$ fish, so condition (c) gives $T-108=5(N-8),$ or $T=5N+68.$ Hence $N=175$ and $T=943.$

4.

How many ordered four-tuples of integers $(a,b,c,d)$ with $0<a<b<c<d<500$ satisfy $a+d=b+c$ and $bc-ad=93?$

Answer

Concepts:casework counting integers in a range factoring

Difficulty rating: 2310

Small Hint:

The first equation implies that $b-a=d-c$

Big Hint:

Set $x=b-a=d-c$ and factor $bc-ad$ in terms of $x$ and $c-a$

Solution:

Let $x=b-a=d-c>0$ and $y=c-a.$ Then $\begin{aligned}bc-ad&=(a+x)c-a(c+x)\\&=x(c-a)=xy=93.\end{aligned}$ Since $b<c,$ we need $x<y.$ The positive factor pairs are $(x,y)=(1,93)$ and $(3,31).$ For the first, $d=a+94<500$ gives $405$ choices for $a.$ For the second, $d=a+34<500$ gives $465$ choices. The total is $405+465=870.$

5.

Let $P_0(x)=x^3+313x^2-77x-8.$ For integers $n\geq1,$ define $P_n(x)=P_{n-1}(x-n).$ What is the coefficient of $x$ in $P_{20}(x)?$

Answer

Concepts:algebraic manipulation binomial theorem polynomial

Difficulty rating: 1910

Small Hint:

Collapse the repeated shifts to write $P_{20}$ directly in terms of $P_0$

Big Hint:

Only collect the linear terms after substituting $x-210$

Solution:

The accumulated shift is $1+2+\cdots+20=210,$ so $P_{20}(x)=P_0(x-210).$ The coefficient of $x$ is therefore $\begin{aligned}&3(210)^2-2(313)(210)-77\\&\quad=132300-131460-77\\&\quad=763.\end{aligned}$

6.

What is the smallest positive integer that can be expressed as the sum of nine consecutive integers, the sum of ten consecutive integers, and the sum of eleven consecutive integers?

Answer

Concepts:arithmetic sequence least common multiple modular arithmetic

Difficulty rating: 1740

Small Hint:

A sum of an odd number of consecutive integers is divisible by the number of terms

Big Hint:

A sum of ten consecutive integers is congruent to $5\pmod {10}$

Solution:

The sums of $9$ and $11$ consecutive integers are divisible by $9$ and $11,$ so the desired number is a multiple of $99.$ A sum of $10$ consecutive integers has the form $10a+45,$ hence is congruent to $5\pmod {10}.$ The first multiple of $99$ ending in $5$ is $5\cdot99=495,$ and each of the three required representations then exists.

7.

Three numbers, $a_1,$ $a_2,$ $a_3,$ are drawn randomly and without replacement from the set $\{1,2,3,\ldots,1000\}.$ Three other numbers, $b_1,$ $b_2,$ $b_3,$ are then drawn randomly and without replacement from the remaining set of $997$ numbers. Let $p$ be the probability that, after a suitable rotation, a brick of dimensions $a_1\times a_2\times a_3$ can be enclosed in a box of dimensions $b_1\times b_2\times b_3,$ with the sides of the brick parallel to the sides of the box. If $p$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?

Answer

Concepts:basic probability Catalan Number sampling without replacement

Difficulty rating: 2410

Small Hint:

Condition on the six selected values and record only whether each belongs to the brick or the box in increasing order

Big Hint:

The brick fits exactly when every prefix of this six-letter word contains at least as many $a$ ’s as $b$ ’s

Solution:

After the six distinct values are fixed and sorted, each of the $\binom63=20$ assignments of three values to the brick is equally likely. The sorted brick dimensions fit the sorted box dimensions exactly when, in every prefix of the resulting word of three $a$ ’s and three $b$ ’s, the number of $a$ ’s is at least the number of $b$ ’s. There are $C_3=5$ such words. Thus $p=\frac{5}{20}=\frac{1}{4},$ and the requested sum is $1+4=5.$

8.

Let $S$ be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of $S$ so that the union of the two subsets is $S?$ The order of selection does not matter; for example, the pair of subsets $\{a,c\},$ $\{b,c,d,e,f\}$ represents the same selection as the pair $\{b,c,d,e,f\},$ $\{a,c\}.$

Answer

Concepts:Burnside’s Lemma multiplication principle subsets

Difficulty rating: 1930

Small Hint:

For an ordered pair, each element can lie in the first subset only, the second only, or both

Big Hint:

When the two subsets are swapped, identify the one ordered pair that remains fixed

Solution:

For an ordered pair $(A,B)$ with $A\cup B=S,$ each element has three possible memberships: $A$ only, $B$ only, or both. This gives $3^6=729$ ordered pairs. Swapping $A$ and $B$ fixes only the pair $A=B=S.$ Therefore the number of unordered pairs is $\frac{729+1}{2}=365.$

9.

Two thousand points are given on a circle. Label one of the points $1.$ From this point, count $2$ points in the clockwise direction and label this point $2.$ From the point labeled $2,$ count $3$ points in the clockwise direction and label this point $3.$ (See figure.) Continue this process until the labels $1,$ $2,$ $3,$ $\ldots,$ $1993$ are all used. Some of the points on the circle will have more than one label and some points will not have a label. What is the smallest integer that labels the same point as $1993?$

Answer

Concepts:Chinese Remainder Theorem modular arithmetic quadratic residue

Difficulty rating: 2550

Small Hint:

Measure every label’s clockwise displacement from the point labeled $1$

Big Hint:

Reduce the resulting quadratic congruence separately modulo $32$ and modulo $125$

Solution:

Label $j$ is displaced $2+3+\cdots+j=\frac{j(j+1)}2-1$ points clockwise from label $1.$ Thus it shares the point of label $1993$ exactly when $j(j+1)\equiv1993\cdot1994$ modulo $4000,$ or equivalently when $j(j+1)\equiv2042\pmod {4000}.$ Modulo $125,$ the solutions are $j\equiv6$ and $j\equiv118,$ and modulo $32,$ they are $j\equiv9$ and $j\equiv22.$ Combining these by the Chinese Remainder Theorem gives $\begin{aligned}j\equiv{}&118,1993,\\&2006,3881\pmod {4000}.\end{aligned}$ The smallest positive possibility is $118.$

10.

Euler’s formula states that for a convex polyhedron with $V$ vertices, $E$ edges, and $F$ faces, $V-E+F=2.$ A particular convex polyhedron has $32$ faces, each of which is either a triangle or a pentagon. At each of its $V$ vertices, $T$ triangular faces and $P$ pentagonal faces meet. What is the value of $100P+10T+V?$

Answer

Concepts:double counting Euler’s Polyhedron Formula polyhedron

Difficulty rating: 2500

Small Hint:

Let $x$ be the number of triangular faces and count face-edge and face-vertex incidences

Big Hint:

Use Euler’s formula to express $x$ in terms of $V$ , then obtain two divisibility conditions on $V$

Solution:

Let $x$ be the number of triangular faces, so there are $32-x$ pentagons and $E=\frac{3x+5(32-x)}2=80-x.$ Euler’s formula gives $V+x=50.$ Counting face-vertex incidences yields $\begin{aligned}TV&=3x=150-3V,\\PV&=5(32-x)=5V-90.\end{aligned}$ Hence $V(T+3)=150$ and $V(5-P)=90.$ Also $18\leq V\leq50,$ so the only common divisor of $150$ and $90$ in that range is $V=30.$ Then $T=2$ and $P=2,$ giving $100P+10T+V=250.$

11.

Alfred and Bonnie play a game in which they take turns tossing a fair coin. The winner of a game is the first person to obtain a head. Alfred and Bonnie play this game several times with the stipulation that the loser of a game goes first in the next game. Suppose that Alfred goes first in the first game, and that the probability that he wins the sixth game is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. What are the last three digits of $m+n?$

Answer

Concepts:basic probability recursion recursive probability

Difficulty rating: 2370

Small Hint:

Compute Alfred’s chance to win a single game when he goes first and when Bonnie goes first

Big Hint:

If $p_r$ is Alfred’s chance to win game $r$ , express $p_{r+1}$ in terms of $p_r$

Solution:

Alfred wins a game with probability $\frac{2}{3}$ when he starts and $\frac{1}{3}$ when Bonnie starts. Since the loser starts the next game, $\begin{aligned}p_{r+1}&=\frac23(1-p_r)+\frac13p_r\\&=\frac23-\frac13p_r,\qquad p_1=\frac23.\end{aligned}$ Thus $p_r-\frac12=\frac{(-\frac{1}{3})^{r-1}}{6}.$ In particular, $p_6=\frac12-\frac1{1458}=\frac{364}{729}.$ Therefore $m+n=1093,$ whose last three digits are $093.$

12.

The vertices of $\triangle ABC$ are $A=(0,0),$ $B=(0,420),$ and $C=(560,0).$ The six faces of a die are labeled with two $A$ ’s, two $B$ ’s, and two $C$ ’s. Point $P_1=(k,m)$ is chosen in the interior of $\triangle ABC,$ and points $P_2,$ $P_3,$ $P_4,$ $\ldots$ are generated by rolling the die repeatedly and applying the rule: If the die shows label $L,$ where $L\in\{A,B,C\},$ and $P_n$ is the most recently obtained point, then $P_{n+1}$ is the midpoint of $\overline{P_nL}.$ Given that $P_7=(14,92),$ what is $k+m?$

Answer

Concepts:coordinate geometry power of 2 recursion

Difficulty rating: 2600

Small Hint:

Reverse the six midpoint operations by multiplying the equation for $P_7$ by $64$

Big Hint:

The six rolled vertices receive the distinct weights $1,$ $2,$ $4,$ $8,$ $16,$ and $32$ ; use the $x$ -coordinate first

Solution:

Let $X$ and $Y$ be the sums of the weights $1,$ $2,$ $4,$ $8,$ $16,$ and $32$ assigned to rolls of $C$ and $B,$ respectively. Iterating the midpoint rule gives $\begin{aligned}64P_7&=P_1+X(560,0)\\&\quad+Y(0,420).\end{aligned}$ Hence $k=896-560X.$ Because $P_1$ is interior, $0<k<560,$ forcing $X=1$ and $k=336.$ The triangle inequality for its coordinates then gives $0<m<168.$ Since $m=5888-420Y,$ the only possible integer $Y$ is $14,$ giving $m=8.$ Therefore $k+m=344.$

13.

Jenny and Kenny are walking in the same direction, Kenny at $3$ feet per second and Jenny at $1$ foot per second, on parallel paths that are $200$ feet apart. A tall circular building $100$ feet in diameter is centered midway between the paths. At the instant when the building first blocks the line of sight between Jenny and Kenny, they are $200$ feet apart. Let $t$ be the amount of time, in seconds, before Jenny and Kenny can see each other again. If $t$ is written as a fraction in lowest terms, what is the sum of the numerator and denominator?

Answer

Concepts:distance formula relative speed tangent line

Difficulty rating: 2840

Small Hint:

Place the circular building at the origin and the two paths on $y=100$ and $y=-100$

Big Hint:

At the first blockage both walkers have $x=-50$ ; set the later connecting line’s distance from the origin equal to $50$

Solution:

At first blockage the walkers are vertically aligned on the tangent $x=-50.$ After $t$ seconds their positions may be written as $(-50+t,100)$ and $(-50+3t,-100).$ The distance from the origin to their connecting line is $\frac{|10000-400t|}{\sqrt{4t^2+40000}}.$ At the second tangency this equals $50.$ Squaring and simplifying gives $(100-4t)^2=t^2+10000,$ so $t(15t-800)=0.$ The positive time is $t=\frac{160}{3},$ and the requested sum is $160+3=163.$

14.

A rectangle that is inscribed in a larger rectangle (with one vertex on each side) is called unstuck if it is possible to rotate (however slightly) the smaller rectangle about its center within the confines of the larger. Of all the rectangles that can be inscribed unstuck in a $6$ by $8$ rectangle, the smallest perimeter has the form $\sqrt N,$ for a positive integer $N.$ Find $N.$

Answer

Concepts:coordinate geometry optimization rectangle

Difficulty rating: 2890

Small Hint:

Center the $6$ -by- $8$ rectangle at the origin and parameterize consecutive inner vertices on the right and top sides

Big Hint:

Use equal half-diagonals to relate the two free coordinates, then express the square of the perimeter through the diagonal and area

Solution:

Opposite vertices lie on opposite sides of the outer rectangle, so the two rectangles have the same center. For a small rotation through angle $\delta,$ a right-side contact at $(4,y)$ moves inward only if $y\delta\geq0,$ while a top-side contact at $(u,3)$ moves inward only if $u\delta\leq0.$ Thus an unstuck rectangle has opposite-signed offsets; after reflection, write its consecutive vertices as $(4,y),(-x,3),(-4,-y),(x,-3)$ with $x,y\geq0.$ Equal half-diagonals give $16+y^2=x^2+9,$ so $x^2-y^2=7.$ If its side lengths are $a,b,$ then $\begin{aligned}a^2+b^2&=4(16+y^2),\\ab&=24+2xy.\end{aligned}$ Therefore its perimeter $Q=2(a+b)$ satisfies $\begin{aligned}Q^2&=4(a^2+b^2+2ab)\\&=448+16y(y+x)\geq448.\end{aligned}$ Equality occurs at $y=0,\ x=\sqrt7,$ which gives a non-axis-aligned, hence unstuck, rectangle. Thus the minimum perimeter is $\sqrt{448}$ and $N=448.$

15.

Let $\overline{CH}$ be an altitude of $\triangle ABC.$ Let $R$ and $S$ be the points where the circles inscribed in the triangles $ACH$ and $BCH$ are tangent to $\overline{CH}.$ If $AB=1995,$ $AC=1994,$ and $BC=1993,$ then $RS$ can be expressed as $\frac{m}{n},$ where $m$ and $n$ are relatively prime integers. Find $m+n.$

Answer

Concepts:altitude incircle, incenter, and inradius law of cosines

Difficulty rating: 2560

Small Hint:

Express the distance from $H$ to each tangency point using the semiperimeter of its right triangle

Big Hint:

Find $AH-BH$ from the side lengths without first computing the altitude

Solution:

Let $h=CH.$ In right triangle $ACH,$ the tangent length from $H$ to its incircle is $\frac{AH+h-AC}{2};$ in triangle $BCH,$ it is $\frac{BH+h-BC}{2}.$ Hence $\begin{aligned}RS&=\frac12\left|AH-BH\right.\\&\qquad\left.-AC+BC\right|.\end{aligned}$ The projection formula gives $\begin{aligned}AH-BH&=\frac{AC^2-BC^2}{AB}\\&=\frac{1994^2-1993^2}{1995}\\&=\frac{3987}{1995}.\end{aligned}$ Since $AC-BC=1,$ $RS=\frac12\left(\frac{3987}{1995}-1\right)=\frac{332}{665}.$ Thus $m+n=332+665=997.$