HMMT 2004

How many ordered pairs of integers (a,b) satisfy all of the following inequalities?

$$\begin{aligned} a^{2}+b^{2} & <16 \\ a^{2}+b^{2} & <8 a \\ a^{2}+b^{2} & <8 b \end{aligned}$$

Find the largest number $n$ such that (2004!)! is divisible by (( $n!)!$ )!.

Compute:

$$\left\lfloor\frac{2005^{3}}{2003 \cdot 2004}-\frac{2003^{3}}{2004 \cdot 2005}\right\rfloor .$$

Evaluate the sum

$$\frac{1}{2\lfloor\sqrt{1}\rfloor+1}+\frac{1}{2\lfloor\sqrt{2}\rfloor+1}+\frac{1}{2\lfloor\sqrt{3}\rfloor+1}+\cdots+\frac{1}{2\lfloor\sqrt{100}\rfloor+1} .$$

There exists a positive real number $x$ such that $\cos \left(\tan ^{-1}(x)\right)=x$. Find the value of $x^{2}$.

Find all real solutions to $x^{4}+(2-x)^{4}=34$.

If $x, y, k$ are positive reals such that

$$3=k^{2}\left(\frac{x^{2}}{y^{2}}+\frac{y^{2}}{x^{2}}\right)+k\left(\frac{x}{y}+\frac{y}{x}\right),$$

find the maximum possible value of $k$.

Let $x$ be a real number such that $x^{3}+4 x=8$. Determine the value of $x^{7}+64 x^{2}$.

A sequence of positive integers is defined by $a_{0}=1$ and $a_{n+1}=a_{n}^{2}+1$ for each $n \geq 0$. Find $\operatorname{gcd}\left(a_{999}, a_{2004}\right)$.

There exists a polynomial $P$ of degree 5 with the following property: if $z$ is a complex number such that $z^{5}+2004 z=1$, then $P\left(z^{2}\right)=0$. Calculate the quotient $P(1) / P(-1)$.

In trapezoid $A B C D, A D$ is parallel to $B C . \angle A=\angle D=45^{\circ}$, while $\angle B=\angle C=135^{\circ}$. If $A B=6$ and the area of $A B C D$ is 30 , find $B C$.

A parallelogram has 3 of its vertices at $(1,2),(3,8)$, and $(4,1)$. Compute the sum of the possible $x$-coordinates for the 4th vertex.

A swimming pool is in the shape of a circle with diameter 60 ft . The depth varies linearly along the east-west direction from 3 ft at the shallow end in the east to 15 ft at the diving end in the west (this is so that divers look impressive against the sunset) but does not vary at all along the north-south direction. What is the volume of the pool, in $\mathrm{ft}^{3}$ ?

$P$ is inside rectangle $A B C D . P A=2, P B=3$, and $P C=10$. Find $P D$.

Find the area of the region of the $x y$-plane defined by the inequality $|x|+|y|+|x+y| \leq 1$.

In trapezoid $A B C D$ shown, $A D$ is parallel to $B C$, and $A B=6, B C=7, C D=$ $8, A D=17$. If sides $A B$ and $C D$ are extended to meet at $E$, find the resulting angle at $E$ (in degrees).

Yet another trapezoid $A B C D$ has $A D$ parallel to $B C . A C$ and $B D$ intersect at $P$. If $[A D P] /[B C P]=1 / 2$, find $[A D P] /[A B C D]$. (Here the notation $\left[P_{1} \cdots P_{n}\right]$ denotes the area of the polygon $P_{1} \cdots P_{n}$.)

A triangle has side lengths 18,24 , and 30 . Find the area of the triangle whose vertices are the incenter, circumcenter, and centroid of the original triangle.

Right triangle $X Y Z$ has right angle at $Y$ and $X Y=228, Y Z=2004$. Angle $Y$ is trisected, and the angle trisectors intersect $X Z$ at $P$ and $Q$ so that $X, P, Q, Z$ lie on $X Z$ in that order. Find the value of $(P Y+Y Z)(Q Y+X Y)$.

