\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 2000 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 distance between 
the $x$-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} .$$
Now the distance between the $x$-coordinates of $P$ and $Q$ is
$$D = \bigg\vert 2p + {1 \over 2p} \bigg\vert .$$
Assuming $p > 0$,
$$D = 2p + {1 \over 2p} .$$
Using the AM--GM Inequality, it is known that for all $x > 0$,
$$x + {1 \over x} \ge 2,$$
with equality when $x=1$.  
Therefore, $p = 1/2$ if $p>0$ or $p = -1/2$.
Hence, the coordinates of $P$ resulting in a minimum distance between 
the $x$-coordinates of $P$ and $Q$ are
$$\biggl( \pm {1 \over 2}, {1 \over 4} \biggr) .$$
\bigskip
From {\it Crux Mathematicorum}, Problem 323, Proposed by Jack Garfunkel, 
Forest Hills High School, Flushing, New York and M. S. Klamkin, 
University of Alberta, 4 (1978), 255--256.
\medskip
2.  If $xyz = (1-x)(1-y)(1-z)$ where $0 \le x, y, z \le 1$, show that
$$x(1-z) + y(1-x) + z(1-y) \ge {3 \over 4} .$$   
\bigskip
Solution by Basil C. Rennie, James Cook University of North Queensland, 
Australia.
\medskip
From $0 \le x \le 1$ and $(x - 1/2)^2 \ge 0$, we get $0 \le x(1-x) \le 
1/4$.  From this and two similar results,
$$xyz(1-x)(1-y)(1-z) \le {1 \over 64} .\eqno(1)$$
By the given relation, the left side of (1) is $(xyz)^2$; so $xyz \le 
1/8$.  Using the relation again yields
$$x(1-z) + y(1-x) + z(1-y) = 1 - 2xyz \ge {3 \over 4} .$$
Equality occurs when $x = y = z = 1/2$.
\bigskip
3.  Let $n \ge 3$ points be given in the plane.  Prove that three of them form 
an angle which is at most $\pi / n$.  
\bigskip
Solution.
\medskip
Suppose the $n$ points are labeled as $P_j$, $1 \le j \le n$.  Note that 
if any $3$ of them are collinear then an angle of measure zero exists, 
so we may assume no $3$ of them are collinear.  Let $P$ be the convex 
polygon obtained as the convex hull of the $n$ points.  Then each of the 
points is either a vertex or an interior point of $P$ and at least $3$ 
of them are vertices.  Assume then that $P_1$, $P_2$, $P_n$ are adjacent 
vertices of $P$ with $P_1$ ``between'' $P_2$ and $P_n$.  Then (by 
relabeling points as needed) we have
$$\eqalign{
\pi &= m ( \angle P_1 P_2 P_n ) + m( \angle P_1 P_n P_2 ) + m( \angle P_2 
P_1 P_n ) \cr
&= m( \angle P_1 P_2 P_n ) + m( \angle P_1 P_n P_2 ) + 
\sum_{i=2}^{n-1} m( \angle P_i P_1 P_{i+1} ) .\cr}$$
So by the pigeonhole principle, at least one of these $n$ angles has 
measure less than or equal to $\pi / n$.
\bigskip
From Joh. Bernoulli, 1697.
\medskip
4.  Justify as far as you can, the equality
$$\int_0^1 x^x dx = 1 - {1 \over 2^2} + {1 \over 3^3} - {1 \over 4^4} + 
{1 \over 5^5} - \cdots .$$ 
\bigskip
Solution.
\medskip
Formally, we have ($\ln$ denotes the natural logarithm)
$$\int _0^1 x^x dx = \int _0^1 e^{x \ln x} dx = \sum_{n=0}^\infty {1 \over 
n!} \int _0^1 (x \ln x)^n dx .$$
If $m \le n$, we have, using integration by parts,
$$\int _0^1 x^n (\ln x)^m dx = -{m \over n+1} \int _0^1 x^n (\ln x)^{m-1} 
dx ,$$
and so
$$\int _0^1 (x \ln x)^n dx = (-1)^n {n! \over (n+1)^n} \int _0^1 x^n dx = 
{(-1)^n n! \over (n+1)^{n+1}} .$$
We get, then,
$$\int _0^1 x^x dx = \sum_{n=1}^\infty {(-1)^{n-1} \over n^n} = 1 - {1 
\over 2^2} + {1 \over 3^3} - {1 \over 4^4} + {1 \over 5^5} - \cdots .$$
%$\underline{\text{Note}}$.  Mention should be made of the fact that 
%$x^x \to 1$ as $x \to 0^+$, so that the integral is ``removably'' 
%improper.  Also, the interchange of the integral and the sum requires 
%justification, such as uniform convergence.  This did not bother 
%Bernoulli much in 1697, however.
\medskip
\noindent $\underline{\text{Note}}$.  Bernoulli's 1697 solution ended here.  The
need to deal with uniform convergence-type questions was not
recognized until later.
\medskip
\noindent Let $\{ f_n (x) \} _{n=0}^\infty$ be the sequence of functions defined 
by
$$f_n (x) = \cases ( x \ln x )^n / n!,& \text{$n \ge 1$, $\ 0 < x \le 1$}\\
1,& \text{$n = 0$, $0 \le x \le 1 $.}
\endcases$$
$n$-fold application of L'H\^{o}pital's theorem gives
$$\lim_{x \to 0^+} f_n (x) = 0,\ \ (n > 0),$$
so $f_n (x)$ is continuous, and therefore integrable, on $[0,1]$.  On 
the interval $(0,1)$ $x \ln x$ is negative and has a single local 
minimum of $-e^{-1}$.  It follows that on $[0,1]$,
$$\vert f_n (x) \vert \le {1 \over e^n n!}$$
for $n \ge 0$.  One sees easily that
$$\vert f_n (x) \vert < {1 \over n^2}$$
for all $n \ge 1$.  But
$$\sum_{n=1}^\infty {1 \over n^2}$$
converges, so by the Weierstrass M-Test the sequence $\{ f_n (x) \} 
_{n=0}^\infty$ converges uniformly on $[0,1]$.  This, in turn, 
guarantees that
$$\sum_{n=0}^\infty \int_0^1 f_n (x) dx = \int_0^1 \biggl( 
\sum_{n=0}^\infty f_n (x) \biggr) dx = \int_0^1 x^x dx .$$
\bigskip
5.  Show that a polynomial in $x$ with real coefficients which takes 
rational values for rational $x$ and (real) irrational values for 
(real) irrational $x$ must be linear. 
\bigskip
Solution.
\medskip
Note that the polynomial cannot be constant.  Denote the polynomial by 
$f(x)$ and its degree by $n$.  Since $x \in \Q$ implies $f(x) \in \Q$, we 
know that $f(0) = y_0$, $f(1) = y_1$, $\ldots$, $f(n) = y_n$ are all 
rational.  Now consider
$$g(x) = \sum_{i=0}^n y_i L_i (x) ,$$
where
$$L_i (x) = \prod_{\scriptstyle k=0 \atop \scriptstyle k \ne i}^n {(x-k) 
\over (i - k)} .$$
Since $f(x)$ and $g(x)$ are both polynomials of degree $n$ which agree at 
the $n+1$ values $0, 1, \ldots , n$, $f(x)$ and $g(x)$ must have the same 
coefficients, so $f(x)$ must have rational coefficients.

