\input amstex
\input epsfx
\hyphenation{Mass-achusetts Central Missouri Wis-con-sin Muthuvel}
\raggedbottom
\loadmsam
\loadmsbm
\loadeufm
\def\R{\Bbb R}
\def\Z{\Bbb Z}
\def\Q{\Bbb Q}
\def\C{\Bbb C}
\def\N{\Bbb N}
\tolerance=1600
\hsize=33pc
\vsize=42pc
\baselineskip=12pt
\lineskip=12pt
\centerline{\bf 2002 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session I}
\bigskip
1.  Let $P \ne (0,0)$ be a point on the parabola $y=x^2$.  The normal 
line to the parabola at $P$ will intersect the parabola at another point, 
say $Q$.  Find the coordinates of $P$ so that the average of the 
$y$-coordinates of $P$ and $Q$ is a minimum. 
\bigskip
Solution.
\medskip
Let $P = (p,p^2)$ and $Q = (q,q^2)$.  The slope of the tangent line to 
the parabola at $P$ is $2p$, so the slope of the normal line to the 
parabola at $P$ is $-1/2p$.  Thus, the equation of the normal line to 
the parabola at $P$ is
$$y - p^2 = -{1 \over 2p} (x - p) .$$
Since $Q = (q,q^2)$ lies on the normal line,
$$q^2 - p^2 = - {1 \over 2p} (q-p)\ \ \text{or}\ \ q + p = - {1 \over  
2p} .$$
Solving for $q$, we obtain
$$q = -p - {1 \over 2p} .$$
Now the average of the $y$-coordinates of $P$ and $Q$ is
$$A = {p^2 + q^2 \over 2} = {p^2 + (-p - 1/2p)^2 \over 2} = p^2 + 
{1 \over 2} + {1 \over 8p^2} .$$
Differentiating this quantity with respect to $p$, we obtain
$${dA \over dp} = 2p - {1 \over 4p^3} = {1 \over 4p^3} (8p^4 - 1) 
.$$
Setting this quantity equal to 0, we arrive at
$$p = 2^{-3/4} .$$
Therefore, the coordinates of $P$ so that the average of the 
$y$-coordinates of $P$ and $Q$ is a minimum are $(2^{-3/4}, 
2^{-3/2})$.
\bigskip
From {\it Mathematical Gems II} by Ross Honsberger, Dolciani 
Mathematical Exposition, 1976, pp. 90--97.
\medskip
2.  A tetrahedron is called {\it isosceles} if the members of each 
pair of opposite edges are equal.  This means, for tetrahedron 
$ABCD$, that $AB = CD$, $BC = AD$, and $AC = BD$.
\medskip
\item{(a)}  Prove that all four faces of an isosceles tetrahedron 
are congruent.
\item{(b)}  Prove that if all four faces of a tetrahedron have the 
same perimeter, then the tetrahedron is isosceles.
\item{(c)}  Prove that a tetrahedron is isosceles if and only if 
the sum of the face angles at each vertex is $180^\circ$. 
$$\epsfxsize=10pc \epsfbox{smaa0206.eps}$$
\bigskip
Solution.
\medskip
\item{(a)} Side-Side-Side
\item{(b)} Denote opposite edges by $a$, $a'$, $b$, $b'$, and $c$, $c'$. 
Then from equal perimeters,
$$a+b+c = a+b'+c' = a'+b+c' = a'+b'+c$$
Eliminate $a$ from the first two equations and $a'$ from the last two.  
Solve each resulting equation for $b-b'$, giving $c-c' = c'-c$, which 
means $c=c'$.  Similarly, $a=a'$ and $b=b'$.  Thus the tetrahedron is 
isosceles.
\item{(c)} Imagine cutting $ABCD$ along the three edges that meet at $D$ 
and flattening the tetrahedron out.  This gives a hexagon $AD_1BD_2CD_3$. 
$$\epsfxsize=10pc \epsfbox{smaa0201.eps}$$
Assume the sum of the face angles at each vertex is $180^\circ$.  Then 
in the hexagon the angles at $A$, $B$, and $C$ are each straight 
angles, making the hexagon really a triangle $D_1D_2D_3$ with $A$, $B$, 
and $C$ as the midpoints of the sides.  Thus, $AB = CD_2 = CD_3$, etc. 
and the tetrahedron is isosceles.