There are 1000 rooms in a row along a long corridor. Initially the first room contains 1000 people and the remaining rooms are empty. Each minute, the following happens: for each room containing more than one person, someone in that room decides it is too crowded and moves to the next room. All these movements are simultaneous (so nobody moves more than once within a minute). After one hour, how many different rooms will have people in them?

How many ways can you mark 8 squares of an $8 \times 8$ chessboard so that no two marked squares are in the same row or column, and none of the four corner squares is marked? (Rotations and reflections are considered different.)

A class of 10 students took a math test. Each problem was solved by exactly 7 of the students. If the first nine students each solved 4 problems, how many problems did the tenth student solve?

Andrea flips a fair coin repeatedly, continuing until she either flips two heads in a row (the sequence $H H$ ) or flips tails followed by heads (the sequence $T H$ ). What is the probability that she will stop after flipping $H H$ ?

A best-of-9 series is to be played between two teams; that is, the first team to win 5 games is the winner. The Mathletes have a chance of $2 / 3$ of winning any given game. What is the probability that exactly 7 games will need to be played to determine a winner?

A committee of 5 is to be chosen from a group of 9 people. How many ways can it be chosen, if Bill and Karl must serve together or not at all, and Alice and Jane refuse to serve with each other?

We have a polyhedron such that an ant can walk from one vertex to another, traveling only along edges, and traversing every edge exactly once. What is the smallest possible total number of vertices, edges, and faces of this polyhedron?

Urn A contains 4 white balls and 2 red balls. Urn B contains 3 red balls and 3 black balls. An urn is randomly selected, and then a ball inside of that urn is removed. We then repeat the process of selecting an urn and drawing out a ball, without returning the first ball. What is the probability that the first ball drawn was red, given that the second ball drawn was black?

A classroom consists of a $5 \times 5$ array of desks, to be filled by anywhere from 0 to 25 students, inclusive. No student will sit at a desk unless either all other desks in its row or all others in its column are filled (or both). Considering only the set of desks that are occupied (and not which student sits at each desk), how many possible arrangements are there?

In a game similar to three card monte, the dealer places three cards on the table: the queen of spades and two red cards. The cards are placed in a row, and the queen starts in the center; the card configuration is thus RQR. The dealer proceeds to move. With each move, the dealer randomly switches the center card with one of the two edge cards (so the configuration after the first move is either RRQ or QRR). What is the probability that, after 2004 moves, the center card is the queen?

Let $f(x)=\sin (\sin x)$. Evaluate $\lim _{h \rightarrow 0} \frac{f(x+h)-f(h)}{x}$ at $x=\pi$.

Suppose the function $f(x)-f(2 x)$ has derivative 5 at $x=1$ and derivative 7 at $x=2$. Find the derivative of $f(x)-f(4 x)$ at $x=1$.

Find $\lim _{x \rightarrow \infty}\left(\sqrt[3]{x^{3}+x^{2}}-\sqrt[3]{x^{3}-x^{2}}\right)$.

Let $f(x)=\cos (\cos (\cos (\cos (\cos (\cos (\cos (\cos x)))))))$, and suppose that the number $a$ satisfies the equation $a=\cos a$. Express $f^{\prime}(a)$ as a polynomial in $a$.

A mouse is sitting in a toy car on a negligibly small turntable. The car cannot turn on its own, but the mouse can control when the car is launched and when the car stops (the car has brakes). When the mouse chooses to launch, the car will immediately leave the turntable on a straight trajectory at 1 meter per second.

Suddenly someone turns on the turntable; it spins at 30 rpm . Consider the set $S$ of points the mouse can reach in his car within 1 second after the turntable is set in motion. (For example, the arrows in the figure below represent two possible paths the mouse can take.) What is the area of $S$, in square meters?