Now assume to the contrary that $n > 1$.  Since the coefficients of $f(x)$ 
are rational, we can write
$$f(x) = (a_n x^n + \cdots + a_1 x + a_0 ) / d ,$$
where $a_i$ and $d$ are integers.  We will derive a contradiction by 
finding a rational value $r$ such that $f(x) = r$ has a real irrational 
solution.  Let $r = (p+a_0)/d$, with $p$ a prime number to be determined.  
Without loss of generality, we may assume that $a_n > 0$.  For 
sufficiently large $p$, $f(x) = r$ has a positive root which is 
approximately
$$\biggl( {p \over a_n} \biggr) ^{1/n} .$$
But by the Rational Root Test, the only positive rational roots of $f(x) = 
r$ are $1 / \lambda$ or $p / \lambda$, where $\lambda$ is a divisor of 
$a_n$.  But for sufficiently large $p$, the former are too small while the 
latter are too large, so $f(x) = r$ has a real irrational root.  
Contradiction.
\vfill\eject
\centerline{\bf 2000 Missouri MAA Collegiate Mathematics Competition}
\vskip 6pt
\centerline{\bf Session II}
\bigskip
1.  Two points are chosen at random (with a uniform distribution) from 
the unit interval $[0,1]$.  What is the probability that the points will 
be within a distance of $\epsilon$ of each other? 
\bigskip
Solution.
\medskip
Clearly if $\epsilon \ge 1$, then the probability is $1$.  If $0 \le 
\epsilon < 1$, then the probability is the area of the region defined 
by $0 \le x \le 1$, $0 \le y \le 1$, and $\vert x-y \vert \le 
\epsilon$ (divided by the area of the unit square).  But this is $1-2 
\cdot (1 - \epsilon )^2 / 2 = 2 \epsilon - \epsilon ^2$.