Assume the tetrahedron is isosceles.  Then the faces are congruent, and 
so the face angles at a vertex are the same as the angles in a face 
triangle, which sum to $180^\circ$.
\bigskip
3.  Let $\{ x_n \}$ be the following sequence involving alternating 
square roots of 5 and 13:
$$x_1 = \sqrt 5,\ \ x_2 = \sqrt {5 + \sqrt {13}},\ \ x_3 = \sqrt {5 + 
\sqrt {13 + \sqrt 5}},\ \ x_4 = \sqrt {5 + \sqrt {13 + \sqrt {5 + 
\sqrt {13}}}},$$
and so on.  Prove that $\lim_{n \to \infty} x_n$ exists and determine its value.
\bigskip
Solution.
\medskip
We see that $x_1, x_2 < 4$;  assume also that $x_{2k-1}, x_{2k} < 4$. 
Then,
$$x_{2k+2} = \sqrt {5 + \sqrt {13 + x_{2k}}} < \sqrt {5 + \sqrt {13 + 
4}} < 4 .$$
The argument is identical for $x_{2k+1}$.  Hence, for each $n$, $x_n < 
4$ by mathematical induction on $n$.  In addition, the sequence 
increases monotonically.  Therefore, by a standard limit theorem on sequences
$$\lim_{n \to \infty} x_n$$
must exist.

Let
$$L = \lim_{n \to \infty} x_n .$$
Then we have
$$L = \sqrt{ 5 + \sqrt {13 + L} }$$
or
$$L^4 - 10L^2 - L + 12 = 0.$$
One root is $L=3$.  Of the three remaining roots, one is positive (between 1 and 2) and the other two are complex.  It follows that
$$\lim_{n \to \infty} x_n = 3 .$$
Convergence is fairly rapid; $x_6$ is already $2.999971$.
\bigskip
From {\it From Erd\H{o}s to Kiev} by Ross Honsberger, Dolciani 
Mathematical Exposition, 1995, pp. 177--179.
\medskip
4.  Does the set $X = \{ 1, 2, \ldots , 3000 \}$ contain a subset $A$ 
of 2000 integers in which no member of $A$ is twice another member of 
$A$?   
\bigskip
Solution.
\medskip
Since twice any integer in the interval $P = [1501, 3000]$ is too big 
to belong to $X$, we could put these 1500 integers in $A$ without 
worrying about doubling up on any of them.  On the other hand, $A$ 
certainly can't get more than 1500 integers from $P$ since it only 
has 1500 altogether.  Obviously, we have to be careful not to pick 
any integer in the interval $Q = [751, 1500]$ which is one-half an 
integer that is chosen from $P$.  Clearly, each integer taken from 
$Q$ negates the eligibility of its double in $P$, and it follows 
that, if $k$ integers are taken from $Q$, then not more than $1500-k$ 
can be selected from $P$, for a total of not more than 1500 
altogether from the entire interval $Q \cup P = [751, 3000]$.  Thus, 
in order to build up to 2000 integers in $A$, at least 500 must come 
from $[1, 750]$, the initial quarter of $X$.
$$\epsfxsize=15pc \epsfbox{smaa0202.eps}$$
Repeated applications of this reasoning give the following results.
In order to build up to 2000 integers in $A$, at least 125 must come 
from $[1, 187]$; at least 31 must come from $[1, 46]$; at least 8
from $[1, 11]$; and at least 2 from $[1, 2]$.
\vfill\eject
$$\epsfxsize=30pc \epsfbox{smaa0203.eps}$$
However, the proposal is not outrageous, for clearly $A$ can be built 
up to
$$1500 + 375 + 94 + 23 + 6 + 1 = 1999 \ \ \ \text{integers.}$$

