\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