\eps{diag.eps}
\bigskip
From Macalester College Problem of the Week \# 820.
\medskip
2.  Write Pascal's Triangle as an infinite array as follows:
$$\matrix 1&1&1&1&1&\cdots \cr
          1&2&3&4&5&\cdots \cr
          1&3&6&10&15&\cdots \cr
          1&4&10&20&35&\cdots \cr
          1&5&15&35&70&\cdots \cr
          \vdots&\vdots&\vdots&\vdots&\vdots&\ddots \cr \endmatrix $$
where the first row and first column consist entirely of ones and every 
other entry is formed by taking the sum of the entry to the left and the 
entry above.  For each positive integer $n$, let $D_n$ denote the $n$ by 
$n$ matrix formed by the first $n$ rows and first $n$ columns of the 
array.  What is the determinant of $D_n$?  Prove your answer.
\bigskip
Solution.
\medskip
Direct calculations for small values of $n$ suggest that $\det ( D_n 
) = 1$ for all $n$.
\smallskip
Outline of Proof:
\smallskip
Perform the following elementary row operations on $D_n$ in the order 
specified to change rows $n$ through $2$:
\smallskip
\item{1.} Subtract the $(n-1)$st row from the $n$th row,
\item{2.} Subtract the $(n-2)$nd row from the $(n-1)$st row,
$$\vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
\item{$(n-1)$.} Subtract the $1$st row from the $2$nd row.
\smallskip
Because of the way the array is constructed, this will translate each 
column one position to the right, and will make the first column a 
one followed by $(n-1)$ zeros.  Repeating this process for rows $n$ 
through $3$, then for rows $n$ through $4$, etc. gives an upper 
triangular matrix with ones on the diagonal, which clearly has 
determinant $1$.
\smallskip
Alternatively, expansion by minors of the first column after the 
first set of row operations yields $\det ( D_n ) = \det ( D_{n-1} )$. 
This and the values for small $n$ give the result.
\bigskip
3.  Given an $n \times n$ checkerboard with the four corners removed, 
characterize for which $n$ this deleted board can be covered with $3 
\times 1$ rectangles.
\bigskip
Solution.
\medskip
There are three cases to consider.  If $n \equiv 0 \pmod 3$, then 
there are $n^2 - 4$ squares in the deleted board but since this is 
not a multiple of $3$, such a covering is impossible.  If $n \equiv 2 
\pmod 3$, the board can be decomposed into a large central $n \times 
(n-2)$ rectangle and two narrow peripheral $(n-2) \times 1$ 
rectangles each of which can clearly be covered by $3 \times 1$ 
rectangles.  If $n \equiv 1 \pmod 3$ i.e. $n = 3k+1$, label the 
squares $1$, $2$, or $3$ as shown in the figure.  Any $3 \times 1$ 
rectangle put on the board will cover exactly one of each of these 
numbers, so if a covering is possible, there must be the same number 
of $1$'s, $2$'s, and $3$'s.  However, there are $4 + 7 + \cdots + 
(n-3) + (n-2) + (n-3) + \cdots + 7 + 4 = 3k^2 + 2k - 3$ squares 
labeled with a $1$.  If there were an equal number of squares with 
each label there would be $[(3k+1)^2 - 4]/3 = 3k^2 + 2k - 1$ squares 
labeled with a $1$.  Contradiction.
\vfill\eject
\null
\eps{square.eps}
\bigskip
4.  For $n \ge 2$, let $x_1, \ldots , x_n$ be non-zero real numbers 
whose sum is zero.  Show that there are $i,j$ with $1 \le i < j \le 
n$ such that
$$1/2 \le \vert x_i / x_j \vert \le 2 .$$ 
\bigskip
Solution.
\medskip
Let $a = \min \{ x_i \}$ and $b = \max \{ x_i \}$.  We may assume (by 
replacing each $x_i$ with $-x_i$ if necessary) that $\vert a \vert > 
b$.  If $\vert a \vert \le 2b$, then $1 \le \vert a/b \vert \le 2$ 
and we are done.  So assume that $b < \vert a \vert / 2$.