For $x>0$, let $f(x)=x^{x}$. Find all values of $x$ for which $f(x)=f^{\prime}(x)$.

Find the area of the region in the $x y$-plane satisfying $x^{6}-x^{2}+y^{2} \leq 0$.

If $x$ and $y$ are real numbers with $(x+y)^{4}=x-y$, what is the maximum possible value of $y$ ?

Find the positive constant $c_{0}$ such that the series

$$\sum_{n=0}^{\infty} \frac{n!}{(c n)^{n}}$$

converges for $c>c_{0}$ and diverges for $0<c<c_{0}$.

Let $P(x)=x^{3}-\frac{3}{2} x^{2}+x+\frac{1}{4}$. Let $P^{[1]}(x)=P(x)$, and for $n \geq 1$, let $P^{[n+1]}(x)=$ $P^{[n]}(P(x))$. Evaluate $\int_{0}^{1} P^{[2004]}(x) d x$.

What is the largest whole number that is equal to the product of its digits?

Suppose $f$ is a function that assigns to each real number $x$ a value $f(x)$, and suppose the equation

$$f\left(x_{1}+x_{2}+x_{3}+x_{4}+x_{5}\right)=f\left(x_{1}\right)+f\left(x_{2}\right)+f\left(x_{3}\right)+f\left(x_{4}\right)+f\left(x_{5}\right)-8$$

holds for all real numbers $x_{1}, x_{2}, x_{3}, x_{4}, x_{5}$. What is $f(0)$ ?

How many ways can you mark 8 squares of an $8 \times 8$ chessboard so that no two marked squares are in the same row or column, and none of the four corner squares is marked? (Rotations and reflections are considered different.)

A rectangle has perimeter 10 and diagonal $\sqrt{15}$. What is its area?

Find the ordered quadruple of digits $(A, B, C, D)$, with $A>B>C>D$, such that

$$\begin{aligned} & A B C D \\ - & D C B A \\ = & B D A C . \end{aligned}$$

Let $A C E$ be a triangle with a point $B$ on segment $A C$ and a point $D$ on segment $C E$ such that $B D$ is parallel to $A E$. A point $Y$ is chosen on segment $A E$, and segment $C Y$ is drawn. Let $X$ be the intersection of $C Y$ and $B D$. If $C X=5, X Y=3$, what is the ratio of the area of trapezoid $A B D E$ to the area of triangle $B C D$ ?

You have a $10 \times 10$ grid of squares. You write a number in each square as follows: you write $1,2,3, \ldots, 10$ from left to right across the top row, then $11,12, \ldots, 20$ across the second row, and so on, ending with a 100 in the bottom right square. You then write a second number in each square, writing $1,2, \ldots, 10$ in the first column (from top to bottom), then $11,12, \ldots, 20$ in the second column, and so forth.

When this process is finished, how many squares will have the property that their two numbers sum to 101 ?