This suggests that two-thirds the number of integers in $X$ is a 
sharp cut-off point for the size of $A$, that is, that $\vert A 
\vert$ can be any number up to two-thirds the size of $X$, but not 
actually as big as ${2 \over 3} \vert X \vert$.  Applying our 
analysis to $X = \{ 1, 2, \ldots , 300 \}$, however, reveals that 
$A$ can have as many as 200 members:
$$A = \{ \underbrace{1, 3, 4}_3;\ \ \underbrace{10, 11, \ldots , 
18}_{+9};\ \ \underbrace{38, 39, \ldots , 75}_{+ 38};\ \ 
\underbrace{151, 152, \ldots , 300}_{+ 150 = 200.} \} .$$
But, this set is as fully packed as possible, suggesting that the 
general result is rather $\vert A \vert \le {2 \over 3} \vert X \vert $.
\medskip
From the above procedure, we can obtain the recursive formula
$$\vert A(N) \vert = \bigg\lceil {N \over 2} \bigg\rceil + \bigg\vert A \biggl( \bigg\lfloor {N \over 4} \bigg\rfloor \biggr) \bigg\vert ,$$
where $\vert \cdot \vert$ denotes the number of elements in a set and $A(N)$ is a subset of $X = \{ 1, 2, \ldots , N \}$ with the no doubling property and having the largest number of elements.
\medskip
Bruce Resnick (University of Illinois at Urbana-Champaign) has recently found the following pretty formula for the maximum size $f_r (n)$ of a subset of $\{ 1, 2, \ldots , n \}$ in which no element is $r$ times another.  Converting $n$ to its representation in base $r$,
$$n = a_m a_{m-1} \cdots a_0 ,$$
then
$$f_r (n) = {1 \over r+1} \biggl( rn + \sum_{k=0}^m (-1)^k a_k \biggr) .$$
\bigskip
5.  Two right circular cylinders of radius $r$ intersect at right 
angles to form a solid.  This solid has four curved faces.  Imagine 
one of these faces ``rolled out flat''.  Find equations of the 
boundary curves of this flattened face and also find its area. 
\bigskip
Solution.
\medskip
Let the $x$-axis be the axis of one cylinder and the $y$-axis be the 
axis of the other cylinder so that the center of the sold is the 
origin.  Cross-sections perpendicular to the $z$-axis are squares 
with side $s = 2 \sqrt {r^2 - z^2}$.  Place the flattened face with 
its axis of symmetry on the horizontal axis, call it the $w$-axis, 
with the left end of the figure at the origin.  This makes the range 
of $w$ the interval $0 \le w \le \pi r$, and the distance from the 
$w$--axis to the top boundary curve is $\sqrt {r^2 - z^2}$.  To 
relate $z$ and $w$, note that if $\theta$ is the angle through which 
the solid has rolled, then $\cos \theta = z/r$ and $w = r \theta$, 
yielding
$$\sqrt {r^2 - z^2} = r \sin {w \over r} .$$
The boundary curves, then are
$$f(w) = r \sin {w \over r}\ \ \text{and}\ \ g(w) = -r \sin {w \over 
r} .$$
The area is given by a simple integral:
$$\text{area} = \int_0^{\pi r} 2r \sin {w \over r} dw = 4r^2 .$$
This solid and its circumscribed cube have the same properties that 
Archimedes admired concerning the sphere and its circumscribed 
cylinder, namely, both the volumes and the surface areas are in the 
ratio $2:3$.
\vfill\eject
\centerline{\bf 2002 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
\bigskip
1. Seven golf balls, labeled 1 through 7, are correctly placed in 
corresponding boxes (one to a box), also labeled 1 through 7.  The 
balls are now removed and then randomly returned to the boxes, one 
ball to a box.  What is the probability that no ball will find its 
correct box? 
\bigskip
Solution.
\medskip
Let $W_n$ denote the number of ways that $n$ golf balls can be returned 
to $n$ boxes with no ball finding its correct home.  Suppose box 1 
contains ball $N$ ($N \ne 1$).  There are then two cases.
\medskip
CASE 1.  Box $N$ contains ball 1.  Hence, the remaining $n-2$ balls are 
to be distributed among $n-2$ boxes, with no ball finding its correct 
home.  There are $W_{n-2}$ ways for this.

CASE 2.  Box $N$ doesn't contain ball 1.  Then $n-1$ balls are to be 
similarly distributed among $n-1$ boxes; there are $W_{n-1}$ ways here.
\medskip
Since the choice of box 1 was arbitrary among the $n-1$ balls $2$, 
$3$, $\ldots$, $n$, the total number of ways is
$$W_n = (n-1) (W_{n-2} + W_{n-1}) .$$
We have, clearly, $W_1 = 0$ and $W_2 = 1$.  The recursion formula then 
gives, successively, $W_3 = 2$, $W_4 = 9$, $W_5 = 44$, $W_6 = 265$, and 
finally $W_7 = 1854$.  But the number of permutations of 7 balls in 7 
boxes is $7! = 5040$, so the desired probability is
$$P_7 = {W_7 \over 7!} = {1854 \over 5040} = {103 \over 280} = 0.3679.$$
\bigskip
2.  
\item{(a)}  Prove that, for any positive integer $n$,
$$\sin n\theta = {n \choose 1} \sin \theta \cos ^{n-1} \theta - {n 
\choose 3} \sin ^3 \theta \cos ^{n-3} \theta + {n \choose 5} \sin ^5 
\theta \cos ^{n-5} \theta - \cdots$$
and
$$\cos n\theta = \cos ^n \theta - {n \choose 2} \sin ^2 \theta \cos 
^{n-2} \theta + {n \choose 4} \sin ^4 \theta \cos ^{n-4} \theta - 
\cdots .$$
\item{(b)}  Prove that, for all $x$ in the interval $[-1,1]$ and any positive integer $n$, the 
function
$$T_n (x) = \cos (n \cos ^{-1} x)$$
is a polynomial in $x$ of degree $n$ and leading coefficient $2^{n-1}$.
\bigskip
Solution.
\medskip
For part (a), from DeMoivre's Theorem
$$(\cos \theta + i \sin \theta )^n = \cos n\theta + i \sin n \theta ,$$
we expand the left side using the binomial theorem and equate real and imaginary parts.

For part (b), use part (a) with $\theta = \cos ^{-1} x$, $\cos 
\theta = x$, and $\sin \theta = \sqrt {1 - x^2}$ to get
$$\cos (n \cos ^{-1} x) = x^n - {n \choose 2} (1-x^2) x^{n-2} + {n 
\choose 4} (1-x^2)^2 x^{n-4} - \cdots .$$
It is clear that $T_n (x)$ is a polynomial of degree $n$, and that 
the leading coefficient is
$$1 + {n \choose 2} + {n \choose 4} + \cdots + {n \choose 2k}$$
where
$$2k = \cases n,&\text{if $n$ is even}\\
              n-1,&\text{if $n$ is odd}. \endcases$$
Now, since
$$2^n = (1+1)^n = 1 + {n \choose 1} + {n \choose 2} + \cdots + {n 
\choose n}$$
and
$$0 = (1-1)^n = 1 - {n \choose 1} + {n \choose 2} - \cdots + (-1)^n 
{n \choose n}$$
we can add and get the leading coefficient above equal to $2^{n-1}$.
\bigskip
From {\it Mathematical Gems II} by Ross Honsberger, Dolciani 
Mathematical Exposition, 1976, pp. 18--20.
\medskip
3. Suppose three equal circles, each of radius $r$, pass through a 
common point $O$ and have three other pairwise intersections at $P_1$, 
$P_2$, and $P_3$.  Prove that the circle containing $P_1$, $P_2$, and 
$P_3$ also has radius $r$.  
\bigskip
Solution.
\medskip
\comment
Let $C_1$, $C_2$, and $C_3$ be the centers of the circles.  Label the 
figure so the $C_i$ and $P_i$ are in the order $P_1$, $C_1$, $P_2$, 
$C_2$, $P_3$, $C_3$ in the counterclockwise direction.  Connect those 
points in that order, and draw $OC_i$ for $i=1, 2, 3$.  Three rhombi 
are formed.  $C_2 P_3$ and $C_1 P_1$ are thus equal and parallel, 
from which we get $C_1 C_2$ equal and parallel to $P_1 P_3$.  
Similarly, $C_2 C_3$ and $P_1 P_2$ are equal and parallel as are $C_1 
C_3$ and $P_2 P_3$.  Thus, triangles $C_1 C_2 C_3$ and $P_1 P_2 P_3$ 
are congruent.  The circumcircle of $C_1 C_2 C_3$ has center $O$ and 
radius $r$, and thus, the circumcircle of $P_1 P_2 P_3$ also has 
radius $r$.
\endcomment
Label the three circles 1, 2, 3, with centers $C_1$, $C_2$, $C_3$, respectively.  Denote the point of intersection common only to circles $i$ and $j$ as $P_k$, $i,j,k = 1,2,3$, $i \ne j \ne k$.  The circle through points $C_1$, $C_2$, $C_3$ has center $O$ and radius $r$ since the distance from $O$ to each $C_i$ is $r$.

$C_1 O C_2 P_3$, $C_1 O C_3 P_2$, and $C_2 O C_3 P_1$ are rhombi whose all four sides are equal to $r$.  Thus, $C_1 P_3$ and $O C_2$ are equal and parallel, as are $O C_2$ and $C_3 P_1$.  This implies $C_1 P_3$ and $C_3 P_1$ are equal and parallel, so that $C_1 P_3 P_1 C_3$ is a parallelogram, and thus, $C_1 C_3$ and $P_1 P_3$ are equal and parallel.  Similarly, $C_1 C_2$ and $P_1 P_2$, as well as $C_2 C_3$ and $P_2 P_3$, are equal and parallel.

Therefore, $\triangle C_1 C_2 C_3$ and $\triangle P_1 P_2 P_3$ are congruent which implies the circumcircles of each are equal, and each circle has radius $r$.
$$\epsfxsize=15pc \epsfbox{smaa0204.eps}$$
\medskip
4. $ABCDE$ is a regular pentagon of side $s$, and $P$ is any point in 
the interior of $ABCDE$.  Line segments are drawn from $P$ 
perpendicular to each of the five sides.  Denote the sum of the 
lengths of these five perpendiculars by $S$.  Prove that $S$ is 
independent of the location of $P$, and find $S$ in terms of $s$.   
\vfill\eject
Solution.
\medskip
Let $P$ be an arbitrary point in the interior.  Then
$$\text{area} \ \triangle PAB = {1 \over 2} \cdot s \cdot h_1,$$
where $h_1$ is the length of the perpendicular from $P$ to $AB$.  
Similarly,
$$\text{area} \ \triangle PBC = {1 \over 2} \cdot s \cdot h_2,$$
where $h_2$ is the length of the perpendicular from $P$ to $BC$.  
Continue this process for $\triangle PCD$, $\triangle PDE$ and 
$\triangle PEA$.  The sum of the areas of these triangles is the 
area of the pentagon, that is,
$${1 \over 2} s (h_1 + h_2 + h_3 + h_4 + h_5) = \text{area of 
pentagon} .$$
Therefore,
$$S = h_1 + h_2 + h_3 + h_4 + h_5$$
is independent of the position of $P$ because $P$ was arbitrary.
$$\epsfxsize=15pc \epsfbox{smaa0205.eps}$$
To compute $S$, let $P = O = 
\text{center of the pentagon}$.  Let $L$ be the point on side $AB$ 
so that $OL$ is perpendicular to side $AB$.  Then $S = 0.5 L$ and
$$\eqalign{
&\angle AOB = 72^\circ ,\ \ \ \ \ \angle AOL = 36^\circ, \ \ \ \ \ 
{AL \over OL} = \tan 36^\circ ,\cr
&AL = OL \tan 36^\circ ,\ \ \ \ \ OL = AL \cot 36^\circ = {s \over 
2} \cot 36^\circ .\cr}$$
Therefore,
$$S = 5 OL = s \biggl( {5 \over 2} \cot 36^\circ \biggr) .$$
\bigskip
From the 1980 All-Union Russian Olympiad. 
\medskip
5. Let $p(n)$ denote the product of the (decimal) digits of the 
positive integer $n$.  Consider the sequences, beginning at any 
arbitrary positive integer, in which succeeding terms are obtained by 
adding to the previous term the product of its digits:
$$n_0 = n,\ \ \text{and for}\ \ r \ge 0,\ \ n_{r+1} = n_r + p(n_r).$$
Is there an initial integer $n$ for which the sequence continues to 
increase indefinitely?   
\bigskip
Solution.
\medskip
The answer is no.

Note that a digit equal to zero anywhere in $n_r$ results in $p(n_r) = 0$, 
leading to $n_{r+1} = n_r$ and to $n_r$ repeating indefinitely; otherwise, 
$p(n_r)$ is positive and the sequence increases.

The list of consecutive numbers containing a 0 at the beginning of the set 
of integers that contain a given number of digits is
$$\eqalign{
&\{ 100, 101, \ldots , 109 \} \cr
&\{ 1000, 1001, \ldots , 1099 \} .\cr}$$
In general, for $k \ge 3$, the $k$-digit integers begin with $10^{k-2}$ 
consecutive numbers containing a 0 (actually there are more than this but 
we do not need greater accuracy).  Now if $p(n_r)$ were to increase $n_r$ 
to any value in this initial segment of $k$-digit numbers containing a 0, 
the sequence would never get any bigger.

For a $(k-1)$-digit number $n_r$, $p(n_r)$ cannot exceed $9^{k-1}$.  If it 
should ever happen that the initial segment of $10^{k-2}$ $k$-digit 
numbers containing a 0 were too great for $p(n_r)$ to get over, that is, 
if ever $10^{k-2} > 9^{k-1}$, then all sequences with terms containing 
$k-1$ or fewer digits could never muster the increment necessary to reach 
any $k$-digit integer that did not contain a zero -- those that managed to 
survive to the $k$-digit level would remain in one of our $10^{k-2}$ 
consecutive $k$-digit integers containing a 0.  Starting with
$$10^{k-2} > 9^{k-1}$$
and taking logs, we see that
$$\eqalign{
&k-2 > (k-1) \log 9 \cr
k &> {2 - \log 9 \over 1 - \log 9} \doteq 22.85 .\cr}$$
Thus, no sequence that starts below 23-digit numbers can survive beyond 
our $10^{21}$ consecutive 23-digit integers containing a 0, and sequences 
that start at $m \ge 23$-digit numbers cannot get past the first 
$10^{m-1}$ integers with $m+1$ digits.
\bye 