%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