A floor is tiled with equilateral triangles of side length 1 , as shown. If you drop a needle of length 2 somewhere on the floor, what is the largest number of triangles it could end up intersecting? (Only count the triangles whose interiors are met by the needle - touching along edges or at corners doesn't qualify.)

Andrea flips a fair coin repeatedly, continuing until she either flips two heads in a row (the sequence $H H$ ) or flips tails followed by heads (the sequence $T H$ ). What is the probability that she will stop after flipping $H H$ ?

A horse stands at the corner of a chessboard, a white square. With each jump, the horse can move either two squares horizontally and one vertically or two vertically and one horizontally (like a knight moves). The horse earns two carrots every time it lands on a black square, but it must pay a carrot in rent to rabbit who owns the chessboard for every move it makes. When the horse reaches the square on which it began, it can leave. What is the maximum number of carrots the horse can earn without touching any square more than twice?

Eight strangers are preparing to play bridge. How many ways can they be grouped into two bridge games - that is, into unordered pairs of unordered pairs of people?

$a$ and $b$ are positive integers. When written in binary, $a$ has 2004 1's, and $b$ has 2005 1's (not necessarily consecutive). What is the smallest number of 1 's $a+b$ could possibly have?

Farmer John is grazing his cows at the origin. There is a river that runs east to west 50 feet north of the origin. The barn is 100 feet to the south and 80 feet to the east of the origin. Farmer John leads his cows to the river to take a swim, then the cows leave the river from the same place they entered and Farmer John leads them to the barn. He does this using the shortest path possible, and the total distance he travels is $d$ feet. Find the value of $d$.

A freight train leaves the town of Jenkinsville at 1:00 PM traveling due east at constant speed. Jim, a hobo, sneaks onto the train and falls asleep. At the same time, Julie leaves Jenkinsville on her bicycle, traveling along a straight road in a northeasterly direction (but not due northeast) at 10 miles per hour. At 1:12 PM, Jim rolls over in his sleep and falls from the train onto the side of the tracks. He wakes up and immediately begins walking at 3.5 miles per hour directly towards the road on which Julie is riding. Jim reaches the road at 2:12 PM, just as Julie is riding by. What is the speed of the train in miles per hour?

Given is a regular tetrahedron of volume 1 . We obtain a second regular tetrahedron by reflecting the given one through its center. What is the volume of their intersection?

A lattice point is a point whose coordinates are both integers. Suppose Johann walks in a line from the point $(0,2004)$ to a random lattice point in the interior (not on the boundary) of the square with vertices $(0,0),(0,99),(99,99),(99,0)$. What is the probability that his path, including the endpoints, contains an even number of lattice points?

Show that any number in row $n$ (for $n>0$ ) is at most $2^{n-1}$.

What is the earliest row in which the number 2004 may appear?

Let

$$S(n, r)=\binom{n-1}{r-1}+\binom{n-1}{r}+\binom{n-1}{r+1}+\cdots+\binom{n-1}{n-1}$$

for all $n, r>0$, and in particular $S(n, r)=0$ if $r>n>0$. Prove that the number in row $n$ of the table, $r$ columns to the left of the 1 in the top row, is at most $S(n, r)$. (Hint: First prove that $S(n-1, r-1)+S(n-1, r)=S(n, r)$.)

Show that the sum of all the numbers in row $n$ is at most $(n+2) 2^{n-1}$.

Prove that the number of switch pairs in row $n$ is at most twice the number of odd numbers in row $n$.

Prove that the number of odd numbers in row $n$ is at most twice the number of switch pairs in row $n-1$.

Prove that the number of switch pairs in row $n$ is at most twice the number of switch pairs in row $n-1$.

Prove that $a \star b=b \star a$ for all $a, b \in S$.

If $b$ is any element of $T$, prove that $b \star b=b$.

Let $a$ be an element of $T$. Let the image of $a$ be the set of all elements of $T$ that can be represented as $a \star b$ for some $b \in T$. Prove that if $c$ is in the image of $a$, then $a \star c=c$.

Prove that there exists an element $a \in T$ such that the equation $a \star b=a$ holds for all $b \in T$.

Prove that there exists an element $a \in S$ such that the equation $a \star b=a$ holds for all $b \in S$.

Let $n$ be a positive odd integer. Prove that

$$\left\lfloor\log _{2} n\right\rfloor+\left\lfloor\log _{2}(n / 3)\right\rfloor+\left\lfloor\log _{2}(n / 5)\right\rfloor+\left\lfloor\log _{2}(n / 7)\right\rfloor+\cdots+\left\lfloor\log _{2}(n / n)\right\rfloor=(n-1) / 2 .$$

Prove that

$$\sigma(1)+\sigma(2)+\sigma(3)+\cdots+\sigma(n) \leq n^{2}$$

for every positive integer $n$.

Prove that

$$\frac{\sigma(1)}{1}+\frac{\sigma(2)}{2}+\frac{\sigma(3)}{3}+\cdots+\frac{\sigma(n)}{n} \leq 2 n$$

for every positive integer $n$.

Now suppose again that $n$ is odd. Prove that

$$\sigma(1)\left\lfloor\log _{2} n\right\rfloor+\sigma(3)\left\lfloor\log _{2}(n / 3)\right\rfloor+\sigma(5)\left\lfloor\log _{2}(n / 5)\right\rfloor+\cdots+\sigma(n)\left\lfloor\log _{2}(n / n)\right\rfloor<n^{2} / 8$$

Find the value of

$$\binom{6}{1} 2^{1}+\binom{6}{2} 2^{2}+\binom{6}{3} 2^{3}+\binom{6}{4} 2^{4}+\binom{6}{5} 2^{5}+\binom{6}{6} 2^{6} .$$

If the three points

$$\begin{aligned} & (1, a, b) \\ & (a, 2, b) \\ & (a, b, 3) \end{aligned}$$

are collinear (in 3 -space), what is the value of $a+b$ ?

If the system of equations

$$\begin{aligned} & |x+y|=99 \\ & |x-y|=c \end{aligned}$$

has exactly two real solutions $(x, y)$, find the value of $c$.

A tree grows in a rather peculiar manner. Lateral cross-sections of the trunk, leaves, branches, twigs, and so forth are circles. The trunk is 1 meter in diameter to a height of 1 meter, at which point it splits into two sections, each with diameter .5 meter. These sections are each one meter long, at which point they each split into two sections, each with diameter .25 meter. This continues indefinitely: every section of tree is 1 meter long and splits into two smaller sections, each with half the diameter of the previous. What is the total volume of the tree?

Augustin has six $1 \times 2 \times \pi$ bricks. He stacks them, one on top of another, to form a tower six bricks high. Each brick can be in any orientation so long as it rests flat on top of the next brick below it (or on the floor). How many distinct heights of towers can he make?

Find the smallest integer $n$ such that $\sqrt{n+99}-\sqrt{n}<1$.

Find the shortest distance from the line $3 x+4 y=25$ to the circle $x^{2}+y^{2}=6 x-8 y$.

I have chosen five of the numbers $\{1,2,3,4,5,6,7\}$. If I told you what their product was, that would not be enough information for you to figure out whether their sum was even or odd. What is their product?

A positive integer $n$ is picante if $n$ ! ends in the same number of zeroes whether written in base 7 or in base 8 . How many of the numbers $1,2, \ldots, 2004$ are picante?

Let $f(x)=x^{2}+x^{4}+x^{6}+x^{8}+\cdots$, for all real $x$ such that the sum converges. For how many real numbers $x$ does $f(x)=x$ ?

Find all numbers $n$ with the following property: there is exactly one set of 8 different positive integers whose sum is $n$.

A convex quadrilateral is drawn in the coordinate plane such that each of its vertices $(x, y)$ satisfies the equations $x^{2}+y^{2}=73$ and $x y=24$. What is the area of this quadrilateral?

Find all positive integer solutions $(m, n)$ to the following equation:

$$m^{2}=1!+2!+\cdots+n!.$$

If $a_{1}=1, a_{2}=0$, and $a_{n+1}=a_{n}+\frac{a_{n+2}}{2}$ for all $n \geq 1$, compute $a_{2004}$.

A regular decagon $A_{0} A_{1} A_{2} \cdots A_{9}$ is given in the plane. Compute $\angle A_{0} A_{3} A_{7}$ in degrees.

An $n$-string is a string of digits formed by writing the numbers $1,2, \ldots, n$ in some order (in base ten). For example, one possible 10-string is

35728910461 What is the smallest $n>1$ such that there exists a palindromic $n$-string?

Kate has four red socks and four blue socks. If she randomly divides these eight socks into four pairs, what is the probability that none of the pairs will be mismatched? That is, what is the probability that each pair will consist either of two red socks or of two blue socks?

On a spherical planet with diameter $10,000 \mathrm{~km}$, powerful explosives are placed at the north and south poles. The explosives are designed to vaporize all matter within $5,000 \mathrm{~km}$ of ground zero and leave anything beyond $5,000 \mathrm{~km}$ untouched. After the explosives are set off, what is the new surface area of the planet, in square kilometers?

The Fibonacci numbers are defined by $F_{1}=F_{2}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ for $n \geq 3$. If the number

$$\frac{F_{2003}}{F_{2002}}-\frac{F_{2004}}{F_{2003}}$$

is written as a fraction in lowest terms, what is the numerator?

Two positive rational numbers $x$ and $y$, when written in lowest terms, have the property that the sum of their numerators is 9 and the sum of their denominators is 10 . What is the largest possible value of $x+y$ ?

Find all ordered pairs of integers $(x, y)$ such that $3^{x} 4^{y}=2^{x+y}+2^{2(x+y)-1}$.

I have written a strictly increasing sequence of six positive integers, such that each number (besides the first) is a multiple of the one before it, and the sum of all six numbers is 79 . What is the largest number in my sequence?

Find the largest integer $n$ such that $3^{512}-1$ is divisible by $2^{n}$.

We say a point is contained in a square if it is in its interior or on its boundary. Three unit squares are given in the plane such that there is a point contained in all three. Furthermore, three points $A, B, C$, are given, each contained in at least one of the squares. Find the maximum area of triangle $A B C$.

Suppose $x^{3}-a x^{2}+b x-48$ is a polynomial with three positive roots $p, q$, and $r$ such that $p<q<r$. What is the minimum possible value of $1 / p+2 / q+3 / r$ ?

How many of the integers $1,2, \ldots, 2004$ can be represented as $(m n+1) /(m+n)$ for positive integers $m$ and $n$ ?

A regular hexagon has one side along the diameter of a semicircle, and the two opposite vertices on the semicircle. Find the area of the hexagon if the diameter of the semicircle is 1 .

Find the value of

$$\binom{2003}{1}+\binom{2003}{4}+\binom{2003}{7}+\cdots+\binom{2003}{2002}$$

A regular dodecahedron is projected orthogonally onto a plane, and its image is an $n$-sided polygon. What is the smallest possible value of $n$ ?

We have an $n$-gon, and each of its vertices is labeled with a number from the set $\{1, \ldots, 10\}$. We know that for any pair of distinct numbers from this set there is at least one side of the polygon whose endpoints have these two numbers. Find the smallest possible value of $n$.

$P$ is a point inside triangle $A B C$, and lines $A P, B P, C P$ intersect the opposite sides $B C, C A, A B$ in points $D, E, F$, respectively. It is given that $\angle A P B=90^{\circ}$, and that $A C=B C$ and $A B=B D$. We also know that $B F=1$, and that $B C=999$. Find $A F$.

Define the sequence $b_{0}, b_{1}, \ldots, b_{59}$ by

$$b_{i}= \begin{cases}1 & \text { if } \mathrm{i} \text { is a multiple of } 3 \\ 0 & \text { otherwise }\end{cases}$$

Let $\left\{a_{i}\right\}$ be a sequence of elements of $\{0,1\}$ such that

$$b_{n} \equiv a_{n-1}+a_{n}+a_{n+1} (\bmod 2)$$

for $0 \leq n \leq 59\left(a_{0}=a_{60}\right.$ and $\left.a_{-1}=a_{59}\right)$. Find all possible values of $4 a_{0}+2 a_{1}+a_{2}$.

A plane $P$ slices through a cube of volume 1 with a cross-section in the shape of a regular hexagon. This cube also has an inscribed sphere, whose intersection with $P$ is a circle. What is the area of the region inside the regular hexagon but outside the circle?

Find the number of 20 -tuples of integers $x_{1}, \ldots, x_{10}, y_{1}, \ldots, y_{10}$ with the following properties:

• $1 \leq x_{i} \leq 10$ and $1 \leq y_{i} \leq 10$ for each $i$;
• $x_{i} \leq x_{i+1}$ for $i=1, \ldots, 9$;
• if $x_{i}=x_{i+1}$, then $y_{i} \leq y_{i+1}$.

There are eleven positive integers $n$ such that there exists a convex polygon with $n$ sides whose angles, in degrees, are unequal integers that are in arithmetic progression. Find the sum of these values of $n$.

For a string of $P$ 's and $Q$ 's, the value is defined to be the product of the positions of the $P$ 's. For example, the string $P P Q P Q Q$ has value $1 \cdot 2 \cdot 4=8$. Also, a string is called antipalindromic if writing it backwards, then turning all the $P$ 's into $Q$ 's and vice versa, produces the original string. For example, $P P Q P Q Q$ is antipalindromic. There are $2^{1002}$ antipalindromic strings of length 2004. Find the sum of the reciprocals of their values.

Simplify $\prod_{k=1}^{2004} \sin (2 \pi k / 4009)$.

Let $S=\left\{p_{1} p_{2} \cdots p_{n} \mid p_{1}, p_{2}, \ldots, p_{n}\right.$ are distinct primes and $\left.p_{1}, \ldots, p_{n}<30\right\}$. Assume 1 is in $S$. Let $a_{1}$ be an element of $S$. We define, for all positive integers $n$ :

$$\begin{gathered} a_{n+1}=a_{n} /(n+1) \text { if } a_{n} \text { is divisible by } n+1 \\ a_{n+1}=(n+2) a_{n} \\ \text { if } a_{n} \text { is not divisible by } n+1 \end{gathered}$$

How many distinct possible values of $a_{1}$ are there such that $a_{j}=a_{1}$ for infinitely many $j$ 's?

You want to arrange the numbers $1,2,3, \ldots, 25$ in a sequence with the following property: if $n$ is divisible by $m$, then the $n$th number is divisible by the $m$ th number. How many such sequences are there?

You would like to provide airline service to the 10 cities in the nation of Schizophrenia, by instituting a certain number of two-way routes between cities. Unfortunately, the government is about to divide Schizophrenia into two warring countries of five cities each, and you don't know which cities will be in each new country. All airplane service between the two new countries will be discontinued. However, you want to make sure that you set up your routes so that, for any two cities in the same new country, it will be possible to get from one city to the other (without leaving the country). What is the minimum number of routes you must set up to be assured of doing this, no matter how the government divides up the country?

A tetrahedron has all its faces triangles with sides $13,14,15$. What is its volume?

$S$ is a set of complex numbers such that if $u, v \in S$, then $u v \in S$ and $u^{2}+v^{2} \in S$. Suppose that the number $N$ of elements of $S$ with absolute value at most 1 is finite. What is the largest possible value of $N$ ?

Write down an integer from 0 to 20 inclusive. This problem will be scored as follows: if $N$ is the second-largest number from among the responses submitted, then each team that submits $N$ gets $N$ points, and everyone else gets zero. (If every team picks the same number then nobody gets any points.)

Shown on your answer sheet is a $20 \times 20$ grid. Place as many queens as you can so that each of them attacks at most one other queen. (A queen is a chess piece that can move any number of squares horizontally, vertically, or diagonally.) It's not very hard to get 20 queens, so you get no points for that, but you get 5 points for each further queen beyond 20 . You can mark the grid by placing a dot in each square that contains a queen.

A binary string of length $n$ is a sequence of $n$ digits, each of which is 0 or 1 . The distance between two binary strings of the same length is the number of positions in which they disagree; for example, the distance between the strings 01101011 and 00101110 is 3 since they differ in the second, sixth, and eighth positions. Find as many binary strings of length 8 as you can, such that the distance between any two of them is at least 3 . You get one point per string.