%Format: AMS TeX
\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}
\newbox\newnewfbox
\newdimen\newnewfw
\font\newnewfa=newnewfa at 72.27truept
\setbox\newnewfbox=\vbox{\hbox{%
\newnewfa\char0\char1\char2}}
\newnewfw=\wd\newnewfbox
\setbox\newnewfbox=\hbox{\vbox{\hsize=\newnewfw
\parskip=0pt\offinterlineskip\parindent0pt
\hbox{\newnewfa\char0\char1\char2}
\hbox{\newnewfa\char3\char4\char5}
\hbox{\newnewfa\char6\char7\char8}}}
\ifx\parbox\undefined
\def\setnewnewf{\box\newnewfbox}
\else
\def\setnewnewf{\parbox{\wd\newnewfbox}{\box\newnewfbox}}
\fi
\tolerance=1600
\hsize=33pc
\vsize=42pc
\baselineskip=12pt
\lineskip=12pt
\centerline{\bf 1999 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 length of the arc
of the parabola between $P$ and $Q$ is a minimum.
\bigskip
Solution.
\smallskip
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) .$$
Hence, the other intersection point of the normal line and the
parabola, $Q$ has the $x$-coordinate
$$q = -p - {1 \over 2p} .$$
Now the length of the arc of the parabola between $P$ and $Q$ is
$$L = \int_{-p-1/(2p)}^p \sqrt {1 + (2x)^2} dx .$$
Differentiating $L$ with respect to $p$ gives
$${dL \over dp} = \sqrt {1 + 4p^2} - \biggl( -1 + {1 \over 2p^2} \biggr)
\sqrt {1 + 4 \biggl( -p - {1 \over 2p} \biggr)^2 }$$
and setting the derivative equal to 0 gives
$$\sqrt {1 + 4p^2} = \biggl( {1 \over 2p^2} - 1 \biggr) \sqrt {4p^2 + 5
+ {1 \over p^2} } .$$
Squaring both sides to remove the radicals and multiplying by $p^4$, we
obtain
$$12p^4 - p^2 - 1 = (4p^2 + 1)(3p^2 - 1) = 0.$$
Hence, the coordinates of $p$ resulting in a minimum arc length are
$$\biggl( \pm \sqrt {1 \over 3} , {1 \over 3} \biggr) .$$
\bigskip
2. Give a precise characterization of those points in the plane which do
$\underline{\text{not}}$ lie on a tangent line to the curve $y = x^4 -
6x^2$.
\bigskip
Solution.
\smallskip
Given a point $( t , t^4 - 6t^2 )$ on the curve, the equation of the
tangent line at that point is $y = (4 t^3 - 12 t ) x - (3 t^4 - 6 t^2
)$. For a fixed value of $x$, as $t$ varies, the maximum value of $y$
will occur when
$${dy \over dt} = (12 t^2 - 12) x - (12 t^3 - 12 t ) = 0 .$$
This polynomial factors as $(12 t^2 - 12) (x - t)$, so the
critical values occur at $t = 1, -1, x$. The corresponding $y$
values are $-8x + 3$, $8x + 3$, and $x^4 - 6x^2$ and a point $(x, y)$
will $\underline{\text{not}}$ lie on any tangent line if the $y$
coordinate is greater than the maximum of these three quantities.
More specifically, the set of points which lie on no tangent line to
the curve is $\{ (x,y) \ \vert \ \vert x \vert > 3 \text{ and } y >
x^4 - 6x^2, \text{ or } \ \vert x \vert \le 3, \text{ and } y > 8 \vert
x \vert + 3 \}$.
\smallskip
Note that $y = \pm 8 x + 3$ are the tangent lines at the points of
inflection, $( \mp 1, -5 )$, and that $( \pm 3, 27)$ are where these
tangents intersect the quartic.
\vfill\eject
From {\it Scientific American}, June 1975, pp. 106--107.
\smallskip
3. On a $5 \times 5$ square matrix place 13 black counters and 12
white counters in alternating checkerboard fashion. Remove the black
counter in the center square. Player A controls the white counters
and B the black. They take turns moving one of their counters
orthogonally to the vacant square until a player loses by being unable
to move. Which player has a winning strategy? What is the strategy?
\bigskip
Solution.
\smallskip
This game was invented in the late 1960's by G. W. Lewthwaite of
Scotland. Player B has a winning strategy. B's strategy is to
imagine that the matrix, except for the center square, is covered by
12 nonoverlapping dominoes.
\medskip
\centerline{\setnewnewf}
\medskip
Whenever A moves, B simply moves his counter that is on the domino A
has just vacated. Since this ensures that B always has a move to
follow a move by A, B is sure to win in 12 or fewer moves. If the
board is colored like a checkerboard, it is obvious that on each move
a counter goes to a square of a different color and that no counter
can be moved twice. The game therefore cannot go beyond 12 moves for
each player.
\vfill\eject
Modified Proposal by Viktors Linis, University of Ottawa,
Ottawa, Canada, Problem 162, {\it Crux Mathematicorum}, 2 (1976),
226--228.
From a list of problems submitted for the 1975 Canadian Mathematics
Olympiad (but not used on the actual exam). This solution is adapted
from solutions submitted independently by John L. Davison, Laurentian
University, Sudbury, Ontario and Dan Eustice, Ohio State University,
Columbus, Ohio.
\smallskip
4. If $x_0 = 5$ and $x_{n+1} = x_n + 1/x_n$, prove that for
all $n \ge 1$
$$2n < x_n ^2 - 25 < 47n/23 .$$
\bigskip
Solution.
\smallskip
%Since $x_{n+1} = x_n + 1/x_n$, it follows that
%$$x_{n+1}^2 = x_n ^2 + 2 + {1 \over x_n ^2} ,\eqno(1)$$
%and so $x_{n+1}^2 > x_n ^2 + 2$. Thus $x_1 ^2 > 27$, $x_2 ^2 > 29$,
%and by induction
%$$x_n^2 > 2n + 25 ,\text{ for } n = 1, 2, \ldots .\eqno(2)$$
%On the other hand, for $n \ge 1$ we get from (1) and (2)
%$$x_{n+1}^2 < x_n^2 + 2 + {1 \over 2n+25} .\eqno(3)$$
%If we sum the $n$ relations obtained by setting $n=0$ in (1) and
%replacing $n$ successively by $1, 2, \ldots , n-1$ in (3), we get
%$$x_n^2 < 2n + 25 + \sum_{k=0}^{n-1} {1 \over 2k+25} .$$
%Now
%$$\sum_{k=0}^{n-1} {1 \over 2k+25} < \int _{-1}^{n-1} {dx \over 2x+25}
%= {1 \over 2} \ln \biggl( {2n + 23 \over 23} \biggr) .\eqno(4)$$
%We know that $\ln (1+x) < x$. Hence
%$${1 \over 2} \ln \biggl( {2n + 23 \over 23} \biggr) < {1 \over 2}
%\cdot {2n \over 23} = {n \over 23} .$$
%Therefore, for $n \ge 1$,
%$$x_n ^2 < 2n + 25 + {n \over 23} = 25 + {47n \over 23} .$$
%The inequalities follow.
The proof of the result is by induction on $n$. The theorem is trivially
true for $n=1$ since $2 < (5.2)^2 - 25 < 47/23$. Assume it is true for
$n=k$. Then, on the one hand
$$\eqalign{
x_{k+1}^2 - 25 &= \biggl( x_k + {1 \over x_k} \biggr)^2 - 25 = (x_k^2 -
25) + 2 + {1 \over x_k^2} \cr
&> 2k + 2 + {1 \over x_k^2} = 2(k+1) + {1 \over x_k^2} > 2(k+1) ,\cr}$$
while on the other hand
$$\eqalign{
x_{k+1}^2 - 25 &= [ (x_k^2 - 25) + 2] + {1 \over x_k^2} < \biggl( {47k
\over 23} + {47 \over 23} \biggr) + \biggl( {1 \over x_k^2} - {1 \over
23} \biggr) \cr
&= {47(k+1) \over 23} - \biggl( {x_k^2 - 23 \over 23 x_k^2} \biggr) <
{47(k+1) \over 23} .\cr}$$
The last inequality follows because if $k \ge 1$, then $x_k > 5$ which
implies $x_k^2 - 23 > 0$. Thus, the result is true for $n=k+1$.
Therefore, the induction proof is complete.
\vfill\eject
5. For an $n \times n$ matrix $X$, we say $\lambda$ is an
eigenvalue if $\det (\lambda I - X) = 0$. Let $A$ be an $m \times n$
matrix and let $B$ be an $n \times m$ matrix. Prove that $AB$ and
$BA$ have the same non-zero eigenvalues.
\bigskip
Solution.
\smallskip
Without loss of generality, we assume $m \ge n$. Let
$$X = \pmatrix A&0 \endpmatrix _{m \times m} \text{ and }
Y = \pmatrix B\\ 0 \endpmatrix _{m \times m} .$$
We are to show that
$$XY = AB \text { and } YX = \pmatrix BA & 0\\ 0 & 0
\endpmatrix $$
have the same eigenvalues.
For any positive $\epsilon$ small enough, $X + \epsilon I$ is
non-singular. Therefore,
$$\eqalign{
\det (\lambda I - XY ) &= \lim_{\epsilon \to 0} \det (\lambda I - (X +
\epsilon I )Y) \cr
&= \lim_{\epsilon \to 0} \det ((X + \epsilon I)^{-1}) \det (\lambda I
- (X + \epsilon I) Y) \det (X + \epsilon I) \cr
&= \lim_{\epsilon \to 0} \det ((X + \epsilon I)^{-1} (\lambda I - (X +
\epsilon I)Y)(X + \epsilon I)) \cr
&= \lim_{\epsilon \to 0} \det (\lambda I - Y (X + \epsilon I)) \cr
&= \det (\lambda I - YX) .\cr}$$
\vfill\eject
\centerline{\bf 1999 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
\bigskip
1. Let $SC$ be the semicircle with $y \ge 0$ centered at $(1,0)$ with
radius 1. Let $C_a$ be the circle with radius $a > 0$ and center $(0,0)$
and denote the point $(0,a)$ by $P$. Consider the line through $P$ and
the intersection of $SC$ and $C_a$. What is the limiting position of the
$x$-intercept of this line as $a \to 0$?
\bigskip
Solution.
\smallskip
The limiting position is $x=4$. The circles intersect at
$$\biggl( {a^2 \over 2}, {a \over 2} \sqrt {4 - a^2} \biggr) .$$
The line through this point and $(0,a)$ is
$$y = a + \biggl( {\sqrt {4 - a^2} - 2 \over a} \biggr) x$$
and the $x$-intercept is
$$x = {a^2 \over 2 - \sqrt {4 - a^2}} .$$
Taking the limit as $a \to 0$ yields 4 as the limit.
\vfill\eject
2. Find the limit
$$\lim_{N \to \infty} \biggl( 1 - 2 \sum_{n=1}^N {1 \over 16n^2 - 1}
\biggr) .$$
\bigskip
Solution.
\smallskip
Observe that
$${1 \over 16n^2 - 1} = {1 \over 2} \biggl( {1 \over 4n-1} - {1 \over
4n+1} \biggr) .$$
The expression in the parentheses above is thus
$$\sum_{n=0}^{2N} {1 \over 2n+1} (-1)^n .$$
However, Gregory's series for the arctangent is
$$\text{Tan} ^{-1} x = \sum_{n=0}^\infty (-1)^n {x^{2n+1} \over 2n+1}
.$$
The Alternating Series Test plus the Lagrange form of the remainder
in Taylor's Theorem can be used to show that the series on the right
converges at $x=1$ to the function on the left, and therefore to $\pi
/ 4$.
\vfill\eject
3. For $n$ positive real numbers with minimum $m$ and maximum $M$, let
$A$ and $G$ denote their arithmetic and geometric means. Prove that
$$A - G \ge n^{-1} ( \sqrt M - \sqrt m )^2 .$$
\bigskip
Solution.
\smallskip
Let the $n$ positive real numbers be $x_1, \ldots , x_n$ and assume
$x_1 = m$ and $x_n = M$. The inequality
$$A - G \ge ( \sqrt M - \sqrt m )^2 / n$$
is equivalent to
$$\sum_{j=1}^n x_j - n \biggl( \prod_{j=1}^n x_j \biggr) ^{1/n} \ge M
- 2 \sqrt {Mm} + m$$
or
$$\sum_{j=2}^{n-1} x_j + 2 \sqrt {Mm} \ge n \biggl( \prod_{j=1}^n x_j
\biggr) ^{1/n} .$$
Applying the AM-GM inequality to the $n$ numbers $\sqrt {Mm}, x_2,
x_3, \ldots , x_{n-1}, \sqrt {Mm}$, we get
$$\sum_{j=2}^{n-1} x_j + 2 \sqrt {Mm} \ge n \cdot \biggl(
\prod_{j=2}^{n-1} x_j \cdot \sqrt {Mm} \sqrt {Mm} \biggr) ^{1/n}
= n \cdot \biggl( \prod_{j=1}^n x_j \biggr) ^{1/n} ,$$
as needed.
\vfill\eject
4. Find all possible continuous and differentiable curves $C$ which have
the following properties. The curve $C$ lies in the first quadrant and
contains the point $(0,0)$. Whenever $P$ is on $C$ the interior of the
rectangle $R$ bounded by the coordinate axes and horizontal and vertical
lines through $P$ is separated into two parts by $C$. When the part
adjacent to the $x$-axis is rotated about the $x$-axis and the part
adjacent to the $y$-axis is rotated about the $y$-axis, two solids of
equal volume are generated.
\bigskip
Solution.
\smallskip
In order for $C$ to always divide $R$ into two and only two separate
parts, $C$ must be an increasing function. Let $C$ be given by
$y=f(x)$. The volumes of the two solids are
$$V_1 = \int_0^x \pi (f(t))^2 dt \ \ \ \ \text{and}\ \ \ \ V_2 =
\int_0^x 2 \pi t(f(x) - f(t)) dt .$$
Setting $V_1 = V_2$, canceling the $\pi$ and breaking the $V_2$
integral into two parts gives
$$\int_0^x (f(t))^2 dt = \int_0^x 2t f(x) dt - \int_0^x 2t f(t) dt .$$
Differentiate both sides with respect to $x$ and simplify to get
$$(f(x))^2 = x^2 f' (x) \ \ \ \ \text{or} \ \ \ \ y^2 = x^2 {dy \over
dx} .$$
Separation of variables and integration gives the family of curves
$$y = {x \over 1 + cx} .$$
The point $(0,0)$ is on each curve in the family, and if $c \ge 0$
the domain is $[0, \infty )$, while if $c<0$ the domain is $[0,
1/\vert c \vert )$.
\vfill\eject
5. Let $A_n$ denote the $n \times n$ matrix whose $(i,j)$ entry is
$\text{GCD} (i,j)$. Compute $\det (A_n)$.
\bigskip
Solution.
\smallskip
We will show that one can use elementary column operations to reduce
$A_n = ( v_1, v_2, \ldots , v_n )$, where the $v_j$ is the
infinite vector whose $i$th coordinate is $\text{GCD} (i,j)$, to
$( w_1, w_2, \ldots , w_n )$, where $w_j$ is the
vector whose $i$th coordinate is $\phi (j)$ if $j \vert i$ and 0
otherwise, $\phi (j)$ being the Euler totient function which counts
the number of positive integers less than or equal to $j$ and
relatively prime to it. First we need a lemma.
\medskip
$\underline{\text{Lemma}}$.
$$\sum_{i \vert n} \phi (i) = n .$$
\medskip
$\underline{\text{Proof}}$. The number of elements of order $i$ in
the group $\Z _n$ is $\phi (i)$ if $i \vert n$ and 0 otherwise. The
expression on the left is the number of elements in $\Z _n$ grouped
by order, but this is clearly $n$.
We prove the result by induction. The case $n=1$ is clear. Given
$( v_1, v_2, \ldots , v_n , v_{n+1} )$ as above, by the inductive
hypothesis we can use elementary column operations to reduce this to $(
w_1, w_2, \ldots , w_n, v_{n+1} )$. Consider
$$\sum_{j \vert n+1} w_j .$$
Its $i$th coordinate is
$$\sum_{{\scriptstyle j \vert n+1} \atop {\scriptstyle j \vert i}}
\phi (j) = \sum_{{\scriptstyle j \vert \text{GCD} (n+1,i)}} \phi (j)
= \text{GCD} (n+1,i) ,$$
so
$$\sum_{j \vert n+1} w_j = v_{n+1} .$$
Therefore,
$$v_{n+1} - \sum_{{\scriptstyle j \vert n+1} \atop {\scriptstyle j
\ne n+1}} w_j = w_{n+1}$$
and we have column-reduced our original matrix to $( w_1,
w_2, \ldots , w_n, w_{n+1} )$.
We can use the column operations above to reduce the matrix $A_n$ to
an upper triangular matrix with $\phi (j)$ on the diagonal $j=1, 2,
\ldots , n$, so
$$\det (A_n) = \prod_{j=1}^n \phi (j) .$$
\bye