Now consider the (infinitely many) intervals
$$\ldots , \biggl[ {\vert a \vert \over 2^n} , {\vert a \vert \over 
2^{n-1}} \biggr) , \ldots , \biggl[ {\vert a \vert \over 8} , {\vert 
a \vert \over 4} \biggr) , \biggl[ {\vert a \vert \over 4}, {\vert a 
\vert \over 2} \biggr) .$$
One of these intervals must contain $2$ of the positive $x_i$ values 
for otherwise
$$\sum_{x_i > 0} x_i < {\vert a \vert \over 2} + {\vert a \vert \over 
4} + \cdots = \vert a \vert \cdot \biggl( {1 \over 2} + {1 \over 4} + 
{1 \over 8} + \cdots \biggr) = \vert a \vert ,$$
which is impossible since
$$\sum_{i=1}^n x_i = 0 .$$
So there exist $i \ne j$ such that $x_i$ and $x_j \in [ \vert a \vert 
/ 2^n , \vert a \vert / 2^{n-1} )$ for some $n$ and consequently
$$1/2 \le x_i / x_j \le 2 .$$
\bigskip
From {\it From Erd\H{o}s to Kiev} by Ross Honsberger, Dolciani 
Mathematical Exposition, 1995, pp. 164--166.
\medskip
5.  This problem concerns sequences $x_1 x_2 \cdots x_n$ in which each 
$x_i$ is either $a$, $b$, or $c$.  Determine the number of those sequences
which have length $n$, begin and end with the letter $a$, and in which 
adjacent terms are always different letters. 
\bigskip
Solution.
\medskip
We begin by looking briefly at the sequences of a few small values of 
$n$.  Let the number of sequences of length $n$ be denoted by $t_n$.

$$
\vbox{\tabskip=0pt \offinterlineskip
\def\tablerule{\noalign{\hrule}}
\halign to200pt{\strut#& \vrule#\tabskip=1em plus2em&
 \hfil#& \vrule#& #\hfil& \vrule#&
 #\hfil& \vrule#\tabskip=0pt\cr\tablerule
&&$n$ &&Sequences &&$t_n$&\cr\tablerule
&&1 &&$a$ &&1&\cr\tablerule
&&2 &&none &&0&\cr\tablerule
&&3 &&$aba$, $aca$ &&2&\cr\tablerule
&&4 &&$abca$, $acba$ &&2&\cr\tablerule
&&5 &&$ababa$, $abaca$, $acaba$, &&&\cr
&& &&$acaca$, $abcba$, $acbca$ &&6&\cr\tablerule \noalign{\smallskip} }}
$$

In attempting to see how sequences of length $n$ might be derived from 
shorter ones, one might notice that a sequence of length $n$ can be 
obtained by attaching either $ba$ or $ca$ at the end of any sequence 
of length $n-2$.  For example,

\eps{abc.eps}
\bigskip
Of course, all the sequences generated in this way have the letter $a$ in 
the third-last position.  Conversely, a sequence of length $n$ whose 
third-last term is the letter $a$ yields an acceptable sequence of length 
$n-2$ when its last two terms are dropped.  Thus the number of sequences 
of length $n$ in which the third-last term is the letter $a$ is 
$2t_{n-2}$.

For the rest of the sequences of length $n$, the third-last term is 
either $b$ or $c$, and each sequence of this kind provides a single 
sequence of length $n-1$ by simply deleting its second-last term:
$$\eqalign{
&a \cdots bca \to a \cdots ba,\cr
&a \cdots cba \to a \cdots ca.\cr}$$
(This is not allowed when the third-last term is the letter $a$.)  
Conversely, there is only one possible letter that can be inserted 
between the last two terms of a sequence, and doing so clearly extends 
one of length $n-1$ to one of length $n$.  Therefore there are $t_{n-1}$ 
sequences of length $n$ in which the third-last term is $b$ or $c$, and 
we have altogether that
$$t_n = t_{n-1} + 2t_{n-2}$$
with initial conditions $t_1 = 1$ and $t_2 = 0$.
Now assume $t_n = r^n$.  Substituting into the difference equation yields
the characteristic equation $r^2 - r - 2 = 0$, from which $r=2$ or $r=-1$.  So
the general solution is
$$t_n = c_1 2^n + c_2 (-1)^n .$$
Using the initial conditions lets us find $c_1 = 1/6$ and $c_2 = -2/3$. 
Therefore,
$$t_n = {1 \over 3} 2^{n-1} + {2 \over 3} (-1)^{n-1} .$$
%Now, if we attach the unknown numbers $t_n$ to the terms of a power 
%series $f(x)$ as follows,
%$$f(x) = t_1 + t_2 x + t_3 x^2 + \cdots + t_n x^{n-1} + \cdots ,$$
%then
%$$x \cdot f(x) = t_1 x + t_2 x^2 + \cdots + t_{n-1} x^{n-1} + \cdots ,$$
%and
%$$2x^2 \cdot f(x) = 2t_1 x^2 + \cdots + 2t_{n-2} x^{n-1} + \cdots .$$
%Subtracting the second and third rows from the first, the recursion $t_n 
%- t_{n-1} + 2t_{n-2} = 0$ gives (recall $t_1 = 1$ and $t_2 = 0$),
%$$(1-x-2x^2) f(x) = t_1 + (t_2 - t_1) x = 1-x ,$$
%and therefore
%$$f(x) = {1-x \over 1-x-2x^2} .$$
%Expanding this expression into its partial fractions, we obtain
%$${1-x \over (1-2x)(1+x)} = {A \over 1-2x} + {B \over 1+x}$$
%so
%$$1-x = A(1+x) + B(1-2x) .$$
%For $x=-1$ and $1/2$, respectively, we find $2=3B$ and $1/2 = 3A/2$, 
%giving $A=1/3$ and $B=2/3$.  Thus
%$$\eqalign{
%f(x) &= {1 \over 3} (1-2x)^{-1} + {2 \over 3} (1+x)^{-1} \cr
%&= {1 \over 3} (1+2x+ \cdots + 2^{n-1} x^{n-1} + \cdots ) \cr
%&\ \ + {2 \over 3} (1-x+ \cdots + (-1)^{n-1} x^{n-1} + \cdots ) ,\cr}$$
%from which the coefficient $t_n$ of $x^{n-1}$ is
%$$t_n = {1 \over 3} \cdot 2^{n-1} + {2 \over 3} \cdot (-1)^{n-1} = 
%{2^{n-1} + 2(-1)^{n-1} \over 3} .$$
\bye
